Show problems as
Classic problem #1703HardArrayGreedySliding WindowPrefix Sum

Minimum Adjacent Swaps for K Consecutive Ones

Real-world version: Coupling Loaded Cars Together
Tracked in this browser only
Read Minimum Adjacent Swaps for K Consecutive Ones on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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

Python
def min_couplings(cars: list[int], k: int) -> int:
Java
public int minCouplings(int[] cars, int k)

More on the same topics