Skip to main content

90. Jump Game II

hardAsked at Plaid

Find the minimum number of jumps to reach the last index. Plaid asks this as a BFS-as-greedy problem — the same shape as finding the minimum number of API-hops to reach a target endpoint across their bank-rail graph.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III hard greedy.
  • LeetCode Discuss (2026)— Plaid min-hop variant.

Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach n - 1. The test cases are generated such that you can reach n - 1.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Examples

Example 1

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

Example 2

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

Approaches

1. DP from the back

dp[i] = min jumps from i to end. O(n^2).

Time
O(n^2)
Space
O(n)
// Quadratic. Don't ship for n=10^4.

Tradeoff: Slow.

2. BFS-style greedy

Treat each jump as a BFS level. Track currentEnd (farthest reachable in this jump) and farthest (farthest reachable considering one more step from anywhere in the current range). When i reaches currentEnd, take a jump and reset currentEnd = farthest.

Time
O(n)
Space
O(1)
function jump(nums) {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Tradeoff: Linear. The trick: BFS levels are encoded as 'when i crosses currentEnd, count one jump and update.'

Plaid-specific tips

Plaid grades this on whether you recognize BFS-as-greedy. Bonus signal: explain why we stop at n-1 (not n) — we never need to jump from the last index because we're already there. Connect to min-hop API routing where each hop is a network round-trip.

Common mistakes

  • Looping to nums.length instead of nums.length - 1 — counts an extra jump.
  • Forgetting to update currentEnd to farthest, not to currentEnd + something.
  • Trying naive greedy (always jump to max reachable) — fails on cases like [2, 3, 1, 1, 4].

Follow-up questions

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

  • Can we reach the end (LC 55) — the simpler boolean version.
  • Minimum jumps with backward moves allowed.
  • Weighted jump game (each jump has a cost).

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 this encode BFS?

Each 'level' is the set of positions reachable in k jumps. currentEnd is the right edge of the current level; farthest is the right edge of level k+1.

Why stop at n-1?

We only need to *reach* the last index, not jump from it. The loop ending at n-2 ensures we count the final jump but no extra.

Practice these live with InterviewChamp.AI

Drill Jump Game II 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 →