Minimum Swaps to Group All 1's Together
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 either0
or1
.
Solution
This is a classic sliding window question that has a fixed size.
We wish to find a window to store all the 1's in the very end, thus we fix the size to the total number of 1's.
Since we want to use minimum number of swaps, it will be best if we can find a window with most 1's (or least 0's).
Let count1
be the number of 1's in the entire data
. We will initialize total
to be the number of 1's in the window from index 0 to the count1
(which is the sum of the window).
Then, as we slide the window to the right, we remove data[r-count1]
from the total
and add data[r]
to the total
so that total
is the sum of the new window.
Then for each window that has size of count1
, we compare for the minimum swaps. Here, we calcluate the swaps count1-total
, as the number of swaps is just the number of 0's in the window.
Implementation
1def minSwaps(self, data):
2 count1 = data.count(1)
3 total = 0
4 for i in range(count1): total += data[i]
5 swaps = count1-total
6 for r in range(count1, len(data)):
7 total += data[r]
8 total -= data[r-count1]
9 swaps = min(swaps, count1-total)
10 return swaps
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Solution Implementation
Which of the following problems can be solved with backtracking (select multiple)
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.