Jump Game


I would like to know how to reach the time complexity for the first approach (backtracking). Since there is no memorization, the same position can be visited multiple times. I would think the time complexity is O(2^N) because T(N) = T(N1) + T(N2) + ... + T(1) & T(N1) = T(N2) + T(N3) + ... + T(1). => T(N) = 2T(N1) => O(2^N).

@jied333 You are correct. My reasoning would only have been valid if the jump could happen both to the left and to the right. I will amend the article to reflect the correct complexity analysis.

@piy9 Thanks, glad that you like it! Thanks @andreifirst for writing this brilliant article.


I approached it using different but simple, linear algorithm, It got accepted and was placed in beats 88% of results in terms of execution time. Let me explain,
The task is to just verify if reaching last index of possible/impossible, exact paths are not needed, so let's rephrase the problem  when is it impossible to reach last index?
The answer is very simple  when you get stuck on element with value 0 and it is impossible to take a step back and jump over this element (you could say that value 0 is sort of a trap). If value is >0 then you can always proceed further until you get to the last index.
So algorithm is following:
 start at the end of array1 (we don't care what is the value of very last element)  pointer 'i':
1.1) if current element (nums[i]) is zero , take another pointer 'j' and look to the left (initate at i1) for element which allows you to jump over this trap (so element which has value > (ij))
1.1.1) if you can't find it and you reach beginning of array  return false as you can't avoid the trap
1.1.2) if you found such element, set 'i' to j1 (where j points to element you just found) and go back to step 1
1.2) if current element (nums[i]) is not zero  decrease 'i' by 1 (move further to the left/start)
This algorithm never scans the same element twice therefore it is linear and one pass (when in doubt see 1.1.2  we skip the entire area that we just scanned in 1.1)
There is one corner case which is easy to miss  first element being 0  so you can check for it right in the beginning.
 start at the end of array1 (we don't care what is the value of very last element)  pointer 'i':

These answers, while interesting, seem far more complex than it needs to be. This code works
def check(i):
j = min(i, 9)
for k in range(ij, i):
if A[k] > ik:
return True
return Falsefor i, v in enumerate(A[:len(A)1]): if v == 0 and not check(i): return False return True
The idea is to check every 0 to see if it can be jumped over. That's all it takes.

I came up with a linear solution that passed all the test and ran faster than 87% of all solutions and I would like to share it because I think it is very simple. The idea is to compute if the end of the array is reachable from the ith element (tracing backward). Starting at any position in the array, the end is reachable if: jumping from the current element, one can reach the end or another position that can reach the end. The algorithm is as followed:
 Start with a pointer at the end of the array, and store the last index as the NeedToReach Index
 Tracing backward the entire array, if a position's index plus its value is >= NeedToReach, update NeedToReach as the current index
 Return if (NeedToReach==0)

So at first, I solved it using BFS (time limit exceeded), then I solved it using DFS (same), then I solved it using BFS coming from both ends. This time, the input that made my solution exceed the time allotted was [1,1,...,1,1]. This made me think of another solution which is fast enough, but a bit more complex. My observation was that only 0's result in arrays that have no solution, so I my approach was to only handle 0's.
My approach is to start with index = 0
 Iterate from i = index to n  1 over all the numbers
 Only if 0 is found at some index i, walk back looking for a number at j that takes me to an index beyond i.
 now, look forward from i + i until the index that the number at j allows to jump to
 recursively call self with nums and index = the valid index found at the previous step
As for the complexity of this solution, I haven't analyzed it.