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
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
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);
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
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; } }
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.
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.
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
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 💯
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
Solved this on my own using learnings from previous lectures, thanks striver :)
fr , just using
did this question on my own by learning from previous lecture!! thanks striver bhaiya
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
Did this question on my own! Feeling so good. The previous lectures helped me
Understood.............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Undeerstood,Thanks Striver for this amazing video.
Todays lc potd
wowwww mazeeee
yeah!!!
yahh!
Was able to solve by myself. Thanks
Solved before watching the video
gives tle for string w exactly k diff chars
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
Striver❤
Why cant we use set?
We need number and its freq set stores single thing not key value pairs
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);
}
};
Sir please add OPPS playlist.
ok opps
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 im leithls aka the lethal sujith
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 (
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);
}
}
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
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;
}
}
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;
}
}
Today's Leetcode Problem of the Day!!!
I think the code sippet liitle bit wrong
while(mpp.size() > k){
l=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.
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 😊
Understood.....Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
This is similar to lats 2 questions
understood !
L9,L10,L11 are the same.
Solved
solved hard question on my own by applying the previous questions logic
thanks bhaiya
Me first 😂😂😂
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
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.
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?
Understood. Completed full playlist.
striver can you please do problems on in how many ways an array can be splitted based on the given condition
Thank you so much bhaiya. I learned a lot from you. Please make a playlist on greedy as well if possible.
This is a gold question
Solved on my own thanks to you!
Understood
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
bruh
🎉🎉
Hii striver, you are wonderful
for helping millions of peoples with your knowledge. ❤❤