Skip to main content

49. Jump Game

mediumAsked at Workday

Given an array of max-jump lengths, determine if you can reach the last index. Workday uses this as a greedy-reasoning test — same shape as 'can a workflow proceed from any starting step given variable hop allowances'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — greedy warmup.

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 start: reachable[i]

DP table marking reachability.

Time
O(n^2)
Space
O(n)
// reachable[0]=true; for each reachable i, mark reachable[i..i+nums[i]]=true

Tradeoff: Quadratic for n=10^4 — fine but greedy is sharper.

2. Greedy max-reach

Track the farthest reachable index. If you ever encounter i > maxReach, fail.

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

Tradeoff: Single pass. Greedy works because at every reachable index we extend max-reach optimally.

Workday-specific tips

Workday wants the greedy proof: at every reachable index i, you can update maxReach optimally (no DP needed). State this before coding — they're testing whether you SEE the greedy invariant.

Common mistakes

  • Iterating past nums.length - 1 — unnecessary.
  • Forgetting the early exit when maxReach >= n - 1.
  • Using maxReach > nums.length - 1 (strictly greater) — fails when the answer lands exactly on the last index.

Follow-up questions

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

  • Jump Game II (LC 45) — minimum number of jumps.
  • Jump Game III (LC 1306) — jump left or right.
  • What if some indices are blocked?

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 greedy work?

If you're at index i and can reach i+k, you've effectively extended your maxReach to i+k. There's no benefit to NOT updating maxReach — only updating it monotonically increases your options.

Why iterate beyond max-reach-already-includes-end?

We can short-circuit. The early-return when maxReach >= n - 1 handles this.

Practice these live with InterviewChamp.AI

Drill Jump Game and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →