Minimum Adjacent Swaps to Place White Balls Before Black Balls
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Minimum Adjacent Swaps to Place White Balls Before Black Balls
There are `n` balls arranged in a line. A 0-indexed binary string `s` describes their colors: `'0'` represents a white ball and `'1'` represents a black ball.
In one step, choose two adjacent balls and swap them. Return the minimum number of steps required to put all white balls on the left and all black balls on the right.
### Examples
**Example 1**
```text
Input: s = "11010"
Output: 5
```
One valid five-step sequence is `"11010" -> "10110" -> "01110" -> "01101" -> "01011" -> "00111"`. The zero initially at index `2` has two black balls before it; the zero at index `4` has three. These five out-of-order black/white pairs each need to cross, so fewer than five adjacent swaps cannot suffice.
**Example 2**
```text
Input: s = "00101"
Output: 1
```
Swapping indices `2` and `3` gives `"00011"`. The only black ball lying before a white ball is the one at index `2` relative to the zero at index `3`, so one swap is necessary and sufficient.
### Constraints
- `1 <= n == s.length <= 10^5`.
- Every `s[i]` is either `'0'` or `'1'`.
### Clarifying Questions
- Can any two positions be swapped in one step? No; only adjacent positions.
- What is the desired color order? All zeros first, followed by all ones.
- Must both colors occur? No; the constraints allow a string containing only one color, which already satisfies the target order.
- Do we return the final string or the swap sequence? No; return only the minimum step count.
- Can the result require more than a signed 32-bit integer? Yes; use the provided `long long` return type.
### C++ Interface
```cpp
class Solution {
public:
long long minimumSteps(string s) {
}
};
```
### Reasoning Checkpoints
- Respect the adjacency requirement when deriving a lower bound on moves.
- Explain why a sequence of legal swaps can attain that bound.
- Handle single-color strings and the largest possible answer.
```hint Count out-of-order pairs
For each white ball, count the black balls originally before it. How does swapping one adjacent 10 pair change the total number of these out-of-order pairs?
```
Overview: Find the fewest adjacent swaps needed to move every white ball before every black ball in a binary color string.
