medium Jump Game

Problem Statement

You are given an array of integers nums. You start at the first index of the array and each element in nums represents the maximum number of steps you can jump forward from that position.

Return true if you can reach the last index, or false otherwise.

Examples

Example 1

• Input: nums = [1, 2, 3, 4, 5]
• Expected Output: true
• Justification: Starting at index 0, you can jump 1 step to index 1. From index 1, you can jump 2 steps to index 3. From index 3, you can jump 1 steps to the last index (4). Therefore, it is possible to reach the end.

Example 2

• Input: nums = [2, 0, 2, 0, 1]
• Expected Output: true
• Justification: Starting at index 0, you can jump 2 steps to index 2. From index 2, you can jump 2 steps to the last index (4). Therefore, it is possible to reach the end.

Example 3

• Input: nums = [1, 0, 1, 0]
• Expected Output: false
• Justification: Starting at index 0, you can jump 1 step to index 1. However, index 1 has a value of 0, which means you cannot move forward from there. Therefore, it is impossible to reach the end.

Constraints:

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 10⁵

Solution

To solve this problem, we will use a greedy approach. The idea is to keep track of the farthest index that can be reached while iterating through the array. If at any point, the current index exceeds the farthest reachable index, then it's not possible to reach the end, and we return false. If we can reach or surpass the last index, we return true. This approach ensures that we only make necessary jumps and keeps the solution efficient.

This greedy method is effective because it continually updates the farthest reachable index, ensuring that we make the optimal choice at each step. By focusing on the maximum reachability, we avoid unnecessary computations and directly assess the feasibility of reaching the last index.

Step-by-Step Algorithm

• Initialize a variable maxReach to 0. This will keep track of the farthest index we can reach.
• Loop through each index i of the array nums:
  • If i exceeds maxReach, return false (since we can't move beyond maxReach).
  • Update maxReach to the maximum of maxReach and i + nums[i].
• If the loop completes, return true (since we can reach or exceed the last index).

Algorithm Walkthrough

Let's walk through the algorithm using the input [2, 0, 2, 0, 1]:

• Initialize maxReach to 0.
• At index 0:
  • nums[0] is 2.
  • Check if 0 > maxReach (0). This is false.
  • Update maxReach to max(0, 0 + 2) = 2.
• At index 1:
  • nums[1] is 0.
  • Check if 1 > maxReach (2). This is false.
  • maxReach remains 2 since max(2, 1 + 0) = 2.
• At index 2:
  • nums[2] is 2.
  • Check if 2 > maxReach (2). This is false.
  • Update maxReach to max(2, 2 + 2) = 4.
• At index 3:
  • nums[3] is 0.
  • Check if 3 > maxReach (4). This is false.
  • maxReach remains 4 since max(4, 3 + 0) = 4.
• At index 4:
  • nums[4] is 1.
  • Check if 4 > maxReach (4). This is false.
  • Update maxReach to max(4, 4 + 1) = 5.

Since maxReach is greater than or equal to the last index (4), we return true.

Code

public class Solution {

  public boolean canJump(int[] nums) {
    // Initialize the maximum reachable index
    int maxReach = 0;
    // Iterate through each index in the array
    for (int i = 0; i < nums.length; i++) {
      // If the current index is greater than maxReach, return false
      if (i > maxReach) {
        return false;
      }
      // Update the maximum reachable index
      maxReach = Math.max(maxReach, i + nums[i]);
    }
    // If we have iterated through the array, return true
    return true;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Example 1
    System.out.println(sol.canJump(new int[] { 1, 2, 3, 4, 5 })); // true
    // Example 2
    System.out.println(sol.canJump(new int[] { 2, 0, 2, 0, 1 })); // true
    // Example 3
    System.out.println(sol.canJump(new int[] { 1, 0, 1, 0 })); // false
  }
}

Complexity Analysis

• Time Complexity: , where n is the length of the array nums. We only traverse the array once.
• Space Complexity: . We only use a single variable maxReach to store the maximum reachable index, which requires constant space.

Pattern Transfer — GREEDY FARTHEST-REACH (Jump I)

Pattern family: greedy farthest-reach for jump games.

Template (boolean reachability):

maxReach = 0
for i in 0..n-1:
  if i > maxReach: return false
  maxReach = max(maxReach, i + nums[i])
return true

Invariant: after processing indices 0..i−1 (and checking i), maxReach is the farthest index reachable from any position we can stand on. If i ≤ maxReach, we can stand at i.

When NOT:

• Min jumps → Jump II (BFS layers / same farthest idea counting layers).
• Jump with cost/fee → DP.
• General graph with weights → shortest path.
• Boolean DP can[i] also works but typically more space / easier to write O(n²).

Complexity: one loop of n iterations, O(1) work each → Θ(n) time, O(1) space.

Edge hand-runs

• [0]: i=0, 0>0 false, maxReach=max(0,0+0)=0, done → true.
• [0,1]: i=0 maxR=0; i=1>0 → false.
• [2,0,0]: maxR grows to 2 → true.
• [1,0,1,0]: i=0 maxR=1; i=1 maxR=1; i=2>1 → false.

Drill: State the Jump II question in one sentence and name the extra variables (end, far, jumps).