# Jump Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/jump-game)
Canonical: https://scaleengineer.com/dsa/problems/jump-game
**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), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Karat](https://scaleengineer.com/companies/karat), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Shopee](https://scaleengineer.com/companies/shopee), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Turing](https://scaleengineer.com/companies/turing), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [HashedIn](https://scaleengineer.com/companies/hashedin), [Verily](https://scaleengineer.com/companies/verily), [Informatica](https://scaleengineer.com/companies/informatica)
---
## Problem
You are given an integer array `nums`. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

Return `true` _if you can reach the last index, or_ `false` _otherwise_.

**Example 1:**

**Input:** nums = [2,3,1,1,4]
**Output:** true
**Explanation:** Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Example 2:**

**Input:** nums = [3,2,1,0,4]
**Output:** false
**Explanation:** You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 105`

# Approaches
## Backtracking
This approach is a straightforward brute-force method. We simulate all possible jump combinations recursively. Starting from the first index, we explore every possible jump. If any of these paths lead to the last index, we return `true`.
**Time:** O(2^n) · **Space:** O(n)
**Pros:** Conceptually simple and easy to implement.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
### Explanation
The core idea is a recursive function, say `canJumpFrom(position, nums)`, which checks if the end can be reached from a given `position`.

*   **Base Case**: If `position` is the last index (`nums.length - 1`), we've successfully reached the end, so we return `true`.

*   **Recursive Step**: From the current `position`, we can jump to any index from `position + 1` up to `position + nums[position]`. We iterate through all these possible next positions. For each `nextPosition`, we make a recursive call `canJumpFrom(nextPosition, nums)`. If any of these recursive calls return `true`, it means we've found a valid path, and we can return `true` immediately.

*   **Failure**: If we try all possible jumps from the current `position` and none of them lead to a solution (i.e., all recursive calls return `false`), it means the end is not reachable from this `position`. We then return `false`.

This method explores all possible jump paths from the starting position, which can lead to a large number of redundant calculations.

```java
class Solution {
    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }

    private boolean canJumpFromPosition(int position, int[] nums) {
        if (position >= nums.length - 1) {
            return true;
        }

        int furthestJump = nums[position];
        // Iterate backwards from the furthest jump for a slight optimization
        // as longer jumps are more likely to reach the end faster.
        for (int jump = furthestJump; jump >= 1; jump--) {
            if (canJumpFromPosition(position + jump, nums)) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Define a recursive function `canJumpFromPosition(position, nums)`.
- If `position` is the last index, return `true`.
- Calculate the furthest reachable index from `position`: `furthestJump = position + nums[position]`.
- Iterate from `position + 1` to `furthestJump`.
- For each `nextPosition`, recursively call `canJumpFromPosition(nextPosition, nums)`.
- If the recursive call returns `true`, return `true`.
- If the loop finishes without finding a path, return `false`.
- The initial call is `canJumpFromPosition(0, nums)`.

## Dynamic Programming (Bottom-Up)
This approach improves upon backtracking by using dynamic programming to avoid re-computing results for the same subproblems. We use an array, let's call it `dp`, to store whether the last index is reachable from each index `i`. We solve the problem iteratively, starting from the end of the array and working our way backward.
**Time:** O(n^2) · **Space:** O(n)
**Pros:** Guarantees a solution without timeouts for larger inputs compared to backtracking.; Systematic way to solve the problem by breaking it down into subproblems.
**Cons:** Time complexity of O(n^2) is not optimal.; Requires O(n) extra space for the DP table.
### Explanation
We create a boolean array `dp` of the same size as `nums`. `dp[i]` will be `true` if the last index is reachable from index `i`, and `false` otherwise.

*   **Initialization**: We know that the last index is reachable from itself, so we initialize `dp[n-1] = true`. All other `dp` entries are implicitly `false`.

*   **Iteration**: We iterate backward from the second-to-last index (`n-2`) down to the start (`0`). For each index `i`, we want to determine `dp[i]`. An index `i` is 'good' if it can jump to another 'good' index `j`.

*   **Logic**: For each index `i`, we check all the indices `j` it can jump to (i.e., `i < j <= i + nums[i]`). If we find any index `j` for which `dp[j]` is already `true`, it means we can reach the end from `i` (by jumping to `j` first). We then set `dp[i] = true` and can stop checking for this `i`.

*   **Result**: After the loop finishes, the value of `dp[0]` tells us whether the last index is reachable from the starting position.

```java
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[n - 1] = true;

        for (int i = n - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[0];
    }
}
```
### Algorithm
- Create a boolean array `dp` of size `n`, where `n` is the length of `nums`.
- Set `dp[n-1] = true`.
- Iterate `i` from `n-2` down to `0`.
- For each `i`, find the furthest possible jump: `furthestJump = i + nums[i]`.
- Iterate `j` from `i+1` to `min(furthestJump, n-1)`.
- If `dp[j]` is `true`, it means we can reach the end from `i`. Set `dp[i] = true` and break the inner loop.
- After the loops complete, return `dp[0]`.

## Greedy Approach
The most efficient solution uses a greedy strategy. Instead of determining if we can reach the end from the start, we can rephrase the problem: what is the leftmost index from which we can reach the end? We can solve this by iterating backward from the end of the array.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Simple and elegant implementation.
**Cons:** The greedy logic might be less obvious to discover compared to DP or backtracking.
### Explanation
The key insight is to track the leftmost 'good' index. A 'good' index is one from which we can reach the last index.

*   **Initialization**: We start by marking the last index (`n-1`) as our initial leftmost 'good' position, let's call this `lastGoodPosition`.

*   **Iteration**: We then iterate backward through the array, from index `n-2` down to `0`.

*   **Greedy Choice**: At each index `i`, we check if we can reach the current `lastGoodPosition` from `i`. The condition for this is `i + nums[i] >= lastGoodPosition`. If we can, it means that index `i` is now a new, even more-left 'good' position. So, we greedily update `lastGoodPosition = i`.

*   **Result**: We continue this process until we've checked all indices down to `0`. If our final `lastGoodPosition` is `0`, it means the starting index is a 'good' position, and thus we can reach the end. Otherwise, it's impossible.

```java
class Solution {
    public boolean canJump(int[] nums) {
        int lastGoodPosition = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastGoodPosition) {
                lastGoodPosition = i;
            }
        }
        return lastGoodPosition == 0;
    }
}
```
### Algorithm
- Initialize a variable `lastGoodPosition` to `nums.length - 1`.
- Iterate `i` from `nums.length - 2` down to `0`.
- Check if the current position `i` can reach `lastGoodPosition` (i.e., `i + nums[i] >= lastGoodPosition`).
- If it can, update `lastGoodPosition` to `i`.
- After the loop, if `lastGoodPosition` is `0`, return `true`. Otherwise, return `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool CanJump(int[] nums) {
        int mx = 0;
        for (int i = 0; i < nums.Length; ++i) {
            if (mx < i) {
                return false;
            }
            mx = Math.Max(mx, i + nums[i]);
        }
        return true;
    }
}
```

### Java

```java
class Solution {
public
  boolean canJump(int[] nums) {
    int mx = 0;
    for (int i = 0; i < nums.length; ++i) {
      if (mx < i) {
        return false;
      }
      mx = Math.max(mx, i + nums[i]);
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {boolean} */ var canJump = function (
  nums,
) {
  let mx = 0;
  for (let i = 0; i < nums.length; ++i) {
    if (mx < i) {
      return false;
    }
    mx = Math.max(mx, i + nums[i]);
  }
  return true;
};

```

### CPP

```cpp
class Solution {
public:
  bool canJump(vector<int> &nums) {
    int mx = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (mx < i) {
        return false;
      }
      mx = max(mx, i + nums[i]);
    }
    return true;
  }
};

```

### Python

```python
class Solution : def canJump ( self , nums : List [ int ]) -> bool : mx = 0 for i , x in enumerate ( nums ): if mx < i : return False mx = max ( mx , i + x ) return True
```