LeetCode 45. Jump Game II
This post was migrated from Tistory. You can find the original here.
Problem link
Approach
$ \bullet $ There’s no case where you can’t reach the last index.
$ \bullet $ So, (except for the last index) it doesn’t matter whether you can reach a specific index or not.
$ \bullet $ Let’s think in terms of ranges. The maximum index reachable at a given STEP, and the index right after it, belongs to the range of STEP+1.
$ \bullet $ Let’s figure out which STEP range the last index falls into.
At first I solved it by updating a dp array with the minimum number of steps needed to reach each index, and it passed, but it was way too slow.
After looking at someone else’s code, I realized this problem needs to be approached in terms of ranges. Below is the revised code.
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def jump(self, nums: List[int]) -> int:
max_idx = 0
end_of_jump = 0
jump = 0
for i in range(len(nums)-1):
max_idx = max(max_idx, i+nums[i])
if i == end_of_jump:
jump += 1
end_of_jump = max_idx
return jump
At the start of the loop, end_of_jump becomes $ A[0] $ .
Then, within the jump=1 range, the if condition isn’t triggered, and only max_idx gets updated.
At the end of the jump=1 range, the condition finally triggers, and end_of_jump gets updated to the farthest index reachable within jump=1.
The same process repeats within the jump=2 range.
$ … $
By the time we’ve iterated through $ A_{0} … A_{n-2} $ , jump will have been updated to the value corresponding to the last range.
The reason we don’t look at $ A_{n-1} $ is that if the final index falls at the end of a range, jump += 1 would run for the next iteration of the logic — so we only loop up to $ A_{n-2} $ .
Code before the fix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def get_min_count(self, nums, target_idx, dp):
# print(dp, target_idx)
if target_idx == 0:
return 0
result = []
for i in range(target_idx-1, -1, -1):
if nums[i] >= target_idx - i:
if dp[i] == "x":
dp[i] = self.get_min_count(nums, i, dp)
if dp[i] == -1:
continue
else:
result.append(dp[i])
# print("out",dp, target_idx, result)
return min(result) + 1 if len(result) > 0 else -1
def jump(self, nums: List[int]) -> int:
dp = [ "x" for _ in range(len(nums)) ]
return self.get_min_count(nums, len(nums)-1, dp)