Skip to main content

49. Jump Game

mediumAsked at Vercel

Given an array of max-jump lengths from each index, decide if you can reach the last index. Vercel asks this for the greedy 'max reachable so far' pattern — same shape as their step-by-step deploy-graph reachability checks.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; greedy expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

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.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Examples

Example 1

Input
nums = [2,3,1,1,4]
Output
true

Example 2

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

Approaches

1. Recursive top-down with memo

From each index, try every jump length 1..nums[i]; memoize.

Time
O(n^2)
Space
O(n)
function canJump(nums) {
  const memo = new Array(nums.length).fill(0);
  function go(i) {
    if (i >= nums.length - 1) return true;
    if (memo[i] !== 0) return memo[i] === 1;
    for (let step = 1; step <= nums[i]; step++) {
      if (go(i + step)) { memo[i] = 1; return true; }
    }
    memo[i] = -1;
    return false;
  }
  return go(0);
}

Tradeoff: O(n^2) and uses stack. The greedy version is O(n) and O(1).

2. Greedy max-reach (optimal)

Walk left to right. Maintain max-reachable index. If current index > max, return false. Else update max = max(max, i + nums[i]).

Time
O(n)
Space
O(1)
function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    if (i + nums[i] > maxReach) maxReach = i + nums[i];
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

Tradeoff: O(n), O(1). The greedy works because we only care about REACHABILITY — once any path reaches index i, we can use the best jump from there. Early exit once maxReach covers the end.

Vercel-specific tips

Vercel grades for the greedy insight. Bonus signal: explaining why DP isn't needed (any reachable index gives access to the same future jumps; we don't need to track HOW we got there). Also flag early exit when maxReach >= last index.

Common mistakes

  • Using DP when greedy suffices — solves the problem but slower and more code.
  • Iterating past i > maxReach — returns wrong answer because future updates can't help.
  • Confusing max-reach with current position — they're different.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Jump Game II (LC 45) — minimum number of jumps.
  • Jump Game III (LC 1306) — can jump +/- nums[i].
  • Reverse jump — can you reach index 0 from any index?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does greedy work?

Because reachability is monotonic: if index i is reachable, so is any j < i. The 'max reachable so far' captures all useful state — we don't need DP over individual paths.

When does greedy fail?

When the cost of paths matters (Jump Game II asks for MIN jumps, which needs a slightly different greedy or BFS). Pure reachability is the easiest variant.

Practice these live with InterviewChamp.AI

Drill Jump Game and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →