LeetCode 1151. Minimum Swaps to Group All 1's Together Solution in Java, C++, Python & More | Explanation + Code

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 <= 105
• data[i] is either 0 or 1.

Solutions

Solution 1: Sliding Window

First, we count the number of 1s 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 1s 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 1s 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.

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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; } }(code-box)