0697HardArrayGreedySliding WindowPrefix Sum

Coupling Loaded Cars Together

Tracked in this browser only

Trains the technique from

LeetCode 1703Minimum Adjacent Swaps for K Consecutive Ones

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 siding holds a line of rail cars, described by cars: cars[i] is 1 when position i holds a loaded car and 0 when it holds an empty one. Every position holds a car, so the line never has gaps.

One shunt exchanges the cars in two neighbouring positions.

Return the least number of shunts after which some k consecutive positions of the siding all hold loaded cars. If the siding already has k loaded cars standing together, the answer is 0.

Examples

Example 1

Input: cars = [1, 0, 0, 1, 1, 1], k = 3
Output: 0

Positions 3, 4 and 5 already hold three loaded cars standing together, so nothing has to be shunted.

Example 2

Input: cars = [1, 0, 1], k = 2
Output: 1

Exchanging the cars in positions 1 and 2 leaves loaded cars in positions 0 and 1, which is two of them standing together after one shunt.

Example 3

Input: cars = [1, 0, 1, 0, 1, 0, 1], k = 4
Output: 4

Move the loaded car at position 2 one place right, the one at position 6 one place left, then the one at position 0 two places right. That is 4 shunts and it leaves loaded cars in positions 2, 3, 4 and 5.

Constraints

1 <= cars.length <= 10^5
0 <= cars[i] <= 1
1 <= k <= 10^5
Each entry of cars is 0 or 1, and k is at most the number of loaded cars.

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 min_couplings(cars: list[int], k: int) -> int:

Java

public int minCouplings(int[] cars, int k)

The intended approach

Time O(n) for a siding of n positions: one scan to find the loaded cars, one over the windows.Space O(m) for the m loaded car positions and their prefix sums.

Only the loaded cars matter, so list their positions and subtract each one's rank in that list. Wanting k loaded cars in consecutive positions then becomes wanting k of those shifted values to agree, and the shunts needed are the total distance from the shifted values to whatever value they agree on. Sliding a window of k over the shifted values and settling each window on its middle entry, with prefix sums giving the two one-sided distance totals in constant time, leaves one pass over the loaded cars.

Pythonentry point: min_couplings

def min_couplings(cars, k):
    spots = [i for i, v in enumerate(cars) if v == 1]
    m = len(spots)
    # subtracting the rank turns "k loaded cars in consecutive positions" into
    # "k equal values", so the cost of a window is the total distance to one
    # chosen value
    shifted = [spots[j] - j for j in range(m)]
    running = [0] * (m + 1)
    for j in range(m):
        running[j + 1] = running[j] + shifted[j]
    best = None
    for lo in range(m - k + 1):
        hi = lo + k - 1
        mid = lo + k // 2
        anchor = shifted[mid]
        left = anchor * (mid - lo) - (running[mid] - running[lo])
        right = (running[hi + 1] - running[mid + 1]) - anchor * (hi - mid)
        cost = left + right
        if best is None or cost < best:
            best = cost
    return best

The obvious version

Explore the sidings themselves in order of shunts used: from each siding reached so far, generate every siding one exchange away, and stop the first time a siding has k loaded cars standing together. The number of sidings grows exponentially, so this is only usable on very short lines.

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_min_couplings(cars, k):
    start = tuple(cars)
    n = len(start)

    def reached(state):
        run = 0
        for v in state:
            run = run + 1 if v == 1 else 0
            if run >= k:
                return True
        return False

    if reached(start):
        return 0
    seen = {start}
    frontier = [start]
    shunts = 0
    while frontier:
        shunts += 1
        nxt = []
        for cur in frontier:
            for i in range(n - 1):
                if cur[i] == cur[i + 1]:
                    continue
                swapped = list(cur)
                swapped[i], swapped[i + 1] = swapped[i + 1], swapped[i]
                cand = tuple(swapped)
                if cand in seen:
                    continue
                if reached(cand):
                    return shunts
                seen.add(cand)
                nxt.append(cand)
        frontier = nxt
    return -1

How this problem was checked

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