0332MediumStringDynamic ProgrammingSliding WindowPrefix Sum

Pontoon Crossing With A Hop Range

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 temporary walkway across a channel is described by s, one character per pontoon along the line. '0' marks a pontoon that still floats and can be stood on, '1' marks one that has gone under and cannot.

A surveyor starts on pontoon 0, which always floats. From the pontoon at index i the surveyor may hop to the pontoon at index j when all of the following hold:

i + minJump <= j <= i + maxJump,
j is within the walkway, so j <= s.length - 1,
s[j] is '0'.

Hops are always forward and there is no limit on how many are taken.

Return true if the surveyor can arrive at the last pontoon, index s.length - 1, and false if no series of hops gets there.

Examples

Example 1

Input: s = "01000110", minJump = 2, maxJump = 3
Output: true

Hopping 0 -> 2 -> 4 -> 7 uses spans of 2, 2 and 3, and pontoons 2, 4 and 7 all float, so the far side is reached.

Example 2

Input: s = "0010", minJump = 2, maxJump = 2
Output: false

Every hop covers exactly two pontoons, so the only landing from pontoon 0 is pontoon 2, which is under water, and the surveyor is stuck at the start.

Example 3

Input: s = "0110", minJump = 3, maxJump = 3
Output: true

A single hop of three lands directly on pontoon 3, which floats.

Example 4

Input: s = "00001", minJump = 1, maxJump = 2
Output: false

The last pontoon is submerged, so it cannot be stood on and the crossing fails.

Constraints

2 <= s.length <= 10^5
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length

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_channel(deck: str, min_span: int, max_span: int) -> bool:

Java

public boolean canCrossChannel(String deck, int minSpan, int maxSpan)

The intended approach

Time O(n)Space O(n)

Sweep the walkway once and mark each pontoon reachable when it floats and at least one already-reachable pontoon lies in the launch window that ends min_span before it and starts max_span before it. That window shifts by one per step, so a single running count of reachable pontoons inside it replaces re-scanning the range.

Pythonentry point: can_cross_channel

def can_cross_channel(deck, min_span, max_span):
    # Sliding count of usable pontoons in the launch window. Position i can be
    # reached when at least one reachable pontoon sits in [i-max_span, i-min_span].
    # Time O(n). Space O(n).
    n = len(deck)
    if deck[n - 1] != "0":
        return False
    reached = [False] * n
    reached[0] = True
    window = 0
    for i in range(1, n):
        if i >= min_span and reached[i - min_span]:
            window += 1
        if i > max_span and reached[i - max_span - 1]:
            window -= 1
        if window > 0 and deck[i] == "0":
            reached[i] = True
    return reached[n - 1]

The obvious version

Depth-first search from pontoon 0, expanding every legal landing in the range explicitly and marking visits.

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_channel(deck, min_span, max_span):
    n = len(deck)
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        i = stack.pop()
        top = i + max_span
        if top > n - 1:
            top = n - 1
        for j in range(i + min_span, top + 1):
            if not seen[j] and deck[j] == "0":
                seen[j] = True
                stack.append(j)
    return seen[n - 1]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 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