Group Circular Ones with Arbitrary Swaps
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The first and last positions of the binary array `nums` are adjacent, making the array circular. In one operation, swap the values at any two distinct positions. Return the fewest operations needed to place all the ones in one contiguous circular block, which may start anywhere.
```cpp
class Solution {
public:
int minSwaps(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [1,0,1,0]
Output: 1
Explanation: Swap positions 1 and 2 to obtain [1,1,0,0].
```
**Example 2:**
```text
nums = [1,0,0,1]
Output: 0
Explanation: The two ones already form a block across the boundary.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- Every entry is zero or one.
### Clarifying Questions
Swaps are arbitrary, not necessarily adjacent. An array with no ones or one one already satisfies the goal.
```hint Inspect the structure
If there are k ones in total, how many zero entries does a proposed length-k target block contain?
```
### Reasoning checkpoints
- Allow a group to cross the last-to-first boundary of the array.
- Use the source's arbitrary-position swap rule when proving both necessity and attainability of the count.
- Handle no ones, a single one, and an array consisting entirely of ones.
### Optional extensions
How would restricting swaps to adjacent positions change the problem?
Overview: Group Circular Ones with Arbitrary Swaps. The binary array nums is circular, so its first and last positions are adjacent. Swap values at any two distinct positions. Return the fewest swaps needed for every 1 to occupy one contiguous circular block, at any location.
