Skip to main content

51. Jump Game

mediumAsked at Snowflake

Decide whether you can reach the last index. Snowflake asks this to test greedy reasoning — the same shape as deciding whether a partial plan can still be completed within a cost budget.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up plan-feasibility discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad onsites.

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 end

dp[i] = can reach end from i. dp[n-1] = true. dp[i] = any j in [i+1, i+nums[i]] has dp[j].

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

Tradeoff: Quadratic. Mention as the obvious DP approach.

2. Greedy max-reach (optimal)

Walk left-to-right, tracking maxReach. If i > maxReach, you're stuck. Otherwise update maxReach = max(maxReach, 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. The greedy invariant: at index i, the best we could possibly reach is maxReach. If maxReach falls short, no future move can rescue us.

Snowflake-specific tips

Snowflake interviewers grade this on the greedy invariant. Bonus signal: connect to plan feasibility — given a partial plan's elapsed cost and remaining-budget, decide whether any continuation can fit. The greedy 'best possible reach' mirrors the planner's 'lower bound on remaining cost'.

Common mistakes

  • Returning false when maxReach == i (i.e., a 0 at index i) — only false when i > maxReach.
  • Walking right-to-left without a clear invariant — DP works but is harder.
  • Stopping the loop too early (e.g., at i == maxReach instead of i > maxReach).

Follow-up questions

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

  • Jump Game II (LC 45) — minimum number of jumps.
  • Jump Game III (LC 1306) — reach a target value.
  • How does the planner prune infeasible partial plans?

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 greedy and not DP?

The greedy invariant is provably correct (proof: induction on i — at i we can reach somewhere in [i, maxReach], so any reachable point also has a known maxReach). It's also linear vs DP's quadratic.

What's the connection to plan feasibility?

Both decide whether a path through state space can reach a target while respecting bounds. Snowflake's planner prunes plans whose lower-bound cost already exceeds budget.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →