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

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

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