0445MediumArrayStackSortingMonotonic Stack

Rafts Reaching the Canal Lock

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.

Loaded barges work their way along a single-file canal reach toward a lock. The lock stands lock metres from the top of the reach. Barge i starts starts[i] metres from the top of the reach and covers paces[i] metres a minute in clear water. No two barges start from the same distance, and all of them are under way at minute 0.

The reach is too narrow to pass. If a barge closes right up on the barge ahead, it has to throttle back and hold that barge's pace from then on, and the two carry on to the lock together as a single raft; a raft holds the pace of the slowest barge in it, and rafts join other rafts the same way. Barges that reach the lock at exactly the same minute count as one raft, whether or not they were travelling together before that.

Return how many rafts pass the lock gate.

Examples

Example 1

Input: lock = 12, starts = [0, 6], paces = [2, 1]
Output: 1

The barge starting 6 metres along needs 6 minutes to reach the lock and the one starting at the head needs 6 minutes as well, so they get there together and are counted once.

Example 2

Input: lock = 50, starts = [35, 5, 20], paces = [1, 10, 3]
Output: 1

The barge at 35 metres reaches the lock 15 minutes in. The other two are held up behind it on the way and pass the lock gate with it.

Example 3

Input: lock = 30, starts = [0, 5, 10, 25], paces = [2, 3, 1, 5]
Output: 2

The barge at 25 metres arrives after 1 minute on its own. The barge at 10 metres arrives 20 minutes in, with the barges from 5 and 0 metres held behind it.

Example 4

Input: lock = 100, starts = [0, 10, 20], paces = [5, 5, 5]
Output: 3

All three barges hold the same pace, so none of them ever closes on the one in front and each reaches the lock on its own.

Constraints

n == starts.length == paces.length
1 <= n <= 10^5
0 < lock <= 10^6
0 <= starts[i] < lock
All values in starts are distinct.
0 < paces[i] <= 10^6

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 raft_count(lock: int, starts: list[int], paces: list[int]) -> int:

Java

public int raftCount(int lock, int[] starts, int[] paces)

The intended approach

Time O(n log n): ordering the barges dominates, then one pass with constant work per barge.Space O(n) for the ordering.

Take the barges in order of how close they start to the lock, nearest first, and carry the arrival time of the raft currently in front. A barge whose own unhindered arrival time is later than that time cannot be held up by anything ahead, so it opens a new raft and becomes the time to beat; any barge that would arrive sooner, or at the very same moment, finishes inside the raft ahead. Arrival times are held as a distance-and-pace pair and compared by cross-multiplying, so no division or rounding enters into it.

Pythonentry point: raft_count

def raft_count(lock, starts, paces):
    # Work from the barge nearest the lock backwards. The barge in front of a
    # group fixes when the group gets there, so keep the arrival time of the group
    # currently in front: a barge whose own unhindered arrival is later than that
    # can never be caught up with by the group ahead and so leads a new raft,
    # while any barge that would arrive sooner or at the same moment ends up
    # travelling in the raft ahead. Arrival times are compared as exact fractions
    # by cross-multiplying, which keeps the comparison free of rounding.
    # O(n log n) time for the ordering, O(n) space for the order.
    order = sorted(range(len(starts)), key=lambda i: starts[i], reverse=True)
    rafts = 0
    lead_left = 0
    lead_pace = 0
    for i in order:
        left = lock - starts[i]
        pace = paces[i]
        if rafts == 0 or left * lead_pace > lead_left * pace:
            rafts += 1
            lead_left = left
            lead_pace = pace
    return rafts

The obvious version

For each barge in turn, scan every other barge to find the latest unhindered arrival time among those that start closer to the lock, and count the barge as a raft leader when its own arrival time is strictly later than all of those. Times are kept as exact fractions.

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_raft_count(lock, starts, paces):
    from fractions import Fraction
    total = len(starts)
    rafts = 0
    for i in range(total):
        mine = Fraction(lock - starts[i], paces[i])
        ahead = None
        for j in range(total):
            if starts[j] > starts[i]:
                theirs = Fraction(lock - starts[j], paces[j])
                if ahead is None or theirs > ahead:
                    ahead = theirs
        if ahead is None or mine > ahead:
            rafts += 1
    return rafts

How this problem was checked

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