There is a slight mistake in the code. Please find the fix below while (mpp.size() > k) { mpp[nums[l]]--; if (mpp[nums[l]] == 0) mpp.erase(nums[l]); l++; } The while condition and the value of L
its working fine int n=arr.length,l=0,r=0,count=0; HashMap map = new HashMap(); while(r k){ map.put(arr[l],map.getOrDefault(arr[l],0)-1); if(map.get(arr[l]) == 0) map.remove(arr[l]); l++; } count+=(r-l+1); r++; } return count;
Hey Striver, I think there are two corrections needed to be done the while condition should be while (mp.size() > k) and instead of l-1, it should be incremented to l+1
Bro u r goated, I was able to solve the problem without looking at the solution thanks to you covering all patterns in the previous problems. Your last few vids helped me in understanding pattern 2 and 3 perfectly.
Hi Striver, I think few corrections required, but I think you have already addressed it, adding in the java reference code, but bro you are awesome. class Solution { public int subarraysWithKDistinct(int[] nums, int k) { return countSubArraysWithGoal(nums, k) - countSubArraysWithGoal(nums, k-1); } private int countSubArraysWithGoal(int[] nums, int goal){ if(goal
hahaha yes.i had seen the videoes before this and thought i watch the playlist from this video today,saw daily question,was easy to solve from the previous videoes knowledge and now when i open this playlist again,i see this video hahah
Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses. Would also like your insights on the point : While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?
00:04 Count the number of subarrays with exactly K different integers. 02:26 Use two pointers and a sliding window to find subarrays with k different integers 04:52 Algorithm for counting total number of subarrays with k different integers 07:12 Using count and frequency to determine valid windows 09:43 Using sliding window to find subarrays with k different integers. 12:16 Creating valid subarrays using 2 Pointers and Sliding Window approach 14:37 Using sliding window to find subarrays with k different integers 17:03 Using the sliding window technique to solve for subarrays with k different integers. 19:17 Discussion on time and space complexity with the use of map data structure. Crafted by Merlin AI.
here is java solution code class Solution { public int subarraysWithKDistinct(int[] nums, int k) { int subK = helper(nums,k); int sub = helper(nums,k-1); return subK-sub; } private int helper(int nums[], int k){ HashMap map = new HashMap(); int left=0; int right=0; int count=0; while(rightk){ map.put(nums[left],map.get(nums[left])-1); if(map.get(nums[left])==0){ map.remove(nums[left]); } left++; } count = count+ right-left+1; right++; } return count; } }
I have a question: When we see that more than k elements are occurring in the subarray, then we remove it from the map So at max the map will always store (k+1) elements So the overall space complexity should be O(K)
Did it myself, But I'm sure it is because i was in the flow of thinking in the sliding window approach, Wouldn't be able to do it if it was randomly thrown at me,
Hey can anyone explain me why space complexity is O(n) I think it should be O(k+1) because as soon as size exceeds 2*(k+1) we are shrinking the window .Please rectify me if I am wrong 😊
class Solution { public int help(int[] arr, int k) { int l = 0; int r = 0; int cnt = 0; HashMap mpp = new HashMap(); while (r < arr.length) { mpp.put(arr[r],mpp.getOrDefault(arr[r],0)+1); while(mpp.size()>k){ mpp.put(arr[l],mpp.get(arr[l])-1); if(mpp.get(arr[l])==0){ mpp.remove(arr[l]); } l++;} cnt=cnt+r-l+1; r++; } return cnt;
} public int subarraysWithKDistinct(int[] arr, int k) { return help(arr,k)-help(arr,k-1);
when sliding window shrinking is happening then at that time we will use k-1 probably this case arises when there is problems ask us to count. Even in the above problem also when we took up to k then we missed few subarrays so at that time we take k-1 . so by subtracting k and (k-1) we get the exact answer
can someone please correct my code class Solution { public: int subarraysWithKDistinct(vector& nums, int k) { int l=0; int r=0; int cnt=0; map m; while(rk){ m[nums[l]]--; if(m[nums[l]]==0)m.erase(nums[l]); l++; } if(m.size()==k){ cnt=cnt+(r-l+1); } r++; } return cnt; } };
public int subarraysWithKDistinct(int[]nums,int k){ return atMostK(nums,k)-atMostK(nums,k-1); } private int atMostK(int[]nums,int k){ int ans=0;int[]cnt=new int[nums.length+1]; for(int l=0,r=0;r
There is a slight mistake in the code. Please find the fix below
while (mpp.size() > k) {
mpp[nums[l]]--;
if (mpp[nums[l]] == 0)
mpp.erase(nums[l]);
l++;
}
The while condition and the value of L
👍
Java Code
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return subArraysLessThanEqualToK(nums,k)-subArraysLessThanEqualToK(nums,k-1);
}
public int subArraysLessThanEqualToK(int[] nums,int k){
int l=0,r=0,count=0;
HashMap hm = new HashMap();
while(r k){
int rm = nums[l];
hm.put(rm,hm.get(rm)-1);
if(hm.get(rm) == 0){
hm.remove(rm);
}
l++;
}
count += (r-l);
r++;
}
return count;
}
}
its working fine
int n=arr.length,l=0,r=0,count=0;
HashMap map = new HashMap();
while(r k){
map.put(arr[l],map.getOrDefault(arr[l],0)-1);
if(map.get(arr[l]) == 0)
map.remove(arr[l]);
l++;
}
count+=(r-l+1);
r++;
}
return count;
✌✌✌✌
Hey Striver,
I think there are two corrections needed to be done
the while condition should be while (mp.size() > k)
and instead of l-1, it should be incremented to l+1
Thanks!!
You're right
you are correct
Agree 💯
yes
Solved this on my own using learnings from previous lectures, thanks striver :)
fr , just using
Bro u r goated, I was able to solve the problem without looking at the solution thanks to you covering all patterns in the previous problems. Your last few vids helped me in understanding pattern 2 and 3 perfectly.
The explanation of the problem and its solutions from basic to optimized solutions... everything is crystal clear ... truely helpful ... thanks
Today's Leetcode Problem of the Day!!!
thanks Striver..Only because of you i can solve subarray related problems during my college contest.. thank you so much
Hi Striver, I think few corrections required, but I think you have already addressed it, adding in the java reference code, but bro you are awesome.
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return countSubArraysWithGoal(nums, k) - countSubArraysWithGoal(nums, k-1);
}
private int countSubArraysWithGoal(int[] nums, int goal){
if(goal
did this question on my own by learning from previous lecture!! thanks striver bhaiya
Did this question on my own! Feeling so good. The previous lectures helped me
3 Corrections.
1) The inner while condition should be while(mp.size>k)
2) The l=l-1 should be l=l+1 in the inner loop.
1 correction.
1). U mentioned 3 but listed 2
@@Dsa_kabaap
@@Dsa_kabaap XD
Exactly
Solved it completely by myself Thanks Striver
Understood.............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood.....Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Sir There are 2 mistakes thre should be if(map.size()>k)
and l++ in the place of l=l-1.
Bro can predict future. Daily problem solvers can relate.
✅
hahaha yes.i had seen the videoes before this and thought i watch the playlist from this video today,saw daily question,was easy to solve from the previous videoes knowledge and now when i open this playlist again,i see this video hahah
Undeerstood,Thanks Striver for this amazing video.
Solved on my own thanks to you!
i solved this on my own Thanks Striver
Todays lc potd
wowwww mazeeee
yeah!!!
yahh!
Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses.
Would also like your insights on the point :
While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?
00:04 Count the number of subarrays with exactly K different integers.
02:26 Use two pointers and a sliding window to find subarrays with k different integers
04:52 Algorithm for counting total number of subarrays with k different integers
07:12 Using count and frequency to determine valid windows
09:43 Using sliding window to find subarrays with k different integers.
12:16 Creating valid subarrays using 2 Pointers and Sliding Window approach
14:37 Using sliding window to find subarrays with k different integers
17:03 Using the sliding window technique to solve for subarrays with k different integers.
19:17 Discussion on time and space complexity with the use of map data structure.
Crafted by Merlin AI.
Thank you so much bhaiya. I learned a lot from you. Please make a playlist on greedy as well if possible.
Understood. Completed full playlist.
Hii striver, you are wonderful
for helping millions of peoples with your knowledge. ❤❤
This is a gold question
Point to remember: when you are not sure which pointer to move,then try to find different approach like striver used in previous 3 videos
super easy if you have watched the previous videos:
class Solution {
public:
int subarraysWithKDistinct(vector& nums, int k) {
//optimal: (atmost k different) - (atmost k-1 different)
int count1 = 0, count2 = 0, l = 0, r = 0;
unordered_map mpp;
while(r < nums.size()){
mpp[nums[r]]++;
if(mpp.size() > k){
while(mpp.size() > k){
mpp[nums[l]]--;
if(mpp[nums[l]]==0)
mpp.erase(nums[l]);
l++;
}
}
if(mpp.size() k-1){
while(mpp.size() > k-1){
mpp[nums[l]]--;
if(mpp[nums[l]]==0)
mpp.erase(nums[l]);
l++;
}
}
if(mpp.size()
solved hard question on my own by applying the previous questions logic
class Solution {
public:
int helper(vector& nums, int k) {
int left = 0, right = 0;
map map;
int cnt = 0;
while(right < nums.size()) {
map[nums[right]]++;
while(map.size() > k) {
map[nums[left]]--;
if(map[nums[left]] == 0)
map.erase(nums[left]);
left++;
}
cnt += right - left + 1;
right++;
}
return cnt;
}
int subarraysWithKDistinct(vector& nums, int k) {
return helper(nums, k) - helper(nums, k - 1);
}
};
thanks bro
Nice
Was able to solve by myself. Thanks
solved it on my own!
understood !
L9,L10,L11 are the same.
here is java solution code
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
int subK = helper(nums,k);
int sub = helper(nums,k-1);
return subK-sub;
}
private int helper(int nums[], int k){
HashMap map = new HashMap();
int left=0;
int right=0;
int count=0;
while(rightk){
map.put(nums[left],map.get(nums[left])-1);
if(map.get(nums[left])==0){
map.remove(nums[left]);
}
left++;
}
count = count+ right-left+1;
right++;
}
return count;
}
}
in helper function, i think you missed the edge case when k is negative.
if(k < 0){
return 0;
}
Solved before watching the video
I have a question:
When we see that more than k elements are occurring in the subarray, then we remove it from the map
So at max the map will always store (k+1) elements
So the overall space complexity should be O(K)
class Solution {
int subarraywithlessthankequaltok(vector& nums, int k){
int n=nums.size();
int l=0,r=0,cnt=0;
map mpp;
while(rk){
mpp[nums[l]]--;
if(mpp[nums[l]]==0){
mpp.erase(nums[l]);
}
l++;
}
cnt=cnt+(r-l+1);
r++;
}
return cnt;
}
public:
int subarraysWithKDistinct(vector& nums, int k) {
return subarraywithlessthankequaltok(nums,k)-subarraywithlessthankequaltok(nums,k-1);
}
};
striver can you please do problems on in how many ways an array can be splitted based on the given condition
thanks bhaiya
Can we use hashset instead of hashmap ??
UNDERSTOOD;
understood
Striver❤
Why are we missing subarray? Whats the exact reason and which led you to
I can observe but cannot digest mathematically why we are missing them.
Solved
this problem be like : Am I a joke to you 😂
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return subArraysLessThanEqualToK(nums,k)-subArraysLessThanEqualToK(nums,k-1);
}
public int subArraysLessThanEqualToK(int[] nums,int k){
int l=0,r=0,count=0;
HashMap hm = new HashMap();
while(r k){
int rm = nums[l];
hm.put(rm,hm.get(rm)-1);
if(hm.get(rm) == 0){
hm.remove(rm);
}
l++;
}
count += (r-l);
r++;
}
return count;
}
}
Same code in java
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return fun(nums,k)-fun(nums,k-1);
}
int fun(int []nums,int k){
Map frequencyMap = new HashMap();
int left = 0, right = 0, count = 0;
while (right < nums.length) {
frequencyMap.put(nums[right], frequencyMap.getOrDefault(nums[right], 0) + 1);
while (frequencyMap.size() > k) {
frequencyMap.put(nums[left], frequencyMap.get(nums[left]) - 1);
if (frequencyMap.get(nums[left]) == 0) {
frequencyMap.remove(nums[left]);
}
left++;
}
count=count+(right-left+1);
right++;
}
return count;
}
}
Did it myself, But I'm sure it is because i was in the flow of thinking in the sliding window approach, Wouldn't be able to do it if it was randomly thrown at me,
I think the code sippet liitle bit wrong
while(mpp.size() > k){
l=l+1
}
Hey can anyone explain me why space complexity is O(n) I think it should be O(k+1) because as soon as size exceeds 2*(k+1) we are shrinking the window .Please rectify me if I am wrong 😊
Sir please add OPPS playlist.
ok opps
How can we do this in O(N) time instead of O(2N) time ..??❓ 🤔🤔
with sliding window i dont think so
We can use 3 pointer approach for that
Understood
SUPERHERO
class Solution {
public int help(int[] arr, int k) {
int l = 0;
int r = 0;
int cnt = 0;
HashMap mpp = new HashMap();
while (r < arr.length) {
mpp.put(arr[r],mpp.getOrDefault(arr[r],0)+1);
while(mpp.size()>k){
mpp.put(arr[l],mpp.get(arr[l])-1);
if(mpp.get(arr[l])==0){
mpp.remove(arr[l]);
}
l++;}
cnt=cnt+r-l+1;
r++;
}
return cnt;
}
public int subarraysWithKDistinct(int[] arr, int k) {
return help(arr,k)-help(arr,k-1);
}
}
This is similar to lats 2 questions
🎉🎉
mujhse ek question bhi nhi ho rha sliding window ka bus brute force soch pa rha hu lag rha hai coding mere bas ki bat nhi
gives tle for string w exactly k diff chars
i im leithls aka the lethal sujith
Why cant we use set?
We need number and its freq set stores single thing not key value pairs
Me first 😂😂😂
21/01/25❤
I have still the confusion like How (
when sliding window shrinking is happening then at that time we will use k-1 probably this case arises when there is problems ask us to count. Even in the above problem also when we took up to k then we missed few subarrays so at that time we take k-1 . so by subtracting k and (k-1) we get the exact answer
for example, k=3
if we take (i)
and for (ii)
so to find for k==3, if we subtract (i) - (ii) => x=3=k
hope this helps.
@@diwakaranagrawal4673 Thank you for the crystal clear explanation !
@@diwakaranagrawal4673 we can also do
it by (
ok]
can someone please correct my code
class Solution {
public:
int subarraysWithKDistinct(vector& nums, int k) {
int l=0;
int r=0;
int cnt=0;
map m;
while(rk){
m[nums[l]]--;
if(m[nums[l]]==0)m.erase(nums[l]);
l++;
}
if(m.size()==k){
cnt=cnt+(r-l+1);
}
r++;
}
return cnt;
}
};
public int subarraysWithKDistinct(int[]nums,int k){
return atMostK(nums,k)-atMostK(nums,k-1);
}
private int atMostK(int[]nums,int k){
int ans=0;int[]cnt=new int[nums.length+1];
for(int l=0,r=0;r
bruh
check this out
int n=arr.length,l=0,r=0,count=0;
HashMap map = new HashMap();
while(r k){
map.put(arr[l],map.getOrDefault(arr[l],0)-1);
if(map.get(arr[l]) == 0)
map.remove(arr[l]);
l++;
}
count+=(r-l+1);
r++;
}
return count;
understood
Understood
Understood
Understood