# Jump Game II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/jump-game-ii)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [DoorDash](https://scaleengineer.com/companies/doordash), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Mitsogo](https://scaleengineer.com/companies/mitsogo), [HashedIn](https://scaleengineer.com/companies/hashedin), [Zomato](https://scaleengineer.com/companies/zomato), [Groupon](https://scaleengineer.com/companies/groupon)
---
## Problem
You are given a **0-indexed** array of integers `nums` of length `n`. You are initially positioned at `nums[0]`.

Each element `nums[i]` represents the maximum length of a forward jump from index `i`. In other words, if you are at `nums[i]`, you can jump to any `nums[i + j]` where:

* `0 <= j <= nums[i]` and
* `i + j < n`

Return _the minimum number of jumps to reach_ `nums[n - 1]`. The test cases are generated such that you can reach `nums[n - 1]`.

**Example 1:**

**Input:** nums = [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.

**Example 2:**

**Input:** nums = [2,3,0,1,4]
**Output:** 2

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 1000`
* It's guaranteed that you can reach `nums[n - 1]`.

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a `dp` array where `dp[i]` stores the minimum number of jumps required to reach the last index from index `i`. We compute this array from the end to the beginning.
**Time:** O(n^2) · **Space:** O(n)
**Pros:** Conceptually simpler to understand than the greedy approach if you are familiar with DP.; Correctly solves the problem by exploring all possibilities in a structured way.
**Cons:** Not the most efficient solution. The time complexity can be high if the jump lengths are large, potentially leading to a 'Time Limit Exceeded' error on larger test cases.
### Explanation
This approach uses a bottom-up dynamic programming strategy. We define an array `dp` where `dp[i]` represents the minimum number of jumps needed to reach the last index `n-1` from index `i`. Our ultimate goal is to find `dp[0]`.

The logic is as follows:
- The base case is `dp[n-1] = 0`, since we are already at the last index and require no jumps.
- We then iterate backward from `i = n-2` down to `0`. For each index `i`, we consider all possible jumps we can make, which land us at an index `j` (where `i < j <= i + nums[i]`).
- The minimum jumps from `i` would be 1 (for the current jump) plus the minimum jumps required from the landing position `j`.
- So, the recurrence relation is: `dp[i] = 1 + min(dp[j])` for all reachable `j`.
- We find this minimum by iterating through all possible `j` for a given `i` and then update `dp[i]`.

```java
import java.util.Arrays;

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        // Initialize dp array with a value representing infinity
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        // Base case: 0 jumps needed from the last index to itself
        dp[n - 1] = 0;

        // Build the dp table from right to left
        for (int i = n - 2; i >= 0; i--) {
            int maxJump = i + nums[i];
            for (int j = i + 1; j <= Math.min(n - 1, maxJump); j++) {
                // If index j is reachable from the end
                if (dp[j] != Integer.MAX_VALUE) {
                    // Update dp[i] with the minimum jumps
                    dp[i] = Math.min(dp[i], 1 + dp[j]);
                }
            }
        }
        
        return dp[0];
    }
}
```
### Algorithm
- Create an integer array `dp` of size `n` and initialize its values to a large number to represent infinity.
- Set `dp[n-1] = 0`.
- Loop from `i = n-2` down to `0`:
  - For each `i`, loop from `j = i + 1` to `min(n - 1, i + nums[i])`.
  - Update `dp[i]` with `min(dp[i], 1 + dp[j])`.
- The final answer is `dp[0]`.

## Greedy Approach
This is the most optimal approach, which solves the problem in linear time. The core idea is to always make a jump that allows us to reach the farthest possible index. This can be visualized as a Breadth-First Search (BFS) where each jump constitutes moving to the next level of reachable indices.
**Time:** O(n) · **Space:** O(1)
**Pros:** Highly efficient with linear time complexity.; Optimal space usage (O(1)).
**Cons:** The logic can be less intuitive to grasp compared to the straightforward DP approach.
### Explanation
This is a highly efficient greedy approach that solves the problem in a single pass. The idea is to think of the jumps in terms of levels, similar to a Breadth-First Search (BFS). At each step, we want to make a jump that gives us the maximum possible reach for the next step.

We use three main variables:
- `jumps`: Counts the total number of jumps made.
- `current_end`: The farthest index that can be reached with the current number of `jumps`. This represents the boundary of the current 'level' in our BFS analogy.
- `farthest`: The farthest index that can be reached from any position within the current level.

The algorithm proceeds as follows:
- We iterate through the array from `i = 0` to `n-2`.
- In each iteration, we update `farthest` by calculating `i + nums[i]` and taking the maximum with the existing `farthest`. This tells us the maximum reach we can achieve from the current level.
- When our iterator `i` reaches `current_end`, it means we have explored all indices reachable with the current number of jumps. We must now 'commit' to a jump. We increment `jumps` and update `current_end` to the new `farthest` point we've discovered. This new `current_end` becomes the boundary for our next level of exploration.
- This process guarantees that we are always making the jump that covers the most ground, thus minimizing the total number of jumps.

```java
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }
        
        int jumps = 0;
        // The end of the range that can be reached with the current number of jumps
        int current_end = 0; 
        // The farthest index that can be reached from the current range
        int farthest = 0;
        
        // We iterate up to n-2 because we don't need to jump from the last element
        for (int i = 0; i < n - 1; i++) {
            // Update the farthest index we can reach
            farthest = Math.max(farthest, i + nums[i]);
            
            // If we have reached the end of the current jump's reach
            if (i == current_end) {
                // We must take another jump
                jumps++;
                // The new reach is the farthest we've found so far
                current_end = farthest;
                
                // Optimization: if the new end already covers the last index, we are done.
                if (current_end >= n - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}
```
### Algorithm
- Initialize `jumps = 0`, `current_end = 0`, `farthest = 0`.
- Loop through the array from `i = 0` to `n-2`:
  - Update `farthest = max(farthest, i + nums[i])`.
  - If `i == current_end`:
    - Increment `jumps`.
    - Set `current_end = farthest`.
- Return `jumps`.

# Solutions
### CSharp

```csharp
public class Solution { public int Jump ( int [] nums ) { int ans = 0 , mx = 0 , last = 0 ; for ( int i = 0 ; i < nums . Length - 1 ; ++ i ) { mx = Math . Max ( mx , i + nums [ i ]); if ( last == i ) { ++ ans ; last = mx ; } } return ans ; } }
```

### Java

```java
class Solution {
public
  int jump(int[] nums) {
    int ans = 0, mx = 0, last = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      mx = Math.max(mx, i + nums[i]);
      if (last == i) {
        ++ans;
        last = mx;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int jump(vector<int> &nums) {
    int ans = 0, mx = 0, last = 0;
    for (int i = 0; i < nums.size() - 1; ++i) {
      mx = max(mx, i + nums[i]);
      if (last == i) {
        ++ans;
        last = mx;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def jump ( self , nums : List [ int ]) -> int : current_reach = next_reach = steps = 0 # stop at 2nd-to-last, not the last index. # because, eg. nums=[1,0] or nums=[0,0], # just check the 2nd-to-last then we can decide if able to reach end # eg. - if input is [0], then 0 step needed for i , num in enumerate ( nums [: - 1 ]): next_reach = max ( next_reach , i + num ) if i == current_reach : current_reach = next_reach # update next-reach before if check steps += 1 # in question, guarenteed can reach end. or else need more check return steps ############ class Solution ( object ): def jump ( self , nums ): """ :type nums: List[int] :rtype: int """ pos = 0 ans = 0 bound = len ( nums ) while pos < len ( nums ) - 1 : dis = nums [ pos ] farthest = posToFarthest = 0 for i in range ( pos + 1 , min ( pos + dis + 1 , bound )): canReach = i + nums [ i ] if i == len ( nums ) - 1 : return ans + 1 if canReach > farthest : farthest = canReach posToFarthest = i ans += 1 pos = posToFarthest return ans
```