0

Minimum adjacent swaps to group red balls

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Minimum adjacent swaps to group red balls

Companies: Microsoft

Difficulty: Medium

Problem statement

A row of balls is given as a string balls. Each character is 'R' (red) or 'W' (white).

In one move you may swap two neighbouring balls. Return the minimum number of moves needed so that all red balls form one contiguous block (the block may be anywhere in the row). If the reds are already contiguous, or there are fewer than two reds, return 0.

Some versions add: if the answer is greater than 10^9, return -1.

Constraints

  • 0 <= len(balls) <= 10^5
  • balls contains only 'R' and 'W'

Example 1

Input:  balls = "WRRWWR"
Output: 2

Move the last red ball two places left to get "WRRRWW".

Example 2

Input:  balls = "WWRWWWRWR"
Output: 4

Keep the red at index 6 in place. Move the red at index 2 right by 3 and the red at index 8 left by 1, giving reds at indices 5, 6, 7.

Approach

Key observation. Adjacent swaps between two red balls change nothing, so
red balls never need to pass each other. The reds keep their relative order:
the i-th red (0-indexed, left to right) ends up at slot s + i of the final
block that starts at s. Moving one ball one step costs one swap (it swaps
with a white neighbour), and the moves of different reds never interfere when
they keep their order. So the cost of a block start s is:

cost(s) = sum over i of |p[i] - (s + i)| = sum over i of |q[i] - s|,  q[i] = p[i] - i

where p[i] is the index of the i-th red ball.

Brute force. Try every start s from 0 to n - k and sum the distances:
O(n * k). Fine to mention first; it already uses the key observation.

Optimal. cost(s) is a sum of absolute deviations from s, minimised at a
median of q. Because p is strictly increasing, q is non-decreasing, so
q[k // 2] is a median without sorting. Sum |q[i] - median| in one pass.

Equivalent framing that many candidates use: pick the middle red ball and pull
every other red toward it. The red at distance j slots from the middle in
the final block moves |p[i] - p[mid]| - |i - mid| steps. Both framings give
the same number.

Invariants.

  • q is non-decreasing (each red is at least one position right of the
    previous one).
  • Any median of q gives the same minimum, so the choice of k // 2 for
    even k is safe.
  • No reds or one red: answer 0.

The original online assessment version asks to return -1 when the answer
exceeds 10^9. The code takes an optional cap for that.

Code

from typing import Optional


def min_swaps_to_group(balls: str, target: str = "R", cap: Optional[int] = None) -> int:
    """Minimum adjacent swaps to make every `target` ball contiguous.

    If `cap` is given and the answer exceeds it, return -1.
    """
    positions = [i for i, ch in enumerate(balls) if ch == target]
    k = len(positions)
    if k <= 1:
        return 0

    # q[i] = p[i] - i is non-decreasing, so its middle element is a median.
    median = positions[k // 2] - k // 2

    total = 0
    for i, p in enumerate(positions):
        total += abs((p - i) - median)
        if cap is not None and total > cap:
            return -1
    return total


def min_swaps_brute(balls: str, target: str = "R") -> int:
    """O(n * k) reference: try every start of the final block."""
    positions = [i for i, ch in enumerate(balls) if ch == target]
    k = len(positions)
    if k <= 1:
        return 0
    return min(
        sum(abs(p - (s + i)) for i, p in enumerate(positions))
        for s in range(len(balls) - k + 1)
    )


if __name__ == "__main__":
    assert min_swaps_to_group("WRRWWR") == 2
    assert min_swaps_to_group("RWRWR") == 2
    assert min_swaps_to_group("WWRWWWRWR") == 4
    assert min_swaps_to_group("WWW") == 0
    assert min_swaps_to_group("") == 0
    assert min_swaps_to_group("R") == 0
    assert min_swaps_to_group("RRRWWW") == 0
    assert min_swaps_to_group("RWWWWR") == 4
    assert min_swaps_to_group("RW" * 4, cap=3) == -1
    print("ok")

Complexity

  • Time: O(n) for one pass to collect red positions and one pass over them.
  • Space: O(k) for the positions, where k is the number of red balls. It can
    be made O(1) extra with two passes (count reds, then find the median red
    while scanning) and a running sum.
  • Brute force: O(n * k) time, O(k) space.

Test cases

  • "WRRWWR" -> 2 (block RRR at indices 1-3: the last red moves 2 left).
  • "RWRWR" -> 2 (both outer reds move one step toward the middle).
  • "WWRWWWRWR" -> 4 (median red at index 6; reds at 2 and 8 move 3 and 1).
  • "RWWWWR" -> 4 (either red walks across all four whites).
  • "RRRWWW" -> 0 (already grouped).
  • "WWW" -> 0 (no reds).
  • "" -> 0 (empty input).
  • "R" -> 0 (one red).
  • "RWRWRWRW" with cap = 3 -> -1 (true answer 4 exceeds the cap).
  • Large input: "R" + "W" * 10**5 + "R" -> 100000; check it runs in linear time.

Follow-ups

  1. Return -1 above a limit (e.g. 10^9). Check the running sum against the
    cap and stop early. In Python there is no overflow, but in Java or C++ use a
    64-bit accumulator.
  2. Group either colour, whichever is cheaper. Run the function for R and
    for W and return the minimum. Still O(n).
  3. Arbitrary swaps instead of adjacent swaps. Different problem: slide a
    window of size k over the string and count whites inside it; the answer is
    the minimum white count in any window (LeetCode 1151 style). O(n) with a
    sliding window. On a circular array, slide over the doubled string.
  4. Three colours, group every colour. Try each of the 6 colour orders;
    the cost of an order is the number of inversions between the current
    sequence and the target, counted with a merge sort or Fenwick tree in
    O(n log n), or O(n) with counters for a fixed small alphabet.
  5. Streaming updates (a ball changes colour). Keep the red positions in an
    order-statistics structure (Fenwick tree over indices) with prefix sums of
    q; the median and the sum of absolute deviations come from prefix sums in
    O(log n) per query.

Interviewer expectations

Mid-level (L4)

  • Sees that reds keep their relative order and that each step is one swap.
  • Writes the brute force over block starts or the "pull toward the middle red"
    version correctly, with empty and single-red cases handled.
  • Walks through one example by hand and gives the complexity.

Senior (L5)

  • Derives the q[i] = p[i] - i transform and explains why the median
    minimises the sum of absolute deviations.
  • Delivers O(n) code quickly, mentions 64-bit sums and the -1 cap, and tests
    with a brute force.
  • Handles the "either colour" and "arbitrary swaps" follow-ups without help,
    and explains how they differ.

Staff (L6+)

  • Proves the lower bound (each red must travel at least |p[i] - (s + i)|
    steps and swaps between reds are wasted), not only the construction.
  • Generalises: inversion counting for multiple colours, circular arrays,
    dynamic updates with Fenwick trees.
  • Discusses testing strategy (randomised comparison with a BFS over states for
    small n) and where the approach breaks (weighted moves, non-adjacent swap
    costs).

Sign in to comment, vote or remix.