Skip to main content

51. Jump Game

mediumAsked at Reddit

Determine if you can reach the last index of an array starting from index 0. Reddit asks this to test greedy intuition — the same forward-reachability check used in their dependency-resolution for ad-pixel firing order.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common greedy DP.

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 — reachable[i] from any j < i

reachable[i] true if any j < i with reachable[j] and j + nums[j] >= i.

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

Tradeoff: Quadratic. Mention as the DP-thinking version before jumping to greedy.

2. Greedy max-reach (optimal)

Track furthest index reachable. Walk forward; if i > furthest, return false. Update furthest = max(furthest, 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;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

Tradeoff: Linear time, O(1) space. The greedy max-reach captures the only state that matters.

Reddit-specific tips

Reddit interviewers grade on the leap from DP to greedy. State the invariant: 'maxReach is the furthest index we can land on; if i > maxReach, we're stuck'. Bonus signal: connect to ad-pixel dependency chains.

Common mistakes

  • Returning false at the first 0 (a 0 is only fatal if you can't jump over it).
  • Updating maxReach inside an if (must always check).
  • Early-exit on i === n - 1 missed by off-by-one.

Follow-up questions

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

  • Jump Game II (LC 45) — minimum jumps.
  • Jump Game III (LC 1306) — BFS variant.
  • Frog jump (LC 403).

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?

Within maxReach, every index is reachable. The only state that matters is the maximum index reachable so far.

Does greedy give the path?

No — only feasibility. For the actual jumps, see Jump Game II (LC 45).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →