To everyone asking *how* to arrive at the intuition of greedily trying to flip any "0" bits, this was basically my thought process that led me there: 1. Since a flipping operation is reversible, that must mean that if I can go from "nums" to all 1s with flips, it must also be possible to go from all 1s to "nums". 2. If we ASSUME the array starts off as being all 1s, that would mean that the first bit that is 0 would HAVE to be the boundry of a flipping location. Since, those all 1's aren't going to sponaneously go from their initial state of "1" to "0" unless it is the start of a flip. 3. This assumption can pretty much apply recursively, where we can assume that any unexpected transition from "1" to "0" represents another flip. 4. If we reach the end and there are still flips not accounted for, that means there were flip boundaries at intervals other than "k" and that we didn't start with all 1s to begin with.
@freecourseplatformenglish28293 ай бұрын
Solved it on my own Beats(94%). Finally seeing the fruit of almost year of practise. class Solution: def minKBitFlips(self, nums: List[int], k: int) -> int: n = len(nums) flips = [0]*n flipSum = 0 count = 0 # Count the number of flips efficiently for i in range(n - k + 1): if (nums[i] == 0 and (flipSum == 0 or flipSum % 2 == 0)) or (nums[i] == 1 and flipSum % 2 == 1): count += 1 flips[i] = 1 flipSum += 1 if i + 1 >= k: flipSum -= flips[i - k + 1] # Check if last k character is 1 for i in range(n - k + 1, n): if (nums[i] == 0 and (flipSum == 0 or flipSum % 2 == 0)) or (nums[i] == 1 and flipSum % 2 == 1): return -1 flipSum -= flips[i - k + 1] return count
@betabias3 ай бұрын
i know you made it pretty simple, but coming up with this logic of mod is basically made me go into existential crisis and question my reality
@aminfardi46332 ай бұрын
Fun fact: in the constant space solution, you don't actually need to check if `i-k >=0`. If it ends up being negative, it'll be a lookup from end of the array (i.e. nums[-2]). For all k values, since we haven't changed any of the numbers in the indexes ahead, it'll still do what we want it to do (which is catch any changes in the past only when it sees a 2. It might still be good practice to ensure you are not going out of bounds though...
@chrischika70263 ай бұрын
very similar to biweekly problems this week.
@mahesh_bvn3 ай бұрын
exactly
@emmanuelfleurine1213 ай бұрын
Hi 😅 what is biweekly problem?
@greatfate3 ай бұрын
the biweekly passed naive approach, this one doesn't
@De1n1ol3 ай бұрын
@@emmanuelfleurine121they meant a problem from the last biweekly contest
@aadityatripathi83633 ай бұрын
the 2nd problem could be solved easily using three variables, and the 3rd problem could be solved using a bool flag; this is a lot harder than them according to me
@TheLearningLab8983 ай бұрын
fuck, im still confused..
@nirmalgurjar81813 ай бұрын
We will keep track of valid count of flips till current index, and check if flip count is odd (num is in flipped condition) and curr num is 1 (means actual flipped num is 0) hence we need to flip this index to make it 1. Also same for, if current count is even (cancelling flips) and num is 0 means we need to flip this index. we will keep track of flip index in deque for efficient adding a new index to end and removing index which is out of current window from front. Here is java solution: public int minKBitFlips(int[] nums, int k) { int n = nums.length, res = 0; Deque dq = new LinkedList(); for(int r = 0; r < n; r++){ if(!dq.isEmpty() && dq.peekFirst() n - k){ return -1; } res++; dq.addLast(r); } } return res; }
@joaopedrocastro44863 ай бұрын
yeah bro you are not alone
@catcoder123 ай бұрын
relatable
@luuduytoan38193 ай бұрын
First try with brute force and get TLE :D
@aadarshyadav66503 ай бұрын
Same bro tle on test case 101/113
@shree27103 ай бұрын
110/113 :'D
@RohanKumar-q6y3 ай бұрын
Tell me honestly how do you come up with approach? I can go waste whole day and still can't figure out the solution
@nonefvnfvnjnjnjevjenjvonej33843 ай бұрын
you have to have seen this before or have read some competitive programming books.. these mod tricks, fenwick tree etc are quite common in those books... i swear companies who ask these can go f*ck themselves.. lol
@satviksrinivas87643 ай бұрын
The more problems you do, the more you'll start to pick up patterns, patterns are the key.
@chrischika70263 ай бұрын
look at the biweekly this week #2 and #3
@GoonCity7773 ай бұрын
He’s just smarter…… jk….. you got this
@GoonCity7773 ай бұрын
Look at solutions & code them hands-on. Then do others without looking.
@srprawinraja42613 ай бұрын
Why use while? you can simply use if statement to pop the left element.
@aadityatripathi83633 ай бұрын
what if the queue had 2 flips that affected the last element ? we have to pop all the flips that no longer affect our current element , thats why we use while
@nathantran43413 ай бұрын
@@aadityatripathi8363 you're checking at each iteration of i though so an if statement would be enough. Once an index is out of range it will immediately be removed from the queue in the next iteration
@prajwalchoudhary48243 ай бұрын
holy cow as soon as i understood how to use queue i solved it instantly on my own. Thanks man.
@chisomedoka56513 ай бұрын
Hi Neetcode, I’ve been focused on learning algorithms and patterns for about a year now, and normally when I see questions I could usually figure out what pattern or algorithm to use. So my question is how do I get good at solving these kind of questions cause they don’t follow the popular algorithms or patterns
@jaatharsh3 ай бұрын
awesome, u changed this Ques from Hard to Easy, this is why LeetCode ques in interview seem unfair sometimes, if u know u know
@pawekrzyzak45623 ай бұрын
If you are still confused, I highly recommend to try with very similar problems that have medium level - 3191. and 3192.
@Aryan-rb3yk3 ай бұрын
Waaoooo great explanation, is this a pattern? i haven't done any bit manipulation questions, though I knew I can use sliding window here but still just didn't know how....
@loke_mc80533 ай бұрын
Everything is nice nav. but one suggestion, while u provide the code, can u give a side-by-side animation on what is happening in the list or the code that runs..that would be really helpful.thank you
@sdemji3 ай бұрын
that's kinda your job with every code that you don't understand
@sunshineandrainbow54533 ай бұрын
Very Great Explanation. Thank you so much !!!
@chrisboumalhab12113 ай бұрын
I understand how the solution works. I just don't understand why the greedy approach is the best solution here. How can a person who sees this problem guarantee that the greedy approach is the best way to go?
@gauravkungwani3 ай бұрын
well i thought of greedy, turned out that it was very simple to think but barrier was N*K time, so this video helped after that
@Friend01foru3 ай бұрын
The best 🌟
@28_vovanthinh753 ай бұрын
Nice explanation!!
@satyamjha683 ай бұрын
Solved it but with O(k) space! Sadly, unable to solve it using O(1) space!
@chien-yuyeh93863 ай бұрын
🎉🎉
@Phantom-wi9hw3 ай бұрын
best explanation
@akashverma57563 ай бұрын
This problem is hell as hard.
@nanicreations77293 ай бұрын
❤
@aseshshrestha29093 ай бұрын
Why did you create multiple channels? Why are you no longer uploading video in your old channel?
@vijayanks17143 ай бұрын
This channel only focus on Leetcode POTD. 1st channel for Interview Preparation related stuff not solving ranom coding question
@GeetainSaar3 ай бұрын
remember: if your love makes you weak its not love . love only makes your partner stronger and as you
@CS_n00b3 ай бұрын
Very beautiful
@asagiai49653 ай бұрын
I like the thumbnail have flipflops, lol.
@shaswatshourya50773 ай бұрын
You are awesome
@pushkarsaini23 ай бұрын
How do you even comeup with these 🤔
@JamesBond-mq7pd3 ай бұрын
He is a genius
@chrischika70263 ай бұрын
look at the biweekly this week #2 and #3
@MrPersononutube3 ай бұрын
PLZ LEETCODE 2090
@AnandKumar-kz3ls3 ай бұрын
solution in java class Solution { public int minKBitFlips(int[] nums,int k){ Queue q = new LinkedList(); int i = 0; int n = nums.length; int oprs = 0; while( i < n){ if( i > ( n - k) ){ if( (nums[i] + q.size()%2)%2 == 0 ) return -1; } else { if( (nums[i] + q.size()%2)%2 == 0 ){ oprs++; q.add(i); } } if( !q.isEmpty() && q.peek() == (i - k + 1) ){ q.poll(); } i++; } return oprs; } }