Skip to main content

49. Jump Game

mediumAsked at Plaid

Determine if you can reach the last index of an array where each value is your max jump length. Plaid asks this as a greedy-baseline problem before harder reachability questions on retry-graph traversal.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid greedy intro.

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. DP from the back

reach[i] = can we reach the end from i? reach[n-1] = true; reach[i] = OR over j in (i+1..i+nums[i]).

Time
O(n^2)
Space
O(n)
function canJump(nums) {
  const n = nums.length;
  const reach = new Array(n).fill(false);
  reach[n - 1] = true;
  for (let i = n - 2; i >= 0; i--) {
    const farthest = Math.min(i + nums[i], n - 1);
    for (let j = i + 1; j <= farthest; j++) {
      if (reach[j]) { reach[i] = true; break; }
    }
  }
  return reach[0];
}

Tradeoff: Quadratic. Works but slower than greedy.

2. Greedy max-reach

Walk forward, tracking the farthest reachable index. If at any point i > maxReach, we're stuck.

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;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

Tradeoff: Linear time, O(1) space. The early-return on maxReach reaching the end is the key optimization.

Plaid-specific tips

Plaid grades this on whether you spot the greedy approach. Bonus signal: prove correctness — at every step the maxReach grows monotonically; if we can reach i, we can reach i + nums[i]. Connect to retry-graph traversal where each node's value is the max steps until next retry window.

Common mistakes

  • Using BFS — works but overkill.
  • Not bailing on i > maxReach — runs through all 10^4 elements unnecessarily.
  • Off-by-one on the 'reached the end' check.

Follow-up questions

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

  • Jump Game II (LC 45) — minimum number of jumps.
  • Jump Game III (LC 1306) — graph with backward jumps allowed.
  • Stochastic jump with probabilities.

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?

If maxReach >= i, we can stand at i. Since maxReach only grows, the first failure is when maxReach < i — and once stuck, no future position is reachable.

When would greedy fail?

It wouldn't, for this exact problem. Greedy fails on Jump Game II (min jumps) if you naively pick the largest next-step value; that one needs BFS-style level tracking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →