~/problems / Greedy

Jump Game

easy ~15 min

Write can_jump(nums: list[int]) -> bool.

You start at index 0. From index i you may jump forward by any distance from 1 to nums[i], so nums[i] == 0 means you are stuck there. Return True if the last index can be reached.

Example: [2, 0, 3, 0, 1] gives True (0 → 2 → 4). [1, 2, 1, 0, 3] gives False: every route lands on index 3, which has value 0. [0] gives True, since you already stand on the last index.

Constraints: 1 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^5.

Marking every index each position can jump to is O(n²) in the worst case and fails the large test; aim for O(n).

Show hint

you don't need to know how you reach an index, only how far right you could possibly get using the indices seen so far.

Topic: Greedy with sorting. Sort, then take the locally best choice; prove it with an exchange argument.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc