0307HardArrayDynamic Programming

Pipeline Pad Hops

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.

An inspection crawler walks a pipeline by hopping between steel pads bolted to the outside of the pipe. pads lists the distance of each pad from the pump house in metres, sorted strictly increasing, and pads[0] is always 0 because the crawler is parked on the first pad.

Hops obey two rules:

The very first hop must cover exactly 1 metre.
If the crawler's previous hop covered k metres, its next hop must cover k - 1, k or k + 1 metres. A hop always moves forward, so its length must be at least 1 metre.

Every hop has to finish on a pad; landing on bare pipe is not allowed, and the crawler may not skip a hop or move backwards.

Return true if the crawler can get from the first pad to the last pad in pads, and false otherwise. Pads in between may be passed over.

Examples

Example 1

Input: pads = [0, 1, 2, 4, 7, 11]
Output: true

Hops of 1, 1, 2, 3 and 4 metres land on pads 1, 2, 4, 7 and 11. The first hop is 1 metre and every later hop is within 1 metre of the one before it.

Example 2

Input: pads = [0, 2]
Output: false

The opening hop has to cover exactly 1 metre, and there is no pad 1 metre along, so the crawler never leaves the first pad.

Example 3

Input: pads = [0, 1, 3, 6, 8]
Output: true

Hops of 1, 2, 3 and 2 metres land on pads 1, 3, 6 and 8. Each hop length is within 1 metre of the previous hop, and the 2-metre finish is one metre shorter than the 3-metre hop before it.

Example 4

Input: pads = [0, 1, 3, 6, 7]
Output: false

Pad 6 can only be entered with a 3-metre hop, after hops of 1 and 2 metres. A 3-metre hop must be followed by one of 2, 3 or 4 metres, which land on bare pipe at 8, 9 and 10, and pad 7 stays out of reach by every other legal sequence too.

Constraints

2 <= pads.length <= 2000
0 <= pads[i] <= 2^31 - 1
pads[0] == 0
pads is sorted in strictly increasing order.

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_reach_last_pad(pads: list[int]) -> bool:

Java

public boolean canReachLastPad(int[] pads)

The intended approach

Time O(n^2)Space O(n^2) for the per-pad sets of hop lengths

A crawler's future depends only on where it is standing and how long its last hop was, so store for each pad the set of hop lengths that can deliver the crawler onto it. Seed the first pad with a previous length of 0, which makes the only legal opening hop 1 metre, then walk the pads in increasing order and push each stored length forward as `k - 1`, `k` and `k + 1`. Because every hop moves forward, a pad is never revisited once it has been processed.

Pythonentry point: can_reach_last_pad

def can_reach_last_pad(pads):
    # Iterative sweep, no recursion, so a 2000-pad input is safe.
    # O(n^2) time: each pad holds at most O(n) distinct hop lengths and each
    # length fans out to 3 candidates. O(n^2) space for those sets.
    target = pads[-1]
    arrivals = {p: set() for p in pads}
    arrivals[pads[0]].add(0)
    for p in pads:
        for k in list(arrivals[p]):
            for step in (k - 1, k, k + 1):
                if step <= 0:
                    continue
                nxt = p + step
                if nxt == target:
                    return True
                if nxt in arrivals:
                    arrivals[nxt].add(step)
    return False

The obvious version

Search outward from the parked crawler with a worklist of (pad, last hop length) states, expanding every legal hop and stopping when the last pad shows up.

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_reach_last_pad(pads):
    target = pads[-1]
    pad_set = set(pads)
    seen = set()
    stack = [(pads[0], 0)]
    while stack:
        pos, k = stack.pop()
        if pos == target:
            return True
        for step in (k - 1, k, k + 1):
            if step <= 0:
                continue
            nxt = pos + step
            if nxt in pad_set and (nxt, step) not in seen:
                seen.add((nxt, step))
                stack.append((nxt, step))
    return False

How this problem was checked

Reference solution executed against 13 test cases — 13 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