Skip to main content

20. Jump Game

mediumAsked at MercadoLibre

Decide whether you can reach the last index starting from the first index with bounded jumps.

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

Problem

You are given an integer array nums. You start at the first index, and each element represents your maximum jump length at that position. Return true if you can reach the last index, otherwise false.

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. Recursion with memo

From each index, try every jump length recursively and memoize whether the end is reachable.

Time
O(n^2)
Space
O(n)
const memo = new Map();
function can(i) {
  if (i >= nums.length - 1) return true;
  if (memo.has(i)) return memo.get(i);
  for (let k = 1; k <= nums[i]; k++) if (can(i + k)) { memo.set(i, true); return true; }
  memo.set(i, false); return false;
}
return can(0);

Tradeoff:

2. Greedy farthest reach

Sweep left to right; if i ever exceeds the farthest reachable index, fail. Otherwise keep extending it.

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:

MercadoLibre-specific tips

MercadoLibre logistics teams love the greedy reach pattern because it mirrors how courier hop-sequences are validated — each hop must stay within fuel range of the next depot.

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

Practice these live with InterviewChamp.AI →