Jump Game II
Jump Game II: Finding the Minimum Jumps
The Jump Game II problem builds upon the classic Jump Game challenge, where instead of determining if you can reach the last index, you aim to calculate the minimum number of jumps required to do so.
This problem requires careful planning and optimization to find the shortest path in terms of jumps.
Problem Description
You are given an array nums, where each element nums[i] represents the maximum number of positions you can jump forward from index i.
Starting from index 0, determine the minimum number of jumps required to reach the last index.
Example 1
Input: nums = [2,4,1,1,1,1]
Output: 2
Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.
Example 2
Input: nums = [2,1,2,1,0]
Output: 2
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 100
Solution Approach: Greedy Algorithm
To find the minimum number of jumps, we use a greedy approach that focuses on extending the farthest reachable position at each step.
Key Idea
Keep Track of Jumps and Boundaries:
- Use two variables:
- current_end to mark the boundary of the current jump.
- farthest to track the farthest position reachable with the current jumps.
- Increment the jump count each time you reach the boundary (current_end).
- Use two variables:
Iterate Through the Array:
- At each index i, update farthest as the maximum of its current value and i + nums[i].
- If the current index equals current_end, increment the jump count and update current_end to farthest.
Stop When You Reach the Last Index:
- Once you’ve extended beyond or reached the last index, the loop ends.
There are mainly Four approach to solve this problem –
- Recursion
- Dynamic Programming (Top-Down)
- Dynamic Programming (Bottom-Up)
- Greedy
1. Recursion
- Time complexity: O(n!)
- Space complexity: O(n)
Python
C++
Java
JavaScript
Python
class Solution:
def jump(self, nums: List[int]) -> int:
def dfs(i):
if i == len(nums) - 1:
return 0
if nums[i] == 0:
return float('inf')
end = min(len(nums) - 1, i + nums[i])
res = float('inf')
for j in range(i + 1, end + 1):
res = min(res, 1 + dfs(j))
return res
return dfs(0)C++
class Solution {
public:
int jump(vector& nums) {
return dfs(nums, 0);
}
private:
int dfs(vector& nums, int i) {
if (i == nums.size() - 1) {
return 0;
}
if (nums[i] == 0) return 1000000;
int res = 1000000;
int end = min((int)nums.size() - 1, i + nums[i]);
for (int j = i + 1; j <= end; ++j) {
res = min(res, 1 + dfs(nums, j));
}
return res;
}
}; Java
public class Solution {
public int jump(int[] nums) {
return dfs(nums, 0);
}
private int dfs(int[] nums, int i) {
if (i == nums.length - 1) {
return 0;
}
if (nums[i] == 0) {
return 1000000;
}
int res = 1000000;
int end = Math.min(nums.length - 1, i + nums[i]);
for (int j = i + 1; j <= end; j++) {
res = Math.min(res, 1 + dfs(nums, j));
}
return res;
}
}JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
jump(nums) {
const dfs = (i) => {
if (i === nums.length - 1) {
return 0;
}
if (nums[i] === 0) return 1000000;
let res = 1000000;
const end = Math.min(nums.length - 1, i + nums[i]);
for (let j = i + 1; j <= end; j++) {
res = Math.min(res, 1 + dfs(j));
}
return res;
}
return dfs(0);
}
}2. Dynamic Programming (Top-Down)
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool canJump(vector& nums) {
unordered_map memo;
return dfs(nums, 0, memo);
}
private:
bool dfs(vector& nums, int i, unordered_map& memo) {
if (memo.count(i)) {
return memo[i];
}
if (i == nums.size() - 1) {
return true;
}
if (nums[i] == 0) {
return false;
}
int end = min((int)nums.size(), i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dfs(nums, j, memo)) {
memo[i] = true;
return true;
}
}
memo[i] = false;
return false;
}
}; Java
public class Solution {
public boolean canJump(int[] nums) {
Map memo = new HashMap<>();
return dfs(nums, 0, memo);
}
private boolean dfs(int[] nums, int i, Map memo) {
if (memo.containsKey(i)) {
return memo.get(i);
}
if (i == nums.length - 1) {
return true;
}
if (nums[i] == 0) {
return false;
}
int end = Math.min(nums.length, i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
if (dfs(nums, j, memo)) {
memo.put(i, true);
return true;
}
}
memo.put(i, false);
return false;
}
}
Python
class Solution:
def canJump(self, nums: List[int]) -> bool:
memo = {}
def dfs(i):
if i in memo:
return memo[i]
if i == len(nums) - 1:
return True
if nums[i] == 0:
return False
end = min(len(nums), i + nums[i] + 1)
for j in range(i + 1, end):
if dfs(j):
memo[i] = True
return True
memo[i] = False
return False
return dfs(0)JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
canJump(nums) {
const memo = new Map();
const dfs = (i) => {
if (memo.has(i)) {
return memo.get(i);
}
if (i == nums.length - 1) {
return true;
}
if (nums[i] === 0) {
return false;
}
const end = Math.min(nums.length - 1, i + nums[i]);
for (let j = i + 1; j <= end; j++) {
if (dfs(j)) {
memo.set(i, true);
return true;
}
}
memo.set(i, false);
return false;
}
return dfs(0);
}
}3. Dynamic Programming (Buttom-Up)
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
Where m is the length of the array queries and n is the length of the array intervals.
C++
Java
Python
JavaScript
C++
class Solution {
public:
int jump(vector& nums) {
int n = nums.size();
vector dp(n, 1000000);
dp[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
int end = min((int)nums.size(), i + nums[i] + 1);
for (int j = i + 1; j < end; j++) {
dp[i] = min(dp[i], 1 + dp[j]);
}
}
return dp[0];
}
}; Java
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
dp = [1000000] * n
dp[-1] = 0
for i in range(n - 2, -1, -1):
end = min(n, i + nums[i] + 1)
for j in range(i + 1, end):
dp[i] = min(dp[i], 1 + dp[j])
return dp[0]
Python
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
dp = [1000000] * n
dp[-1] = 0
for i in range(n - 2, -1, -1):
end = min(n, i + nums[i] + 1)
for j in range(i + 1, end):
dp[i] = min(dp[i], 1 + dp[j])
return dp[0]JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
jump(nums) {
const n = nums.length;
const dp = new Array(n).fill(1000000);
dp[n - 1] = 0;
for (let i = n - 2; i >= 0; i--) {
const end = Math.min(nums.length, i + nums[i] + 1);
for (let j = i + 1; j < end; j++) {
dp[i] = Math.min(dp[i], 1 + dp[j]);
}
}
return dp[0];
}
}4. Breadth First Search (Greedy)
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int jump(vector& nums) {
int res = 0, l = 0, r = 0;
while (r < nums.size() - 1) {
int farthest = 0;
for (int i = l; i <= r; i++) {
farthest = max(farthest, i + nums[i]);
}
l = r + 1;
r = farthest;
res++;
}
return res;
}
}; Java
public class Solution {
public int jump(int[] nums) {
int res = 0, l = 0, r = 0;
while (r < nums.length - 1) {
int farthest = 0;
for (int i = l; i <= r; i++) {
farthest = Math.max(farthest, i + nums[i]);
}
l = r + 1;
r = farthest;
res++;
}
return res;
}
}Python
class Solution:
def jump(self, nums: List[int]) -> int:
res = 0
l = r = 0
while r < len(nums) - 1:
farthest = 0
for i in range(l, r + 1):
farthest = max(farthest, i + nums[i])
l = r + 1
r = farthest
res += 1
return resJavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
jump(nums) {
let res = 0, l = 0, r = 0;
while (r < nums.length - 1) {
let farthest = 0;
for (let i = l; i <= r; i++) {
farthest = Math.max(farthest, i + nums[i]);
}
l = r + 1;
r = farthest;
res++;
}
return res;
}
}
