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
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
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?
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
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 😊
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; } }
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; } };
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);
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
![KSI - Thick Of It (feat. Trippie Redd) [Official Music Video]](http://i.ytimg.com/vi/At8v_Yc044Y/mqdefault.jpg)
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;
}
}
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.
did this question on my own by learning from previous lecture!! thanks striver bhaiya
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
Today's Leetcode Problem of the Day!!!
Did this question on my own! Feeling so good. The previous lectures helped me
Sir There are 2 mistakes thre should be if(map.size()>k)
and l++ in the place of l=l-1.
The explanation of the problem and its solutions from basic to optimized solutions... everything is crystal clear ... truely helpful ... thanks
Understood.............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood.....Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
Solved on my own thanks to you!
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?
Undeerstood,Thanks Striver for this amazing video.
Understood. Completed full playlist.
understood !
L9,L10,L11 are the same.
Todays lc potd
wowwww mazeeee
yeah!!!
yahh!
This is a gold question
solved hard question on my own by applying the previous questions logic
Thank you so much bhaiya. I learned a lot from you. Please make a playlist on greedy as well if possible.
Was able to solve by myself. Thanks
Solved before watching the video
thanks bhaiya
I think the code sippet liitle bit wrong
while(mpp.size() > k){
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
Can we use hashset instead of hashmap ??
striver can you please do problems on in how many ways an array can be splitted based on the given condition
Solved
Hii striver, you are wonderful
for helping millions of peoples with your knowledge. ❤❤
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 😊
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
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
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
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;
}
}
gives tle for string w exactly k diff chars
Understood
Why cant we use set?
We need number and its freq set stores single thing not key value pairs
Striver❤
This is similar to lats 2 questions
Sir please add OPPS playlist.
ok opps
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);
}
};
i im leithls aka the lethal sujith
🎉🎉
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;
}
}
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]
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;
}
}
Me first 😂😂😂
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;
}
};
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);
}
}
bruh
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