Array Game: Can you escape the array?
The following is a problem from Hackerrank and I explain my approach/logic in solving it. (https://www.hackerrank.com/challenges/java-1d-array/problem)
Basic brief of the problem:
- We have an integer array of length n.
- We control a "player" that is able to traverse through this array. The player can move through the array in any direction, either in increments of 1 OR in increments of a specified "leap value" (which is given as a parameter).
- The values in the indexes can either be 1 or 0. We can only make the player move into a particular index if it has a 0 in it. If it has a 1 in it, you cannot enter it.
- The player always starts at index 0 (which is always assumed to have a value of 0). It is our job to determine whether the "player" can traverse through the array and ultimately exit the array through the other end of it. We can exit the array if we are able to reach the last index or if we reach an index i, where i+leap would be more than the last index of the array.
Basic approach (using recursion)
The basic idea of our approach is to use recursion and explore each inner pathway to see if it will eventually end up in an index where it is possible to exit out of the array. So for each method call, it will traverse to a new index and then "explore" which paths are accessible to it. It will traverse down each accessible path and call the method again and do the same, resulting in a deep exploration of all possible paths.
The problems:
The major problem with this is that since we are able to traverse in both directions (forwards and backwards) , the program will end up moving back and forth betweene 2 indexes infinitely. That is, if those indexes are not in an array exitable index.
A solution
We need to keep some kind of a track on which indexes we have already traversed on so that we don't repeat the same explorations on them. That way we won't keep moving back and forth between indexes.
Solution #1 (Naive):
We could keep a value called "Prev" (previous) which keeps track of which index we were previously on. So that when we enter a call stack of the move method, we will know which one we were on in the previous call stack and prevent the program from going back to that.
Problems with this approach:
Thr problem with this occurs if there is a gap of call stacks of more than 1. What if you end up moving to a new index and find that you can leap backwards to an index (which you were previously on 3 calls ago?). You'd only know where you were in the previous call stack...not the one 3 calls ago.
Solution #2 (Efficient):
But what if there's a way to not have to loop through an array each time? Here's an efficent solution (which is inspired by the idea of a stack)
What we do is keep a " Latest Filled Value ". As we progress through the array, we ensure that we explore all possible indexes up until a point. After we explore all those indexes, we update the value of this point. With this point we know that everything below this value has been explored. And so we will only explore indexes above this point. This is a way of making the traversible area smaller and smaller as we go along.
How it is implemented
To implement this, I have divided the function into 3 main parts (the sequence is important)
- part 1 (all the backwards traversals): this is where we traverse backwards (by increments of 1 and the leap). After all the calls to this have finished, the program will reach part 2.
- part 2: Where we update the latest filled value (since we have explored everything behind us)
- Part 3: Traverse forward to all values above the fill point.
