Minimum Number of K Consecutive Bit Flips | 3 Approaches | Detailed | Leetcode 995 | 3191
Vložit
- čas přidán 27. 07. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 94th Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve an extremely good problem : Minimum Number of K Consecutive Bit Flips | 3 Approaches | Super Detailed | Leetcode 995 | Leetcode 3191 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Minimum Number of K Consecutive Bit Flips | 3 Approaches | Super Detailed | Leetcode 995 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode 995 Link : leetcode.com/problems/minimum...
Leetcode 3191Link : leetcode.com/problems/minimum...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Auxiliary Array to Mark Flipped Indices
Time Complexity: O(n)
Space Complexity: O(n)
Description: This approach uses an auxiliary boolean array isFlipped to track whether an index has been flipped. The flipCountFromPastForCurri variable keeps track of the cumulative number of flips affecting the current index. For each index, it adjusts the flip count based on whether the i-k index was flipped and then checks if the current bit needs to be flipped based on the current flip count. If a flip is needed but not possible due to array bounds, it returns -1.
Approach 2: Using the Input Array to Mark Flipped Indices
Time Complexity: O(n)
Space Complexity: O(1)
Description: This approach modifies the input array to mark flipped indices by setting flipped elements to 2. The index_i_kitna_flip_jhela variable is used to track the number of flips affecting the current index. Similar to Approach 1, it adjusts the flip count based on whether the i-k index was flipped (indicated by 2 in the array) and checks if the current bit needs to be flipped. If a flip is needed but not possible due to array bounds, it returns -1.
Approach 3: Using Deque to Mark Flipped Indices
Time Complexity: O(n)
Space Complexity: O(k)
Description: This approach uses a deque (flipQue) to efficiently track the flips within the window of size k. The index_i_kitna_flip_jhela variable keeps track of the cumulative number of flips affecting the current index. For each index, it adjusts the flip count by removing the effect of the flip that goes out of the k-window (front of the deque) and checks if the current bit needs to be flipped. If a flip is needed but not possible due to array bounds, it returns -1. The deque helps in maintaining the flip history within the window efficiently.
These three approaches offer different trade-offs between space complexity and how the flip history is managed, with Approach 2 being the most space-efficient and Approach 1 and 3 offering clear and efficient ways to manage flip history with additional space usage.
✨ Timelines✨
00:00 - Introduction
00:55 - Problem Explanation
06:57 - Thought Process Approach-1
44:05 - Coding Approach-1
46:23 - Approach-2
49:52 - Coding Approach-2
50:43 - Approach-3
01:00:03 - Coding Approach-3
01:02:03 - Solving Leetcode 3191. Minimum Operations to Make Binary Array Elements Equal to One I
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
subah se pareshan tha. I watched Larry's video but kuch samajh nahi aya. Finally I understood each and every point. thanks a lot . I will also say ->
NETFLIX ❌
MIK Lengthy video 💚
Larry ka nai samajh aata . But banda legend corer hai
I love netfflix, DSA is very painful for my brain
@@adsnehi 😂😂😂😂🤣🤣
@@adsnehi 🤣
I can see the hard work in this video. There were few videos only for this problem on CZcams which i tried watching in the morning. They wasted my time.
And this legend makes a video of 1 hour to clear all my doubts .
Guruji 🙏🏻🙏🏻🙏🏻 aap kamaal ho
I love your explanations! The way you slowly build up intuition from examples really helps. Most other videos just go over the top solutions, without getting into the intuition, which may lead to memorizing solutions.
Only Mik can make this Hard question's explaination an easy one
For the first time, I could solve a Hard question in 15 minutes myself.
And like you said, it was only possible because I had solved a similar question before.
In the biweekly, there was a similar question where k was fixed = 3. I figured it out during the contest that it's greedy approach. Even in this question, I instantly knew it was greedy.
Now, to tackle with variable "k" , I had solved a similar question using "Scanline Algorithm" and instantly I knew how to tackle with "k" .
The final solution consisted of combining these two, and I had already solved similar questions before, this hard became literally easy-medium.
Tried other CZcamsrs videos on this topic, couldn't understand, here you cleared everything
Enjoyed learning the intuition of this problem a lot and the best part is that all the three approaches were beautifully connected, now this hard level prob also feels like a cakewalk!! thanks a lot!!
Oohh thanks a lot for such a clear explanation.....❤ ignore the people who all are saying vdo is lengthy....if they got the concept at the starting they can even do it by themselves rather then complaining
Bro your contribution is amazing!
matlab ye video recording he 1 Hr ka hai to preparation aur apko samajhane me kitna samay aur efforts lage hoge.
Hats Bro!! 🗿
very very nice explanation than all others whom i warched this. thanks keep it up
I believe no one has the patience to cover even every minute points in the explanation . Hats off to you
Excellent explanation of how to use the isFlipped array bhaiya!!! Thanks... I was stuck on this question for a long time!! Please keep uploading
Thankssss bhaiya, smash aa raha hi apki videos...
Awesome explanation! Keep it up.
I solved LC Contest Question with Bruteforce during contest as value of k was 3 :)
Watched till 25:15 , then i was able to do it by my own. Thanks for helping me building the intuition.
*Javascript Code:*
var minKBitFlips = function(nums, k) {
let res = 0;
let currFlipCount = 0;
for(let i=0;i=0 && nums[i-k]===-1) {
currFlipCount--;
}
if((currFlipCount%2===0 && nums[i]===0) || (currFlipCount%2===1 && nums[i]===1)) {
if(i+k>nums.length) return -1;
nums[i] = -1;
currFlipCount++;
res++;
}
}
return res;
};
bhai tussi great ho . thank you
Very nice explanation sir❤
Wow. Solving leetcode 3191 was insane 😮
Thank You!
great explanation
Great explanation
No one on this CZcams platform , i understand this problem from them but after seeing this video of MIK Bhaiya it is in very interesting way he solved that and I learnt from him
i made it myself thankfulllyyyy!!!
thankyou so much bhaii
Thank you so much 🙏
Kya baat hai sir, sochraha hu apna bhi ek channel khol lun, padhane se khud ko bhi zyda smjh ata hoga… aap Konsi company mei ho?
love u guruji!
Absolute cinema
Hats off bhai🫡
we can also use if( (nums[i] + flipcnt ) % 2 == 0) then we will flip
Jeetu Bhaiya from Kota Factory == MIK Bhaiya from DSA Industry ❤️❤️
Thank you so much bhaiya itna time leke itna easily samjhane k liye ❤️
And those who are saying why 1 hour long video, guys please understand it is impossible for bhaiya to explain in this much details with multiple dry runs within 15-20 mins. If you don't have time to watch a 1 hour long video and want to solve a leetcode hard problem just for the sake of maintaining a streak then don't do it . Belive me 1 hour deke dekho regret nahi karoge 😊💯
bhai tumhara ye comment instagram and linkedIn me kaafi reach me ja raha hai. MIK posted about this comment 👍
bhai ho sake to brute force bhi explain kiya kro taki jo new log h logic banane ka try kr rhe h unko bhi samjh aye chize acche se.
Bhaiya *longest valid parantheses* important q h please video banaiye aapne bola tha ki weekend par banaunga
Thanks mik, for such a detailed video, can you also pls discuss the solution for leetcode 3192.
Please make videos of contest upsolve
❤❤❤
❤❤
Bor bit manipulation playlist pls😎🙏
Kya ye ques hard tha ...No is video ke baad , not at all , it was super easy....
imp dry run 19:52
Hi MIK, I have a doubt regarding approach 3. Why we have used deque instead of queue. Is there any particular reason for using deque because both enqueue and dequeue operations in both queue and deque take same time O(1)..
Bhaiya aap dp concept? Kab start karenge
Insane explanation 😳🔥
And 38:13 was awesome 🙌
Bhaiya, Approach-2 mai aapne nums ko hii modify kiya hai, toh vo bhi toh space complexity mai count hona chahiye naa ? isFlipped nhi liya lekin data tamper kiya hai, toh space used should also be O(n) in approach-2
bhaiya please provide slides in all the next question please
Minimum Operations to Make Binary Array Elements Equal to One II , can we solve this with same approach ??
Sir, everything was good but please make a length video shorter.
class Solution {
public:
int minKBitFlips(vector& nums, int k) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
//check kya i+k > n ho gya hai tb -1 return kr do
if (i + k > n)
return -1;
for (int j = 0; j < k; j++) {
nums[i + j] ^= 1;
}
count++;
}
}
// check humara sara nums 1 ho gya hai kya
for (int i = 0; i < n; i++) {
if (nums[i] == 0)
return -1;
}
return count;
}
};
mik bhaia brute force approach🙏🙏🙏🙏
Can you do it in English?
Why is it always google asking these kinda problems🙃
COPIED FROM VIDEO DESCRIPTION
✨ Timelines✨
00:00 - Introduction
00:55 - Problem Explanation
06:57 - Thought Process Approach-1
44:05 - Coding Approach-1
46:23 - Approach-2
49:52 - Coding Approach-2
50:43 - Approach-3
01:00:03 - Coding Approach-3
01:02:03 - Solving Leetcode 3191. Minimum Operations to Make Binary Array Elements Equal to One I
bro i am following you for very long time , but one suggestion of mine is don't make too much large video you can explain the logic by one good testcase . We can not spent 1 hrs for one question so please try to make it as short as you can .
Sure
I will try to reduce 😇❤️🙏
@@codestorywithMIK esa kr skte ho ki normal km length ke hisab se explain krdo aur fir 10-15min ka detail dry run dal do sath me jinko detailed chahiye aur jinko normal chahiye vo skip kr lenge aur video me bta bhi dena if you have less time you can skip. sayad aap smaj pa rhe ho ki me kya bolna chah rha
@@codestorywithMIK thanks 😇
it is modified problem of leetcode 3191&3192?🎉❤
Indeed.
I have solved 3191 in the end of this video ❤️❤️❤️
@@codestorywithMIK bhiya perfact samjhaya katai zeher explaination
TLE (burite force)
class Solution {
public:
int solve(vector&nums, int i, int temp){
while(i < temp){
nums[i] = 1-nums[i];
i++;
}
return 1;
}
int minKBitFlips(vector& nums, int k) {
int count = 0;
for(int i=0; i
i was able to come up with brute force only
// Brute Force
void toggleBit(vector &nums, int temp)
{
if (nums[temp] == 0) nums[temp] = 1;
else nums[temp] = 0;
}
int minKBitFlips(vector &nums, int k)
{
int i = 0, j = i + k - 1, count = 0;
while (j < nums.size())
{
if (nums[i] == 0)
{
int temp = i;
count++;
while (temp
No need to create toggle function.
For toggling use:
nums[i] = 1 - nums[i]
class Solution {
public:
int minKBitFlips(vector& nums, int k) {
int n = nums.size();
vector pre(n+2 , 0);
int i = 1, j = k;
int ans = 0;
while( j
Sir ye question thoda dimaag ghuma dia. 😢
bhai 20-30 min max rakho video length
lengthy - more details and more to learn.
@@gui-codes 🙏🙏par 1 hour bahut jyada hai bhai 30 min should be max
nope as detailed as possible, new logo ko kafi help hoti h. aur 2-3 approach me ye expected h bor
Bhaiya.. Itni lambi lambi video na banao plss😢
Badi video mein hi clear hota
Bro Jo content hoga vohi toh banayenge aur HARD bhi toh hai question 😊
sahi mai bhai
@@harshtiwari416 yes
Bhai,
lengthy = more details = more to learn.
//int n=nums.size(),ans=0;
//for(int i=0;i