DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Jump Game

mediumGreedy Must-doMicrosoft SRE

Problem statement

You stand on index 0 of an array nums of non-negative integers. From index i you may jump forward by any distance from 1 up to nums[i] (a value of 0 means you cannot move from there).

Return true if you can reach the last index, and false otherwise.

Examples

Example 1

Input: nums = [1, 2, 0, 1, 4]

Output: true

Explanation: Jump 0 -> 1, then 1 -> 3 (a jump of 2 skips the zero), then 3 -> 4.

Example 2

Input: nums = [2, 1, 0, 0, 3]

Output: false

Explanation: From index 0 you can reach at most index 2, from index 1 also index 2, and index 2 has a 0. Index 3 and beyond are out of reach.

Hints

Approach

Greedy furthest reach. Reachable indices always form one unbroken prefix (if you can reach index k, you can reach every index before it), so a single number describes them: the furthest index reached so far.

  1. furthest = 0.
  2. Scan i from left to right. If i > furthest, index i cannot be reached, so return false.
  3. Otherwise update furthest = max(furthest, i + nums[i]). If it reaches the last index, return true early.

One pass, two variables.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def canJump(self, nums: list[int]) -> bool:
furthest = 0
last = len(nums) - 1
for i, step in enumerate(nums):
if i > furthest: # a gap we cannot cross
return False
furthest = max(furthest, i + step)
if furthest >= last:
return True
return True

Follow-up questions

  • Return the minimum number of jumps needed (that is Jump Game II).
  • Jumps can go backwards as well as forwards. What approach do you need now?

Frequently asked questions

Because the set of reachable indices is always a contiguous prefix. Any index below the furthest reach is reachable by jumping shorter from wherever produced that reach. So the only thing that matters is whether the prefix ever stops growing before the end.

The furthest-reach sweep is the same reasoning as checking coverage: can a sequence of relays, each with a range, carry a signal to the end of a line? Do a set of maintenance windows or on-call shifts leave any gap? It also tests whether you can spot that a DP is overkill and a single running maximum is enough.