Skip to main content

27. Jump Game

mediumAsked at Doordash

Determine if you can traverse an array by jumping up to each cell's value — Doordash uses this greedy reachability pattern when modeling whether a Dasher can cover consecutive delivery zones given variable driving ranges.

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

Problem

You are given an integer array nums. You are initially positioned at the 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
  • Elements represent maximum jump distance, not exact

Examples

Example 1

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

Explanation: Jump 1 to index 1, then 3 to the last index.

Example 2

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

Explanation: Every path leads to index 3 which has value 0; index 4 is unreachable.

Approaches

1. DP bottom-up reachability

Mark each index reachable if any reachable predecessor can reach it. O(n^2) time but illustrates the DP structure clearly.

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

Tradeoff:

2. Greedy max-reach

Track the furthest index reachable so far. For each index up to that frontier, update the furthest reachable. If frontier ever reaches or passes the last index, return true.

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:

Doordash-specific tips

Doordash sometimes frames this as a coverage problem: 'given each zone's max reach in km, can a Dasher chain deliveries to the final zone?' The greedy insight — maintain a rolling maximum reach and bail if you fall behind it — is what they want to hear stated before any code. Follow-ups include Jump Game II (minimum jumps) and the streaming version where zones are revealed one at a time. Mention that the greedy proof relies on 'we never gain by stopping short of our maximum reach' — that kind of reasoning signals senior-level thinking.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →