0079MediumArrayDynamic ProgrammingGreedy

Stepping Stone Crossing

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_cross(grips: list[int]) -> bool:

Java

public boolean canCross(int[] grips)

The intended approach

Time O(n)Space O(1)

Track the furthest stone index reachable from anything seen so far. Sweep left to right: if the current index is already beyond that frontier the ranger can never stand here, so the crossing fails; otherwise push the frontier out to i + grips[i]. The moment the frontier covers the last stone the answer is settled, which needs one pass and two integers.

Pythonentry point: can_cross

def can_cross(grips):
    last = len(grips) - 1
    reach = 0
    for i in range(len(grips)):
        if i > reach:
            return False
        if i + grips[i] > reach:
            reach = i + grips[i]
        if reach >= last:
            return True
    return True

The obvious version

Fill a reachability flag per stone: for each stone already marked standable, mark every stone within its rating. Reading the last flag answers the question. O(n^2) in the worst case.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_cross(grips):
    n = len(grips)
    standable = [False] * n
    standable[0] = True
    for i in range(n):
        if not standable[i]:
            continue
        limit = grips[i]
        if limit > n - 1 - i:
            limit = n - 1 - i
        for step in range(1, limit + 1):
            standable[i + step] = True
    return standable[n - 1]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in