1151. Minimum Swaps to Group All 1's Together 🔒

SourceBiweekly Contest 6 Q2DifficultyMediumRating1508

Description

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.

Example 3:

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].

Constraints:

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

Solutions

Solution 1: Sliding Window

Thinking

All \(1\)s must occupy some window of length \(k\), the total number of \(1\)s. Zeros inside that window are the swaps needed, i.e. \(k\) minus the number of \(1\)s already there. Slide to maximize \(1\)s in the window; the answer is \(k\) minus that maximum.

First, we count the number of \(1\)s in the array, denoted as \(k\). Then we use a sliding window of size \(k\), moving the right boundary of the window from left to right, and count the number of \(1\)s in the window, denoted as \(t\). Each time we move the window, we update the value of \(t\). Finally, when the right boundary of the window moves to the end of the array, the number of \(1\)s in the window is the maximum, denoted as \(mx\). The final answer is \(k - mx\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array.

Python3JavaC++GoTypeScriptC#

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        k = data.count(1)
        mx = t = sum(data[:k])
        for i in range(k, len(data)):
            t += data[i]
            t -= data[i - k]
            mx = max(mx, t)
        return k - mx

class Solution {
    public int minSwaps(int[] data) {
        int k = 0;
        for (int v : data) {
            k += v;
        }
        int t = 0;
        for (int i = 0; i < k; ++i) {
            t += data[i];
        }
        int mx = t;
        for (int i = k; i < data.length; ++i) {
            t += data[i];
            t -= data[i - k];
            mx = Math.max(mx, t);
        }
        return k - mx;
    }
}

class Solution {
public:
    int minSwaps(vector<int>& data) {
        int k = 0;
        for (int& v : data) {
            k += v;
        }
        int t = 0;
        for (int i = 0; i < k; ++i) {
            t += data[i];
        }
        int mx = t;
        for (int i = k; i < data.size(); ++i) {
            t += data[i];
            t -= data[i - k];
            mx = max(mx, t);
        }
        return k - mx;
    }
};

func minSwaps(data []int) int {
    k := 0
    for _, v := range data {
        k += v
    }
    t := 0
    for _, v := range data[:k] {
        t += v
    }
    mx := t
    for i := k; i < len(data); i++ {
        t += data[i]
        t -= data[i-k]
        mx = max(mx, t)
    }
    return k - mx
}

function minSwaps(data: number[]): number {
    const k = data.reduce((acc, cur) => acc + cur, 0);
    let t = data.slice(0, k).reduce((acc, cur) => acc + cur, 0);
    let mx = t;
    for (let i = k; i < data.length; ++i) {
        t += data[i] - data[i - k];
        mx = Math.max(mx, t);
    }
    return k - mx;
}

public class Solution {
    public int MinSwaps(int[] data) {
        int k = data.Count(x => x == 1);
        int t = data.Take(k).Sum();
        int mx = t;
        for (int i = k; i < data.Length; ++i) {
            t += data[i];
            t -= data[i - k];
            mx = Math.Max(mx, t);
        }
        return k - mx;
    }
}

1151. Minimum Swaps to Group All 1's Together 🔒

Description

Solutions

Solution 1: Sliding Window

Comments