Minimum Adjacent Swaps to Group a Binary Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
# Minimum Adjacent Swaps to Group a Binary Array
You are given an array containing only `0` and `1`. Using adjacent-element swaps, rearrange it so that all zeros occupy one end and all ones occupy the other end.
Either final ordering is allowed: all zeros followed by all ones, or all ones followed by all zeros. Return the minimum number of adjacent swaps required across the two choices.
Implement `minBinaryGroupingSwaps(arr)`.
## Constraints
- `1 <= arr.length <= 100,000`
- Every element is `0` or `1`.
- The answer fits in a signed 64-bit integer.
- Swapping positions `i` and `i + 1` costs one move.
## Example 1
```text
Input: arr = [0, 1, 0, 1]
Output: 1
```
Swap the middle `1` and `0` to obtain `[0, 0, 1, 1]`.
## Example 2
```text
Input: arr = [1, 0, 0, 1]
Output: 2
```
Either permitted grouping requires two adjacent swaps.
Quick Answer: Find the minimum adjacent swaps needed to group every zero at one end and every one at the other, choosing the cheaper orientation. The problem tests inversion counting, already-grouped inputs, balanced choices, and 64-bit accumulation.
Given an array containing only 0 and 1, use adjacent swaps so all zeros occupy one end and all ones the other. Either zeros followed by ones or ones followed by zeros is permitted. Return the minimum adjacent-swap count across those two choices.
Constraints
- 1 <= arr.length <= 100,000
- Every element is 0 or 1.
- One adjacent swap costs one move.
- Either zeros-first or ones-first grouping is allowed.
- The answer fits in signed 64-bit range.
Examples
Input: ([0, 1, 0, 1],)
Expected Output: 1
Explanation: One adjacent swap produces zero-first grouping.
Input: ([1, 0, 0, 1],)
Expected Output: 2
Explanation: Both permitted target orders cost two swaps.
Hints
- Count how many opposite-valued elements each new element would need to cross for each target order.
- The two swap costs are the two possible cross-value inversion counts.