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

Input: arr = [0, 1, 0, 1]
Output: 1

Swap the middle 1 and 0 to obtain [0, 0, 1, 1].

Example 2

Input: arr = [1, 0, 0, 1]
Output: 2

Either permitted grouping requires two adjacent swaps.

Minimum Adjacent Swaps to Group a Binary Array

Hints

1. Count how many opposite-valued elements each new element would need to cross for each target order.
2. The two swap costs are the two possible cross-value inversion counts.

Approach

Adjacent swaps preserve the relative order among equal values. The exact cost of zeros-first order is the number of one-before-zero pairs, because every such inverted pair must cross once. Likewise, ones-first costs the number of zero-before-one pairs. Count both pair types in one scan using the numbers of zeros and ones already seen, then return the smaller total.

• Time complexity: O(n), where n is arr.length.
• Space complexity: O(1) auxiliary space.