I have a solution for this question without using memoization - that is, without changing the values in the 'mem' list. I base my solution on the fact that once I visited the 'i'th cell (that is, visited[i] == true) there is no need to come back to it, seeing as either left or right works, and if that cell has already been visited, the appropriate truth value has already been returned, and everything is combined via an 'or' statement. My solution is O(n) both timewise and spacewise, so I see no fault in it.
Thanks for your quick reply,
Date: 03 Dec 2015 13:38
Number of posts: 2
RSS: New posts
To clarify - I have a solution, and do not see any way to add memoization into it - not without increasing time complexity to O(n^2), at the very least. I can maybe change some of the values in 'mem' though I would not really need them. Is this passable, or do I have to change every single value in 'mem'?