Skip to main content

19. Jump Game

mediumAsked at Klarna

Decide if you can reach the last index starting from index 0 using each cell's max jump length.

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

Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element represents your maximum jump length from 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. Backtracking

Try every jump length from each index recursively.

Time
O(2^n)
Space
O(n)
function canJump(nums) {
  const go = (i) => {
    if (i >= nums.length - 1) return true;
    for (let s = 1; s <= nums[i]; s++) if (go(i + s)) return true;
    return false;
  };
  return go(0);
}

Tradeoff:

2. Greedy farthest reach

Sweep left to right, tracking the farthest index reachable so far. If you ever stand past the current max reach, you're stuck.

Time
O(n)
Space
O(1)
function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

Tradeoff:

Klarna-specific tips

Klarna BNPL risk engineers love greedy reachability because it maps to whether a delinquent customer can 'jump' back to good standing inside a dunning window; expect them to ask about the proof of correctness.

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 Klarna interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →