Leap to the Finish Line: can you reach the last index?

An Amazon interviewer draws an array on the whiteboard: [2,3,1,1,4]. "You start at index 0. Each value tells you the maximum you can jump forward. Can you reach the end?" This is Leap to the Finish Line, also known as Jump Game on other platforms. It appears frequently at Amazon, Google, Yahoo, Uber, and DoorDash, and it's a Blind 75 staple. The problem tests whether you recognize that a single greedy variable can replace an expensive search over all possible jump sequences.

TL;DR

Scan left to right, maintaining maxReach: the farthest index reachable from any position seen so far. At each index i, update maxReach = max(maxReach, i + nums[i]). If i ever exceeds maxReach, return false (you're stranded). If maxReach reaches the last index, return true. One pass, O(n) time, O(1) space.

The Problem

Given an integer array nums where you start at index 0, each element represents the maximum number of steps you can jump forward from that position. Return true if you can reach the last index, false otherwise.

canJump([2,3,1,1,4]) => true
canJump([3,2,1,0,4]) => false

For the first example, you can jump from index 0 to 1 (jump 1 of max 2), then from index 1 to 4 (jump 3 of max 3). For the second, every path gets stuck at index 3 where nums[3] = 0.

Why Greedy Works

You might think you need to explore every possible jump sequence, like a BFS or DFS through the array. But the question only asks "can you reach the end?", not "what's the shortest path?" That makes this a reachability problem, and reachability has a clean greedy solution.

The key observation: if you can reach index i, you can reach every index from 0 to i. The reach only grows (or stays the same) as you move right. So you just need one variable tracking the farthest point you've confirmed is reachable. If that variable ever covers the last index, you're done.

The Algorithm

1. Initialize maxReach = 0.
2. For each index i from 0 to n-1:
   • If i > maxReach, return false (unreachable position).
   • Update maxReach = max(maxReach, i + nums[i]).
   • If maxReach >= n - 1, return true (end is reachable).
3. Return false if the loop completes without reaching the end.

Reachable: [2,3,1,1,4]

At index 0, nums[0] = 2 so maxReach becomes 2. At index 1, nums[1] = 3 so maxReach becomes max(2, 1+3) = 4. Since 4 >= 4 (last index), we return true. We never even need to check indices 2, 3, or 4.

Unreachable: [3,2,1,0,4]

Everything looks fine through index 3. But at index 3, nums[3] = 0, and maxReach stays at 3. When we reach index 4, i (4) > maxReach (3), so we return false. The zero at index 3 creates an impassable barrier.

Edge Cases

Clearing Zeroes

A zero doesn't always mean you're stuck. If an earlier jump can clear the zero, it's irrelevant.

In [2,0,0], nums[0] = 2 gives maxReach = 2, which already covers the last index. The zeroes at indices 1 and 2 don't matter because you can jump directly from index 0 to index 2.

Single Element

With [0], you start at the last index. The algorithm returns true immediately since maxReach (0) >= n-1 (0).

Diminishing Jumps

In [5,4,3,2,1,0,0], each jump value decreases by 1. Index 0 reaches index 5 (maxReach = 5), but the last index is 6. No later position extends the reach beyond 5, so the array is unreachable. The decreasing pattern means every position adds zero net progress.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false;
      }
      maxReach = Math.max(maxReach, i + nums[i]);
      if (maxReach >= nums.length - 1) {
        return true;
      }
    }
    return false;
  }
}

The implementation is compact. A few things to note:

• The i > maxReach check must come before the update. If you update first, you might extend reach using an unreachable position.
• The early return true when maxReach >= nums.length - 1 avoids unnecessary iterations. In the best case, the algorithm exits after checking just one or two elements.
• The final return false handles edge cases where the loop completes without either condition triggering (though with correct logic, this only fires for empty arrays).

Complexity Analysis

Time: O(n)

One pass through the array. Each index is visited at most once. The early exit can make this faster in practice, but the worst case is still O(n).

Space: O(1)

A single integer variable maxReach. No arrays, stacks, or recursion.

Alternative Approaches

Dynamic Programming (O(n^2) time, O(n) space)

Create a boolean array dp where dp[i] means index i is reachable. Set dp[0] = true. For each reachable index, mark all positions within jump range as reachable. Check dp[n-1]. This works but is slower and uses more space than greedy.

Backward Greedy (O(n) time, O(1) space)

Track the leftmost "good" index (one that can reach the end). Start from the second-to-last index and work backward. If i + nums[i] >= lastGood, update lastGood = i. At the end, check if lastGood == 0. Same complexity as the forward approach.

Common Mistakes

• Not checking reachability before updating. If you compute maxReach = max(maxReach, i + nums[i]) before checking i > maxReach, you allow jumps from positions you can't actually reach. The order matters.

• Returning true when maxReach > 0 at the end. A positive maxReach doesn't mean the end is reachable. You must check maxReach >= n - 1.

• Ignoring arrays with a single element. [0] should return true because you're already at the last index. Don't assume nums[0] > 0 is required.

