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

[@pranjuljaiswal1974]

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;

[@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

[@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

[@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.

[@AdityaMaurya-dw3od]

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

[@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

[@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..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@devanshsingh2]

Solved on my own thanks to you!

[@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?

[@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

[@torishi82]

Understood. Completed full playlist.

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

[@Krishna-ti8ys]

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

[@hareshnayak7302]

Undeerstood,Thanks Striver for this amazing video.

[@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.

[@wilhelmrudolphfittig3577]

understood ! L9,L10,L11 are the same.

[@VarunPattikonda]

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

[@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

[@rushidesai2836]

This is a gold question

[@techmatein]

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

[@codeman3828]

Was able to solve by myself. Thanks

[@ashishsinghNITR]

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

[@siddharthsharma7938]

solved it on my own!

[@harsh2518]

this problem be like : Am I a joke to you 😂

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

[@vinaykumarratnala5832]

Solved before watching the video

[@UtkarshWasHereBeforeYou]

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,

[@abhisheksinghdangi5027]

Todays lc potd

[@Mohit_Q]

wowwww mazeeee

[@priyanshkumar17]

yeah!!!

[@yashgaikwad6256]

yahh!

[@VinayQ-]

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

[@N1903-q9t]

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

[@DeadPoolx1712]

UNDERSTOOD;

[@117_mainakpaul2]

Can we use hashset instead of hashmap ??

[@anantsaxena5454]

Solved

[@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 😊

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

[@oyeesharme]

thanks bhaiya

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

[@SHIVAMOJHA21]

SUPERHERO

[@aayushgakhar3525]

gives tle for string w exactly k diff chars

[@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

[@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

[@raushankumargupta7018]

Striver❤

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

[@shivangitiwari2485]

Understood

[@tanujaSangwan]

This is similar to lats 2 questions

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

[@md.sabbirahmed4482]

Sir please add OPPS playlist.

[@akworld2739]

ok opps

[@prasannavenkkatesh1192]

Why cant we use set?

[@sirat_e_islam]

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

[@angeldeveloper]

🎉🎉

[@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 (

[@THOSHI-cn6hg]

ok]

[@leslysujith8032]

i im leithls aka the lethal sujith

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

[@ChillCoderForever]

Me first 😂😂😂

[@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

[@shreshthkushwaha]

bruh

[@pranjuljaiswal1974]

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;

[@SitaRam-m1i]

Understood