Description
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
Solutions
1. DP?
# Time: O(nm)
# Space: O(n)
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
dp = [float('inf')] * n
dp[0] = 0
for i, num in enumerate(nums):
for j in range(1, num+1):
if i + j >= n:
break
dp[i + j] = min(dp[i] + 1, dp[i + j])
return dp[n-1]
# Time Limit Exceeded
# 91/92 cases passed (N/A)
2. Greedy
# Time: O(nm)
# Space: O(n)
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
jumps = 0
# these two variable store the index which it can reach
pre_jump_max, cur_jump_max = 0, 0
for i in range(n):
cur_jump_max = max(cur_jump_max, i + nums[i])
if pre_jump_max == n - 1:
break
if i == pre_jump_max:
jumps += 1
pre_jump_max = cur_jump_max
return jumps
# 92/92 cases passed (96 ms)
# Your runtime beats 78.9 % of python3 submissions
# Your memory usage beats 8.33 % of python3 submissions (14.9 MB)
# Time: O(n)
# Space: O(1)
class Solution:
def jump(self, nums: List[int]) -> int:
res = 0
pre_max_reach, cur_max_reach = 0, 0
for i, num in enumerate(nums):
if i > pre_max_reach:
pre_max_reach = cur_max_reach
res += 1
cur_max_reach = max(cur_max_reach, i + num)
return res
# 92/92 cases passed (92 ms)
# Your runtime beats 91.37 % of python3 submissions
# Your memory usage beats 8.33 % of python3 submissions (14.9 MB)