You can go from 2*N iterations to N + total_ones: calculate ones in the window nums[:total_ones] and then move your window of constant size from 0 to N-1.
holy shit this is so easy when you explained it lol. I tried the greedy approach and it worked until it failed for the test case lol ur approach is amazin
great explanation sir! Fun Fact: we can skip the if statement to add 1 as the array only contains 1 and 0 so if we blindly take sum+=arr[i] it will work same i guess :/ but anyways what a great guy!!
the left pointer needs to go only up to N-1 the for loop should be this: for r in range(N+total_ones) That way the "l" doesn't need mod, and it's faster for large N and small total_ones
Another approach: (using sliding windows ofc) total_ones=nums.count(1) l=0 nums.extend(nums[:total_ones-1])
zero_cnt=0 res=float("inf") for r in range(len(nums)): zero_cnt+=not(nums[r]) if (r-l+1)==total_ones: res=min(res,zero_cnt) zero_cnt-=not(nums[l]) l+=1
i think a better idea would be realizing that by grouping 1s tgt, 0s would be group tgt too, so you just keep track of cnt of 0s for the respective 0 wnd too.
For the circular part I tries consolidating zeros instead of ones , since if zeros are linearly together , ones also must be together , circular or otherwise.
my solution, more consice and the loop is running N + # of 1's: def minSwaps(self, nums: List[int]) -> int: total = sum(nums) right = total if right == len(nums): return 0 maxSub = sum(nums[:total]) window = maxSub for left in range(len(nums)): window = window - nums[left] + nums[right] maxSub = max(maxSub, window) right = (right + 1) % len(nums) return total - maxSub
You probably could've made your run time a little more quicker if you exited the loops once the left pointer exceeds the length of the original array instead of going the full 2N. But yeah, this one was a doozy - I don't think I would have gotten it without the hints that they gave.
You consider it against all possible cases. You devise cases and say to yourself that this solution must return this valid value if it works properly and if it don't, then something is wrong with the solution (using counter-examples).
The reason why we never saw a Minimum Swaps to Group All 1's Together I is because it is premium-only. i guess it's the same problem without circular edge case
Thank you for sharing. You can apply Sliding Window for counting minimum 0 in K window def minSwaps(self, nums: List[int]) -> int: """ Calculate minimum sliding window for 0 """ k = nums.count(1) numZero = nums[:k].count(0) ans = numZero n = len(nums) for R in range(k, 2*n): if nums[R%n] == 0: numZero +=1 if nums[(R-k)%n] == 0: numZero -= 1 ans = min(ans, numZero) return ans
surprisingly ... i did not find this tough at all ! Simple sliding window.. with double the array size ! easy def minSwaps(self, nums: List[int]) -> int: ones = nums.count(1) double = nums+nums ct = nums[:ones].count(1) maxx = ct l=0 for i in range(ones,len(double)): if double[i]==1: ct+=1 if double[l]==1: ct-=1 maxx = max(ct,maxx) l+=1 return ones - maxx
![[LIVE] นาทีนี้ต้องพี่ทนาย | ทนายแก้ว vs ทนายไพศาล | #คุยให้เด็กมันฟัง EP.47 (02/11/67)](http://i.ytimg.com/vi/HmquaO-PL_M/mqdefault.jpg)
0:57 In the example "0101101", you actually only need 1 swap to make "0001111" or "0111100".
My dumb ass brain stopped functioning and thought we can only do swap between two adjacent number and waste 1 hour on this problem...
nah its not you, this problem is a bit evil for the beginning of the month lmao
I also thought so. 😢
Same here man
Not one hours for me but a good 20 mins.
You can go from 2*N iterations to N + total_ones: calculate ones in the window nums[:total_ones] and then move your window of constant size from 0 to N-1.
holy shit this is so easy when you explained it lol. I tried the greedy approach and it worked until it failed for the test case lol ur approach is amazin
this one was tough :p
great explanation sir!
Fun Fact: we can skip the if statement to add 1 as the array only contains 1 and 0 so if we blindly take sum+=arr[i] it will work same i guess :/ but anyways what a great guy!!
this is one of the greatest explanations ever
the left pointer needs to go only up to N-1
the for loop should be this:
for r in range(N+total_ones)
That way the "l" doesn't need mod, and it's faster for large N and small total_ones
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
Another approach: (using sliding windows ofc)
total_ones=nums.count(1)
l=0
nums.extend(nums[:total_ones-1])
zero_cnt=0
res=float("inf")
for r in range(len(nums)):
zero_cnt+=not(nums[r])
if (r-l+1)==total_ones:
res=min(res,zero_cnt)
zero_cnt-=not(nums[l])
l+=1
return res if res!=float("inf") else 0
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
you are a genius brother!!! I tried backtrack loll, so complicated to write
NICE SUPER EXCELLENT MOTIVATED
the hints of this of this problem are pretty good they gave like 5 hints and the second hint gives it all away
i think a better idea would be realizing that by grouping 1s tgt, 0s would be group tgt too, so you just keep track of cnt of 0s for the respective 0 wnd too.
and you just take the min of the two ans
For the circular part
I tries consolidating zeros instead of ones , since if zeros are linearly together , ones also must be together , circular or otherwise.
The % idea was really brilliant
It felt to easy yet amazing after watching the first 3 minutes of your video ❤❤ i was able to solve it
my solution, more consice and the loop is running N + # of 1's:
def minSwaps(self, nums: List[int]) -> int:
total = sum(nums)
right = total
if right == len(nums): return 0
maxSub = sum(nums[:total])
window = maxSub
for left in range(len(nums)):
window = window - nums[left] + nums[right]
maxSub = max(maxSub, window)
right = (right + 1) % len(nums)
return total - maxSub
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
You probably could've made your run time a little more quicker if you exited the loops once the left pointer exceeds the length of the original array instead of going the full 2N. But yeah, this one was a doozy - I don't think I would have gotten it without the hints that they gave.
Can you solve the ready-made function in the list? Or is it forbidden?
Thanks for sharing!
in line 7 we can just got til n+totalOnes . 2*n is not required
Thank you
I was staring at this problem for 10 mins. Thinking about the intervals, and how to calculate average distance between dots......
How'd you know this solution would work?
You consider it against all possible cases. You devise cases and say to yourself that this solution must return this valid value if it works properly and if it don't, then something is wrong with the solution (using counter-examples).
Everyday thank you
Another little tweak, you only have to check the max when you add another one at your right pointer.
@neeetcode where to apply for the interview
The reason why we never saw a Minimum Swaps to Group All 1's Together I is because it is premium-only. i guess it's the same problem without circular edge case
Why we need window one, max_window_ones?
Coded on my own
why neetcode website not able to open??????? i am facing issue from last 3-4 days
I thought it would be a cakewalk
Thank you for sharing. You can apply Sliding Window for counting minimum 0 in K window
def minSwaps(self, nums: List[int]) -> int:
"""
Calculate minimum sliding window for 0
"""
k = nums.count(1)
numZero = nums[:k].count(0)
ans = numZero
n = len(nums)
for R in range(k, 2*n):
if nums[R%n] == 0:
numZero +=1
if nums[(R-k)%n] == 0:
numZero -= 1
ans = min(ans, numZero)
return ans
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
I couldn't even solve it using brute force and wasted an hour
surprisingly ... i did not find this tough at all ! Simple sliding window.. with double the array size ! easy
def minSwaps(self, nums: List[int]) -> int:
ones = nums.count(1)
double = nums+nums
ct = nums[:ones].count(1)
maxx = ct
l=0
for i in range(ones,len(double)):
if double[i]==1:
ct+=1
if double[l]==1:
ct-=1
maxx = max(ct,maxx)
l+=1
return ones - maxx
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
4:12 🤔🤔
I hate "guess the trick" questions
l,f=len(n),sum(n); o=t=sum(n[:f])
for i,v in enumerate(n,f): o=max(o,t:=t+n[i%l]-v)
return f-o
i hate circular array