Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | codestorywithMIK
Vložit
- čas přidán 21. 06. 2024
- iPad PDF Link - github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 93rd Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good Array based Problem : Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | 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 : Count Number of Nice Subarrays | 2 Approaches | Similar Concept | Leetcode 1248 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/count-n...
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 Prefix Sum and Hashmap
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
This approach leverages the prefix sum technique combined with a hashmap to efficiently count subarrays with exactly k odd numbers.
Initialization:
mp (unordered_map) to store the frequency of prefix sums.
Variables: n (length of nums), count (result count), and currSum (current prefix sum).
Iterate Through Array:
For each element, update currSum by adding 1 if the element is odd (nums[i] % 2), else add 0.
Check if currSum - k exists in mp. If it does, increment count by the frequency of currSum - k.
Update mp to include the current currSum.
This method ensures that each subarray's prefix sum is calculated in linear time, and the hashmap provides efficient lookups for the required subarray sums.
Approach 2: Sliding Window (Khandani Template with a Twist)
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(1)
This approach utilizes a sliding window technique to dynamically count subarrays containing exactly k odd numbers.
Initialization:
Variables: n (length of nums), oddCount (number of odd numbers in the current window), count (subarrays ending at the current position), result (total count of valid subarrays), and two pointers i and j (window boundaries).
Sliding Window:
Iterate with j from 0 to n-1. For each element:
If the element is odd, increment oddCount and reset count to 0.
While oddCount equals k, increment count and adjust the window by incrementing i and decreasing oddCount if the element at i is odd.
Add count to result.
This method maintains a sliding window that expands and contracts based on the number of odd numbers, ensuring efficient computation in linear time with constant space.
✨ Timelines✨
00:00 - Introduction
#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
If anyone is confused why we have to reset prevCount = 0.
Let's see this with an example :
nums = {2, 1}, k = 1
we have two subarrays having oddCount --> {2, 1}, {1}
COUNT_NICE_SUBARRAY = 2
Now, suppose we have one more integer 2 . our array looks like --> {2, 1, 2}, k = 1
If you see, addition of this extra 2 will not impact the oddCount because this 2 is even.
So, we again get two more subarrays by including this 2 with previous two nice subarrays {2, 1} and {1}
so we get {2, 1, 2}, {1, 2}
So, over all Nice subarrays becomes - {2, 1}, {1}, {2, 1, 2}, {1, 2}
Now, COUNT_NICE_SUBARRAY = 4
Now, let's take one more example : Let's say the one more integer after {2, 1} is 1
So, our array becomes -> {2, 1, 1}
Let's break it again -> from {2, 1} we had {2, 1}, {1} i.e. COUNT_NICE_SUBARRAY = 2
Now, when 1 comes, this is another Odd number so oddCount is affacted and hence we can't add previousCount = 2 to our result because {2, 1, 1} doesn't have k = 1 odd numbers. It has 2 odd numbers.
So, we need to start from fresh and hence prevCount is made 0.
Now, the new subarray having k = 1 oddCount is the {1}
so we got one nice subarray now.
COUNT_NICE_SUBARRAY = 2 + 1 = 3 (correct output)
ek do example dry run karke mai samajh gaya ye. thanks a lot
Other youtuber max 9 minutes explanation while MIK comes with 32 minutes videos surely it has something extraordinary..
Honestly i find your explanation the best in whole yt community ..since i found your channel never looked back , for every topic i just look for your video😊
sir your channel is the most genuine channel ive seen, i have been able to build consistency on leetcode solving daily potd by the help of our approach and process of solving a question
25:00 this is why I come to your channel,thanks a lot
finally todays my 10th day of leetcode and i was able to code it after understanding the concept. thank you.
Can you please try to upload videos a little early if possible.
Your type of explanation is realy amazing!😃
great explanation bhaiya such a good quality content you are posting on youtube for free
Hi bhai, following you from the last 6-7 months ques bn rhe hai thanks for such simple and great explanations ❤
Bs ab jaldi se segment tree video no. 4 upload krdo
You actually taking my suggestion seriously, that's really cool bro.
Keep up the good work 😎
top class explaination as usual
i_bada approach, those who follow MIK might know this 😃
I feel this approach is well-suited for these kinds of problems and is quite intuitive.
public class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int i = 0, i_bada = 0;
int j = 0 ;
int res = 0;
int odd_count = 0;
while(j < nums.length){
if(nums[j] % 2 == 1)
odd_count++;
while(odd_count > k){
if(nums[i] % 2 == 1)
odd_count--;
i++;
i_bada = i;
}
while(i < nums.length && nums[i] % 2 == 0)
i++;
if(odd_count == k){
res += i - i_bada + 1;
}
j++;
}
return res;
}
}
Loved it 👌👌👌
0:00 Problem Introduction
2:04 Approach-1 (Using map)
18:09 Approach-1 code
20:17 Approach-2 (Sliding Window)
30:27 Approach-2 code
thanks man
thanks
Bhaiya kisi video mein apne daily routine mein baarien mein batana how u are managing ur work , utube and personal life
Your Hand Writing is really awesome!! Thanks for awesome explanation!
ekdm same leetcode 560 jaisa hai ye. dobara samjhane k lie thank you bhai. this shows your dedication towards providing quality content. thanks a lot
First approach was very clever. sliding window detect karliya tha maine but beech me stuck hogaya tha, then exactly wahi cheez aapne batai. thanks a lot
Sir can u please start uploading leetcode weekly and biweekly contest solution videos. That would be a great help!!
example sir aap aisa choose krte ho ki kai test case clear ho jaye
You are the best MIK
Good explanation 👏 👍
Nice video
Itna mast kaise parha lete ho yaar 🙏🏻
codechef ka contest discussion bhi start kariye sir please
thank you :-)
For those who are wondering why we need to reset the prevCount to 0 when we see a new Odd number (nums[j]).
Just try this leetcode's first Example : [1,1,2,1,1], k = 3 and you will see you are overcounting. simple dry run will help.
nice...
butter. what a fine explanation. Your choice of examples are really good. how do you come up with those. for example in the second approach example : {2, 1}, k = 1 was apt and helped me clear all my doubts
For hashmap approach
if arr = [2, 4, 6] ans k = 1
wont the result be 3
because oddCont - k => 0 - 1 = -1
this will come 3 times?
❤❤
Thanks a lot bhaiya
Congrats for 53k subs 🥳🥳
Lekin 2nd approach ache se samajh nahi aya 🙂
Thank you Gaurav ❤️
I would love to know where exactly in approach-2 you felt stuck. I will be more than happy to clear it here ❤️🙏
@@codestorywithMIK Bhaiya prevCount variable ka use case and usko reset karne ka reason samajh nahi aya thik se
@@gauravbanerjee2898 Sure, let me try to explain with a small example. I have Pinned my comment above for this.
If anyone is confused why we have to reset prevCount = 0.
Let's see this with an example :
nums = {2, 1}, k = 1
we have two subarrays having oddCount --> {2, 1}, {1}
COUNT_NICE_SUBARRAY = 2
Now, suppose we have one more integer 2 . our array looks like --> {2, 1, 2}, k = 1
If you see, addition of this extra 2 will not impact the oddCount because this 2 is even.
So, we again get two more subarrays by including this 2 with previous two nice subarrays {2, 1} and {1}
so we get {2, 1, 2}, {1, 2}
So, over all Nice subarrays becomes - {2, 1}, {1}, {2, 1, 2}, {1, 2}
Now, COUNT_NICE_SUBARRAY = 4
Now, let's take one more example : Let's say the one more integer after {2, 1} is 1
So, our array becomes -> {2, 1, 1}
Let's break it again -> from {2, 1} we had {2, 1}, {1} i.e. COUNT_NICE_SUBARRAY = 2
Now, when 1 comes, this is another Odd number so oddCount is affacted and hence we can't add previousCount = 2 to our result because {2, 1, 1} doesn't have k = 1 odd numbers. It has 2 odd numbers.
So, we need to start from fresh and hence prevCount is made 0.
Now, the new subarray having k = 1 oddCount is the {1}
so we got one nice subarray now.
COUNT_NICE_SUBARRAY = 2 + 1 = 3 (correct output)
@@codestorywithMIK Thanks a lot bhaiya Bahut ache se explain kardiya apne ❤❤. really sorry for bothering you, but the way you respond to each query in the comment section is what separates you from other creators. Thank you so much❤❤
@gauravbanerjee2898
Means a lot ❤️🙏
Sliding window approach not working for -
int[] nums = { 1, 1, 1, 1, 1 };
int k = 1;
app ka solution kis time pai aata hai mostly
sir please make solution of 3181. Maximum Total Reward Using Operations II using bitset; having trouble understanding it; and thanks for the segment tree playlist
sliding window problem mei aap ko kaise idea laga ki ye example kaam krega ki nahi...
qki mere se jaise hi ek test case paas hota to code kr deta phir fail ho jata hai...
Please help for the approach... what should be the minimum no of test cases we should try on before writing the code.... @codestorywithmik
bhai second wali approach samjh hi nhi ayi kiya kya, i wrote the queue code by self, but space na use karne wali approach nhi samjh ayi
Hi Sahil,glad to know you solved queue approach on your own.
Would you share where exactly you got stuck in the 2nd approach. I will try to explain here.
Also please see my pinned comment above ❤️
can we not use take and not take approach to find all subarray with that specific sum of odd number MIK?
For subarray, you need to have consecutive elements. If you don’t take an element you will have to start a new subarray. Or i think it will be a little tricky to handle a lot of corner cases
Is segment Tree frequenty asked topic in Interview? As my internship session started in July in my college.
Should I study this topic or focus on the preparation for Intership...
For internships no company as suck ask segment trees and some high paying companies ask segment trees in placement. So focus more on Topics such as Arrays, LinkedList, Stack, Queue, Graph, Tree and maps for internship.
@@the_star_harsh Thanks bro❤❤
Bhaiya segment tree ka next video kab aarha hai
bhaiya please provide this side pdf and all next problem please provides slides for better understanding and attached the pdf also for this question and one thing bhaiya apke samjane ka tarika alag hai jisme maja ata hai
Attached the link in the description
@@codestorywithMIK thank you
i get idea of approach 3rd-- but stuck and got wrong-- here is my code
class Solution {
public:
int countSubarraysWithKOddNumbers(int i, int oddCount, const vector& nums, int n, int k) {
if (i == n) {
return oddCount == k ? 1 : 0;
}
int includeCurrent = countSubarraysWithKOddNumbers(i + 1, oddCount + (nums[i] % 2 == 1), nums, n, k);
int excludeCurrent = countSubarraysWithKOddNumbers(i + 1, oddCount, nums, n, k);
return includeCurrent + excludeCurrent;
}
int numberOfSubarrays(vector& nums, int k) {
int n = nums.size();
return countSubarraysWithKOddNumbers(0, 0, nums, n, k);
}
};
i want to do it simply but use of recursion , no dp , just to run code , not to submit because it has exponential 2 time complexity. if anyone correct my code , i am really become so grateful.
hope for fast reply , if you can roast my code , it is also good for me .
Did it easily. I just wanted to inquire like how many videos can we expect in Segment Tree playlist? So that i can plan accordingly to do cses
For covering concepts, there will be only 2-3 more videos. Rest will be answered only. I’ll try to upload one tomorrow as I am out today ❤❤❤
@@codestorywithMIKtry to cover Fenwick tree also
Noted Sahil ❤️
@@codestorywithMIK there is lot to learn from ur videos in terms of approaching to solution of any problem
... Sir placement season is not too far so try to make dp and graph k hard question from leetcode... It'll be very helpful
sliding window ka ye twist thora confusing tha......
bhaeeya prevcount ko reset kiw kr rhey hai smjh nhi aaaya
Hi there, please see my Pinned comment above ❤
BHAI MAI BHI QUESTION KARTA HO BUT BNTA NHI HAI KYA KARU
us bhai us, 50 din se daily 1 ques kar rha hu, about 15 bhi khud nhi kar paya.
bhaiya are you not even reading my comment or ignoring me . I keep requesting from your previous last videos for solution of leetcode 2659 , make array empty but why are you even not clarifying whether you will make or not , or do you also not able to understand the intuition of this problem?If thats so , its fine i wasnt able to understand the intuition thats why i was requesting you. Not the segment tree approach but the other one.
Hi there,
Actually i get really occupied due to multiple other activities and get less time. I will try to cover this soon.
Thanks ❤️❤️❤️
@@codestorywithMIK thank you so much bhaiya you are my only hope, i really got distressed there that's why i wrote like that very sorry 🥺.
are bhai itna gussa. araam se bhai. working professional hain wo, time nikalna mushkil to hota hi hoga.
@@gui-codes hn bhai
i get idea of approach 3rd-- but stuck and got wrong , i want to do it simply but use of recursion , no dp , just to run code , not to submit because it has exponential 2 time complexity. if anyone correct my code , i am really become so grateful. here is my code
class Solution {
public:
int countSubarraysWithKOddNumbers(int i, int oddCount, const vector& nums, int n, int k) {
if (i == n) {
return oddCount == k ? 1 : 0;
}
int includeCurrent = countSubarraysWithKOddNumbers(i + 1, oddCount + (nums[i] % 2 == 1), nums, n, k);
int excludeCurrent = countSubarraysWithKOddNumbers(i + 1, oddCount, nums, n, k);
return includeCurrent + excludeCurrent;
}
int numberOfSubarrays(vector& nums, int k) {
int n = nums.size();
return countSubarraysWithKOddNumbers(0, 0, nums, n, k);
}
};
hope for fast reply , if you can roast my code , it is also good for me .
sliding window approach not working for int[] nums = { 1, 1, 1, 1, 1 }; int k = 1;