• Confusing max jump with exact jump. nums[i] = 3 means you can jump 1, 2, or 3 steps, not exactly 3. The max in the problem description is critical.

Interview Tips

• Name the strategy. "This is a greedy reachability problem. I'll track the farthest index reachable from any position I've passed."
• Draw the barrier. For [3,2,1,0,4], sketch how the zero at index 3 creates a wall. Show that no earlier index can jump past it.
• Mention the DP alternative. "A DP solution would use O(n) space and O(n^2) time. The greedy approach improves both to O(1) space and O(n) time because reach is monotonically non-decreasing."
• Discuss Jump Game II. If the interviewer asks "what if I want the minimum number of jumps?", explain that you'd track jump boundaries (the range of indices reachable in the current jump count) and increment a counter each time you move past the current boundary.

Related Problems

Jump Game is the entry point for a family of reachability and jumping problems:

• Jump Game II - Find the minimum number of jumps to reach the end. Requires tracking jump boundaries in addition to maxReach.
• Jump Game III - You can jump forward or backward by exactly nums[i]. Uses BFS since the reach is no longer monotonic.
• Jump Game IV - Jump to adjacent indices or any index with the same value. Graph traversal with BFS.
• Frog Jump - Variable jump distances based on previous jump. Requires a set or map to track reachable states.

The greedy maxReach pattern from this problem is unique to Jump Game I because reach only grows. The sequels introduce bidirectional movement or state-dependent jumps that break the greedy property.

Ready to practice greedy problems? Firecode sequences related problems using spaced repetition so you build intuition for reachability patterns over time. Over 50,000 engineers have used it to prepare for interviews at top companies like Amazon, Google, and Uber.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def can_jump(self, nums: List[int]) -> bool:
        max_reachable = 0
        for i, jump in enumerate(nums):
            if i > max_reachable:
                return False
            max_reachable = max(max_reachable, i + jump)
            if max_reachable >= len(nums) - 1:
                return True
        return False

JavaScript

class Solution {
  canJump(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false;
      }
      maxReach = Math.max(maxReach, i + nums[i]);
      if (maxReach >= nums.length - 1) {
        return true;
      }
    }
    return false;
  }
}

TypeScript

class Solution {
  canJump(nums: number[]): boolean {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false;
      }
      maxReach = Math.max(maxReach, i + nums[i]);
      if (maxReach >= nums.length - 1) {
        return true;
      }
    }
    return false;
  }
}

C++

#include <algorithm>
#include <vector>

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

Go

package solution

type Solution struct{}

func (s *Solution) CanJump(nums []int) bool {
    maxReach := 0
    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
        if maxReach >= len(nums)-1 {
            return true
        }
    }
    return false
}

Scala

class Solution {
  def canJump(nums: Array[Int]): Boolean = {
    var maxReach = 0
    for (i <- nums.indices) {
      if (i > maxReach) return false
      maxReach = math.max(maxReach, i + nums(i))
      if (maxReach >= nums.length - 1) return true
    }
    false
  }
}

Kotlin

class Solution {
    fun canJump(nums: IntArray): Boolean {
        var maxReach = 0
        for (i in nums.indices) {
            if (i > maxReach) {
                return false
            }
            maxReach = maxOf(maxReach, i + nums[i])
            if (maxReach >= nums.lastIndex) {
                return true
            }
        }
        return false
    }
}

Swift

import Foundation

class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var maxReach = 0
        for i in nums.indices {
            if i > maxReach {
                return false
            }
            maxReach = max(maxReach, i + nums[i])
            if maxReach >= nums.count - 1 {
                return true
            }
        }
        return false
    }
}

Rust

impl Solution {
    pub fn can_jump(&self, nums: Vec<i32>) -> bool {
        let mut max_reach = 0;
        for i in 0..nums.len() {
            if i > max_reach {
                return false;
            }
            max_reach = max_reach.max(i + nums[i] as usize);
            if max_reach >= nums.len() - 1 {
                return true;
            }
        }
        false
    }
}

C#

public class Solution {
    public bool CanJump(int[] nums) {
        var maxReach = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (maxReach >= nums.Length - 1) {
                return true;
            }
        }
        return false;
    }
}

Dart

import 'dart:math';

class Solution {
  bool canJump(List<int> nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false;
      }
      maxReach = max(maxReach, i + nums[i]);
      if (maxReach >= nums.length - 1) {
        return true;
      }
    }
    return false;
  }
}

PHP

class Solution {
    public function canJump(array $nums): bool {
        $maxReach = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($i > $maxReach) {
                return false;
            }
            $maxReach = max($maxReach, $i + $nums[$i]);
            if ($maxReach >= count($nums) - 1) {
                return true;
            }
        }
        return false;
    }
}

Ruby

class Solution
  def can_jump(nums)
    max_reach = 0
    nums.each_with_index do |jump, i|
      if i > max_reach
        return false
      end
      max_reach = [max_reach, i + jump].max
      if max_reach >= nums.length - 1
        return true
      end
    end
    false
  end
end