L11. Subarray with k different integers | 2 Pointers and Sliding Window Playlist

[@takeUforward]

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

[@ManishKumar-dk8hl]

👍

[@rainyvideo6936]

[@karthik-varma-1579]

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;
}
}

[@rohitn8883]

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

[@priyanshkumar17]

Thanks!!

[@aritralahiri8321]

You're right

[@abhishekrao4853]

you are correct

[@gajananbodhankar1963]

Agree 💯

[@manasranjandas3108]

yes

[@yogeshinba6809]

Solved this on my own using learnings from previous lectures, thanks striver :)

[@tarunyadav6617]

fr , just using

[@AdityaSingh-uy8ms]

The explanation of the problem and its solutions from basic to optimized solutions... everything is crystal clear ... truely helpful ... thanks

[@anubhavpal1071]

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.

[@soumyajit_0]

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.

[@Dsa_kabaap]

1 correction.
1). U mentioned 3 but listed 2

[@pruthvinarayana9568]

@@Dsa_kabaap

[@trailblazer555]

Today's Leetcode Problem of the Day!!!

[@data-fi4hl]

did this question on my own by learning from previous lecture!! thanks striver bhaiya

[@AdityaMaurya-dw3od]

Did this question on my own! Feeling so good. The previous lectures helped me

[@HimanshuYadav-fg8sm]

Sir There are 2 mistakes thre should be if(map.size()>k)
and l++ in the place of l=l-1.

[@stith_pragya]

Understood.............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@stith_pragya]

Understood.....Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@RoshanPathak-i4l]

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

[@AbhishekKumar-vu3cp]

i solved this on my own Thanks Striver

[@Cool96267]

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?

[@hareshnayak7302]

Undeerstood,Thanks Striver for this amazing video.

[@Krishna-ti8ys]

Thank you so much bhaiya. I learned a lot from you. Please make a playlist on greedy as well if possible.

[@devanshsingh2]

Solved on my own thanks to you!

[@torishi82]

Understood. Completed full playlist.

[@wilhelmrudolphfittig3577]

understood !
L9,L10,L11 are the same.

[@rushidesai2836]

This is a gold question

[@117_mainakpaul2]

Can we use hashset instead of hashmap ??

[@siddharthsharma7938]

solved it on my own!

[@techmatein]

solved hard question on my own by applying the previous questions logic

[@RajanKumar-vf7op]

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);
}
};

[@abhishekrao4853]

thanks bro

[@harshsingh357]

Nice

[@N1903-q9t]

striver can you please do problems on in how many ways an array can be splitted based on the given condition

[@codeman3828]

Was able to solve by myself. Thanks

[@VinayQ-]

I think the code sippet liitle bit wrong
while(mpp.size() > k){
l=l+1
}

[@oyeesharme]

thanks bhaiya

[@vinaykumarratnala5832]

Solved before watching the video

[@abhisheksinghdangi5027]

Todays lc potd

[@Mohit_Q]

wowwww mazeeee

[@priyanshkumar17]

yeah!!!

[@yashgaikwad6256]

yahh!

[@anantsaxena5454]

Solved

[@shreyxnsh.14]

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()

[@ashishsinghNITR]

Hii striver, you are wonderful
for helping millions of peoples with your knowledge. ❤❤

[@DeadPoolx1712]

UNDERSTOOD;

[@knowthrvdo]

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.

[@RadheShyam33455]

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 😊

[@aayushgakhar3525]

gives tle for string w exactly k diff chars

[@varrnitjaiswal1484]

Bro can predict future. Daily problem solvers can relate.

[@kenil98]

✅

[@taqimustafa7665]

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

[@foziezzz1250]

How can we do this in O(N) time instead of O(2N) time ..??❓ 🤔🤔

[@sid_ofc17]

with sliding window i dont think so

[@ayushmishra6575]

We can use 3 pointer approach for that

[@shivangitiwari2485]

Understood

[@prasannavenkkatesh1192]

Why cant we use set?

[@sirat_e_islam]

We need number and its freq set stores single thing not key value pairs

[@md.sabbirahmed4482]

Sir please add OPPS playlist.

[@akworld2739]

ok opps

[@niteshkumarjha7914]

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;
}
}

[@jitinroy2246]

in helper function, i think you missed the edge case when k is negative.
if(k < 0){
return 0;
}

[@raushankumargupta7018]

Striver❤

[@akworld2739]

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

[@sksanoyarali1067]

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);
}
};

[@tanujaSangwan]

This is similar to lats 2 questions

[@THOSHI-cn6hg]

ok]

[@HimanshuYadav-fg8sm]

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;
}
}

[@imdavinder]

I have still the confusion like How (

[@teja1184]

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

[@diwakaranagrawal4673]

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.

[@imdavinder]

@@diwakaranagrawal4673 Thank you for the crystal clear explanation !

[@TarunKumar-cn6in]

@@diwakaranagrawal4673 we can also do
it by (

[@angeldeveloper]

🎉🎉

[@leslysujith8032]

i im leithls aka the lethal sujith

[@ManishKumar-dk8hl]

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);

}
}

[@karthik-varma-1579]

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;
}
}

[@ChillCoderForever]

Me first 😂😂😂

[@smitasingh8942]

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;
}
};

[@shreshthkushwaha]

bruh

[@dayashankarlakhotia4943]

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