Minimum Swaps To Group All Ones Together
01 · Problem
You are given a binary array data (each element is 0 or 1). The array is not circular.
In one swap you may exchange the values at any two positions (they do not need to be adjacent). Return the minimum number of swaps required to place all the 1s in one contiguous block, anywhere in the array.
If the array contains zero or one 1, it is already grouped and the answer is 0.
02 · Examples
data = [0,1,1,0,1,0,1]
1
There are four 1s. The window at indices 1-4 is [1,1,0,1], which already holds three of them, so one swap moves the last 1 into its 0.
data = [0,0,0,1,0]
0
There is only a single 1, so it is already grouped.
data = [1,0,1,0,1,0,0,1,1,0,1]
3
There are six 1s. The best window of length 6 is indices 3-8 = [0,1,0,0,1,1], which already holds three 1s, so three swaps bring in the remaining three.
03 · Constraints
- 011 <= data.length <= 105
- 02data[i] is either 0 or 1
- 03The array is linear, not circular
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.