Show problems as
Classic problem #55MediumArrayDynamic ProgrammingGreedy

Jump Game

Real-world version: Stepping Stone Crossing
Tracked in this browser only
Read Jump Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ranger crosses a creek on a line of stepping stones, numbered from the near bank. Stone i carries a grip rating grips[i]: standing on that stone, the ranger can hop forward by any whole number of stones from 1 up to grips[i]. A rating of 0 means the stone gives no purchase at all, so no hop can start from it.

The ranger starts on stone 0 and wants to end up standing on the last stone. Return true if some sequence of hops gets there and false if none does. Hops never go backwards, and a hop that would carry the ranger past the last stone is not useful, so the last stone has to be landed on exactly.

A line of one stone means the ranger is already standing on the last stone, whatever that stone's rating is.

Examples

Example 1

Input
grips = [2, 3, 0, 1, 4]
Output
true

A single hop onto stone 1 buys a rating of 3, which is enough to land on the last stone; hopping two stones first would strand the ranger on the slick stone 2.

Example 2

Input
grips = [3, 1, 0, 0, 5]
Output
false

The best the ranger can do is stand on stone 3, and both stone 2 and stone 3 give no purchase, so the far side stays out of range.

Example 3

Input
grips = [0]
Output
true

The near bank stone is also the last stone, so the crossing is already done and the rating is irrelevant.

Constraints

  • 1 <= grips.length <= 10^4
  • 0 <= grips[i] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_cross(grips: list[int]) -> bool:
Java
public boolean canCross(int[] grips)

More on the same topics