Skip to main content

15. Jump Game

mediumAsked at Autodesk

Decide if you can reach the last index given max jump lengths at each position.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array nums where each element represents your maximum jump length at that position. Starting at index 0, determine if you can reach the last index of the array.

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. DFS / memoized recursion

From every position try each jump length and memoize reachability.

Time
O(n^2)
Space
O(n)
function canReach(i){ if (i>=n-1) return true; if (memo[i]!==undefined) return memo[i]; for (let k=1;k<=nums[i];k++) if (canReach(i+k)) return memo[i]=true; return memo[i]=false; }

Tradeoff:

2. Greedy max reach

Walk left to right tracking the farthest reachable index. If you ever stand past the current reach, 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:

Autodesk-specific tips

Greedy reach problems echo Autodesk's pathfinding heuristics used in robot/CNC toolpath planners.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Autodesk coding interview questions

See all Autodesk problems →

Companies that also ask Jump Game