Link: https://leetcode.com/problems/jump-game/
Solution:
Intuition
This can be solved with a simple DFS, but at best it will be o(n*n) because of the high branching factor (every position i has a range of possible positions from i+1 to i+nums[i]. Without caching, it’s o(n*n*n). BFS is even worse because we can’t early exit.
The DFS solution passes all test cases, however there is a greedy solution that is o(n). This one is pretty tricky to come up with. The key idea is to start from the back, and see if we can reach the minimum necessary position. What does this mean?
Very simple, if the second last index can reach the last index, then we now should only care about reaching the second last index because if we can reach it, then by default, we can reach the last index!
For example:
* = where we must reach
^ = current pointer
[4,0,0,0,1,4]
^ * We see that the ^ pointer can reach * because
the distance to * is less than or equal to the
max allowable jumps! (1)
[4,0,0,0,1,4]
^ * Cannot reach
[4,0,0,0,1,4]
^ * Cannot reach
[4,0,0,0,1,4]
^ * Cannot reach
[4,0,0,0,1,4]
^ * Can reach!
[4,0,0,0,1,4]
^ *
The algorithm ends with * = 0, so the last index is reachabe from the first!
Implementation
def jump_game(nums):
must_reach = len(nums)-1
for i in range(len(nums)-2, -1, -1):
distance_to = must_reach - i
if nums[i] >= distance_to:
must_reach = i
return must_reach == 0
#time: o(n)
#memory: o(1)Review 1
I initially thought that this was solvable by DP and BFS (and it is), but then I found the greedy solution very quickly. DFS will be better than BFS in this case because the branching factor is very high, but both are quite terrible.
The complexity for DP is a bit confusing, its basically linear (1d), but inside the recursion we must iterate over possible jumps which have an upper bound of n in the worst case, so thus the time cost is n*n. BFS with a visited set would be the same I believe…I don’t think it is worse.