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(N-1) + T(N-2) + ... + T(1) & T(N-1) = T(N-2) + T(N-3) + ... + T(1). => T(N) = 2T(N-1) => 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.

• This is a brilliant article. Not only does it contain the solution but also the thought process of how to break it down and conclude one thing after the other

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

• In the first solution

// Old
for (int nextPosition = position + 1; position <= furthestJump; position++)
// New
for (int nextPosition = furthestJump; nextPosition > position; position--)

The for loop is slightly incorrect. It should be nextposition++ and not position++

• @piy9 Thanks for pointing that out! Just fixed. FYI @andreifirst .

• The code, that checks cutom test cases, throws exceptions when null or [] is specified as an input for the custom test case. Shouldn't such things always be checked?

• approach #1 recursion is not constant space

• The space complexity of Approach #3 (Dynamic Programming Bottom-up) [Time limit exceeded] is O(n), not O(2n) = O(n), because there is no recursion.

• 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:

1. start at the end of array-1 (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 i-1) for element which allows you to jump over this trap (so element which has value > (i-j))
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 j-1 (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.

• 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(i-j, i):
if A[k] > i-k:
return True
return False

``````    for 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.

• Thanks for the article!
Learned a lot.

• I learned a lot from this problem and solution. Thank you !

• class Solution {
public:
bool canJump(vector<int>& A) {
int max_jump = 0;
for (int i =0; i < A.size(); ++i){
if(max_jump >= i){
max_jump = max(max_jump,A[i] + i);
}
}
return (max_jump >= A.size() - 1);
}
};

• 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 i-th 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:

1. Start with a pointer at the end of the array, and store the last index as the NeedToReach Index
2. Tracing backward the entire array, if a position's index plus its value is >= NeedToReach, update NeedToReach as the current index
3. Return if (NeedToReach==0)

• Learned a lot! Thank you so much for explaining this.

• I think the run time of approach#2 is O(n) and not O(n^2). Indeed, because of array memo, each element of the array nums is visited at most once.

• first thank you! it's been very helpful I have only one question, there is an option to wright the Approach #1 (Backtracking) [Stack Overflow] without any loop?

• 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.