Coding

Minimum Swaps to Group All 1’s Together

Asked at

Swiggy

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There is a binary array data of length n, where each element is either 0 or 1. In one move, you can swap any two elements of the array. Your task is to determine the minimum number of swaps required so that all the 1’s in the array become grouped together (i.e. appear consecutively). If the 1’s are already grouped together, return 0. Return the minimum number of swaps required.

Input: data = [1, 0, 1, 0, 1] Output: 1 Explanation: There are 3 ones in the array. If you consider a window of length 3, the optimal window (either the first or last window) contains 2 ones. Thus, the minimum swaps required = 3 - 2 = 1.

Input: data = [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] Output: 3 Explanation: One possible solution that uses 3 swaps is [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1].

Input: data = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0]

1 <= data.length <= 105 data[i] is either 0 or 1.

cpp

class Solution {
public:
    int minSwaps(vector<int>& data) {
    // Your Code Goes Here
    }
};

java

class Solution {
    public int minSwaps(int[] data) {
        // Your Code Goes Here
    }
}

python

class Solution(object):
    def minSwaps(self, data):
        """
        :type data: List[int]
        :rtype: int
        """
        // Your Code Goes Here

javascript

/**
 * @param {number[]} data
 * @return {number}
 */
var minSwaps = function(data) {
    //Your Code Goes Here
};

csharp

class Solution
{
    public int minSwaps(int[] data)
    {
        // Your Code Goes Here
    }
}

func minSwaps(data []int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Count total ones to get window length k.
02Count ones in the first k positions.
03Slide the window one step at a time.
04Keep the maximum ones in any k window.
05Return k minus that maximum.

Reference answer

All ones must end up together, so the final block has length equal to the total number of ones, k. For any candidate block of length k, every zero inside it must be swapped out, and the number of swaps is k - onesInWindow. Therefore maximize the number of ones in a length-k sliding window. Count the first window, then advance one position at a time by subtracting the leaving value and adding the entering value. Track the maximum count and return k - best. When k is zero or one, the answer is zero. This uses O(N) time and O(1) extra space, and it is preferable to attempting explicit swap sequences. Confirm whether the circular-array variant is intended because that requires doubled indexing.

Then expect these follow-ups

How does the circular variant change?
Tests: modular indexing
Can you return the best block boundaries?
Tests: tracking

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question