ontent":"https://k5kc.com/images/og-image.png"}]] 21:I[34242,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 22:I[56081,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 23:I[12820,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 24:I[15024,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 25:Td8e,

Problem

A swap is defined as taking two distinct positions in an array and swapping the values in them.

Given a binary array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [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].

Solution

Method 1 - Sliding Window

The idea is to find the smallest number of swaps required to group all 1s together in any position within the array.

Approach

Count 1s: First, count the total number of 1s in the array, denoted as totalOnes.
Sliding Window: Use a sliding window of size totalOnes to find the minimum number of 0s in any window of that size. The number of swaps needed will be equal to the number of 0s in the optimal window.

Steps

Count the total number of 1s, totalOnes.
Apply a sliding window of size totalOnes to count the number of 0s in each window, and keep track of the minimum count of 0s.
The answer will be the minimum count of 0s found in the windows, as this represents the minimum number of swaps needed.

Code

[{"language":"Java","code":"class Solution {\n\n\tpublic int minSwaps(int[] nums) {\n\t\tint totalOnes = (int) Arrays.stream(nums).filter(num -> num == 1).count();\n\n\t\tif (totalOnes == 0) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tint n = nums.length;\n\t\tint minSwaps = Integer.MAX_VALUE;\n\t\tint currentZeros = 0;\n\n\t\t// Initial window of size totalOnes\n\t\tfor (int i = 0; i < totalOnes; i++) {\n\t\t\tif (nums[i] == 0) {\n\t\t\t\tcurrentZeros++;\n\t\t\t}\n\t\t}\n\n\t\tminSwaps = currentZeros;\n\n\t\t// Sliding window: traverse the array and update counts\n\t\tfor (int i = 1; i < n; i++) {\n\t\t\tif (nums[(i - 1) % n] == 0) {\n\t\t\t\tcurrentZeros--;\n\t\t\t}\n\n\t\t\tif (nums[(i + totalOnes - 1) % n] == 0) {\n\t\t\t\tcurrentZeros++;\n\t\t\t}\n\n\t\t\tminSwaps = Math.min(minSwaps, currentZeros);\n\t\t}\n\n\t\treturn minSwaps;\n\t}\n\n\tpublic static void main(String[] args) {\n\t\tint[] nums = { 1, 0, 0, 1, 1, 0, 1 };\n\t\tSystem.out.println(minSwaps(nums)); // Output: 1\n\t}\n}","lang":"java"}]

Complexity

⏰ Time complexity: O(n), where n is the length of the array
🧺 Space complexity: O(1)

19:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children"

Related Tags