Jump Game

MediumGreedyArrayDynamic Programming
Category: Greedy
Companies that ask this question:
AmazonGoogleFacebookMicrosoftBloomberg

Approach

Jump Game

Problem Statement

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.

Examples

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 <= 10^4
  • 0 <= nums[i] <= 10^5

Approach

Key Insight

Greedy approach is optimal!

Track the farthest position reachable at each step.

  • If we can't reach current position → return false
  • If farthest reaches last index → return true

Solution 1: Greedy (Optimal)

Track maximum reachable position.

Algorithm:

  1. Initialize maxReach = 0
  2. For each position i:
    • If i > maxReach → return false (unreachable)
    • Update maxReach = max(maxReach, i + nums[i])
    • If maxReach >= last index → return true
  3. Return true

Solution 2: Greedy Backwards

Work backwards from end.

Algorithm:

  1. Start with goal = last index
  2. For each position from right to left:
    • If can reach goal from position i:
      • Update goal = i
  3. Return goal == 0

Solution 3: Dynamic Programming

Bottom-up DP (less efficient but works).

Algorithm:

  1. Create dp array: dp[i] = can reach last index from i
  2. dp[n-1] = true (already at last)
  3. For each position from right to left:
    • Try all possible jumps
    • If any jump reaches a true position → dp[i] = true
  4. Return dp[0]

Complexity Analysis

Greedy Solution:

  • Time Complexity: O(n) - single pass
  • Space Complexity: O(1) - only variables

DP Solution:

  • Time Complexity: O(n²) - nested loops
  • Space Complexity: O(n) - DP array

Pattern Recognition

This problem demonstrates:

  • Greedy optimization
  • Range tracking pattern
  • Forward/backward scanning techniques
  • Foundation for Jump Game II
  • Common interview pattern

Solution

java
1class Solution {
2    // Solution 1: Greedy (Forward)
3    public boolean canJump(int[] nums) {
4        int maxReach = 0;
5        int n = nums.length;
6
7        for (int i = 0; i < n; i++) {
8            // If current position is unreachable
9            if (i > maxReach) {
10                return false;
11            }
12
13            // Update maximum reachable position
14            maxReach = Math.max(maxReach, i + nums[i]);
15
16            // If we can reach the last index
17            if (maxReach >= n - 1) {
18                return true;
19            }
20        }
21
22        return true;
23    }
24
25    // Solution 2: Greedy (Backward)
26    public boolean canJumpBackward(int[] nums) {
27        int goal = nums.length - 1;
28
29        // Work backwards
30        for (int i = nums.length - 2; i >= 0; i--) {
31            // If can reach goal from position i
32            if (i + nums[i] >= goal) {
33                goal = i;
34            }
35        }
36
37        return goal == 0;
38    }
39
40    // Solution 3: Greedy (Cleaner)
41    public boolean canJumpClean(int[] nums) {
42        int maxReach = 0;
43
44        for (int i = 0; i < nums.length; i++) {
45            if (i > maxReach) {
46                return false;
47            }
48            maxReach = Math.max(maxReach, i + nums[i]);
49        }
50
51        return true;
52    }
53
54    // Solution 4: Dynamic Programming (Not optimal)
55    public boolean canJumpDP(int[] nums) {
56        int n = nums.length;
57        boolean[] dp = new boolean[n];
58        dp[n - 1] = true;  // Already at last index
59
60        // Work backwards
61        for (int i = n - 2; i >= 0; i--) {
62            // Try all possible jumps from position i
63            int maxJump = Math.min(nums[i], n - 1 - i);
64            for (int j = 1; j <= maxJump; j++) {
65                if (dp[i + j]) {
66                    dp[i] = true;
67                    break;
68                }
69            }
70        }
71
72        return dp[0];
73    }
74}
75
Loading visualizer...