< Ace Coding /> 🚀
✅ Hello everyone, today was my interview date, and I was asked the following question: At first, I thought I could use the two pointers technique to solve it, but then I realized that that would make the algorithm inefficient. Then I noticed that the number of 1s will be the length of the subarray with grouped 1s. This changed my approach to a fixed sliding window, and then the rest was easy. My interviewer was very nice and guided me the whole way.
'''
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] count_ones = 6 count_zeros = 3 curr_zeros = 3 min of count_zeros and curr_zeros
l
r
time comp = O(n)
space comp = O(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**5
data[i] is either 0 or 1.
'''
"""
1. count 1's store one count_ones
2. assign count_zeros = inf curr_zeros = 0
3. l, r = 0
4. check for a valid window
5. update curr_zeros
6. take the min of the count_zeros and curr_zeros
7. check if the values at the indexes are zeros if so decrement curr_zeros
8. update pointers
9. return count_zeros
"""
# my code
def minNumberOfSwaps(arr):
count_ones = arr.count(1)
count_zeros, curr_zeros = float('inf'), 0
l = 0
for r in range(len(arr)):
if arr[r] == 0:
curr_zeros += 1
# check for a valid window
if r - l + 1 == count_ones:
count_zeros = min(count_zeros, curr_zeros)
if arr[l] == 0:
curr_zeros -= 1
l += 1
return count_zeros if count_zeros != float('inf') else 0
"""
1= 6
curr_zeros = 3
count_zeros = 3
1,0,1,0,1,0,0,1,1,0,1
l
r
"""
#A2SV #a2sv #a2sv2024
A2SV a2sv 2024 In person
🚀 @AceCoding Presents! 🚀
9 · 396 ·