Skip to main content

51. Jump Game

mediumAsked at Ola

Determine if you can reach the last index of an array given max jump lengths at each index.

By Sam K., 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 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 the end

Mark reachable[i] = true if some j<=i can reach the end. O(n^2).

Time
O(n^2)
Space
O(n)
const r = Array(nums.length).fill(false); r[r.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 (r[i+j]) { r[i]=true; break; }
}
return r[0];

Tradeoff:

2. Greedy reach

Track the farthest index reachable; if i ever exceeds it, return false.

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:

Ola-specific tips

Ola favors the greedy frontier; tie it to whether a courier with bounded battery range can complete a chained dispatch from origin to destination.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Ola coding interview questions

See all Ola problems →

Companies that also ask Jump Game