Good solution! Two things I noticed: One, we can use an 'if' statement instead of a 'while' for the 'while len(count) < k' line since at any point in the array, the max length of count will be k+1. Two, l_near always points to an element with exactly one occurrence, so in that 'while' loop, we don't actually have to decrement it - we can always just pop it right away. So, we can just simplify the code with: if len(count) > k: count.pop(nums[l_near]) l_near += 1 l_far = l_near
Yes, this is right! Good observation!!. I had the same question when I was going through a scenario and leftNear will always point to an element whose count is 1.
You improved sooo much compared to past tutorials, in these new tutorials, you including your thought process, which matches with all of our thought process at early stages of finding the solution for new problems and also explained why it won't work. Thank you soo much for your contribution to ever lasting best tutorials on youtube! Best of Luck!!
Another way to solve is like this - Subarrays with "EXACTLY" K Different Integers = Subarrays with 5 Subarrays So, subarrays with Exactly K different Integers = 12 - 5 => 7 So, we can iterate over the array twice, once to find number of subarrays with at most K different integers, and once to find the Number of subarrays with at most K - 1 different integers. And for both, we will use Sliding Window technique. In this way, the overall time complexity will be O(2N) => O(N) Here is my explanation on Leetcode for the same -> leetcode.com/problems/subarrays-with-k-different-integers/discuss/2582425/Python-Sliding-Window-%2B-Dictionary This is a technique we can use on other Sliding Window Problems as well which ask us to find subarrays with "EXACTLY" K something. For example this problem -> leetcode.com/problems/binary-subarrays-with-sum/ Or this problem -> leetcode.com/problems/count-number-of-nice-subarrays/
One thing to take care of is that the while loop which checks the length of the hash map should always come in first. I think that maybe this is because of the fact that the priority to check the length of the hash map is simply higher than the priority to check if we have more than one occurrence of a particular number.
I almost solved this one on my own. Git to the 3 pointers idea but just couldnt work out the fine details. Ddnt help that it was like midnight lol Exciting because I think this was the first hard I almost solved on my own.
C++ implementation : ``` class Solution { public: int subarraysWithKDistinct(vector& nums, int k) { unordered_map freq; int len = nums.size(), leftNear=0,leftFar=0, distinct=0, res=0; for(int right=0;rightk){ // left pointer will always point to the element whose frequency is 1. // while(distinct>k){ freq[nums[leftNear]]--; // if(!freq[nums[leftNear]]) // not needed as left will always point to the element whose frequency is 1. distinct--; leftNear++; leftFar = leftNear;// will update more times than we need. but it's okay } while(freq[nums[leftNear]]>1){ freq[nums[leftNear]]--; leftNear++; } if(distinct==k) res += leftNear-leftFar +1; } return res; } }; ```
i dont understand how people come up with getting no of sub arrays with two pointer like subtracting them we get subarrays I stuck in thinking but I know it works and know why does it work but still I can code myself in new problem for this too I thought 3 pointer but don't know how do make subarrays and over complicated taking 2 hashmaps and shifting farpointer and can even pass the base cases
class Solution: def subarraysWithKDistinct(self, nums: List[int], k: int) -> int: def subA(nums,k): d = defaultdict(int) res = 0 l = 0 for r in range(len(nums)): d[nums[r]] += 1 while len(d) > k: d[nums[l]] -= 1 if d[nums[l]] == 0: del d[nums[l]] l += 1 res += r - l + 1 return res return subA(nums,k)-subA(nums,k-1)
Is it true that for any subarray problems, an approach with window ending at a given index always works efficiently (and so, we never need to think about the alternative approach where the window starts at some index )?
In the scenario where len(count)> k, I see we aren't explicitly deleting all elements between l_far and l_near before the two pointers become equal. Is it implicitly being handled somehow? Ideally all the elements to the left of l_far should be made removed from hashmap.
Now that I’ve started to think that I begin to understand that “sliding window” thing, Neetcode says: “Ok, now we are gonna have two left pointers…”:)))
NeetCode, pls explain 12:27 where from the result=6 is? Firstly, 1-0+1 = 2(6-2=4). Ok. Further 2 - 0 + 1 != 4 🤔 Other explanation is ok. But this moment I can’t catch …
class Solution { public int subarraysWithKDistinct(int[] nums, int k) { HashMap map = new HashMap(); int res = 0; int l_far = 0, l_near = 0, r = 0; while (r < nums.length) { map.put(nums[r], map.getOrDefault(nums[r], 0) + 1); while (map.size() > k) { map.put(nums[r], map.getOrDefault(nums[r], 0) - 1); if (map.get(nums[r]) == 0) { map.remove(nums[r]); } if(l_near < nums.length ) l_near+=1; l_far = l_near; } while ( map.get(nums[l_near]) != null || map.get(nums[l_near]) > 1) { map.put(nums[r], map.getOrDefault(nums[r], 0) - 1); if(l_near < nums.length ) l_near+=1; } if (map.size() == k) { res += (l_near - l_far + 1 ); } r++; } return res; } } i am getting error can any 1 point out why and how to solvey them
Good solution! Two things I noticed:
One, we can use an 'if' statement instead of a 'while' for the 'while len(count) < k' line since at any point in the array, the max length of count will be k+1.
Two, l_near always points to an element with exactly one occurrence, so in that 'while' loop, we don't actually have to decrement it - we can always just pop it right away.
So, we can just simplify the code with:
if len(count) > k:
count.pop(nums[l_near])
l_near += 1
l_far = l_near
Yes, this is right! Good observation!!. I had the same question when I was going through a scenario and leftNear will always point to an element whose count is 1.
near decade of algorithm solving, this is the first time i ever heard of 3ptr sliding window... cool
Wow, sliding window technique on steroids... Great explanation, thanks!
You improved sooo much compared to past tutorials, in these new tutorials, you including your thought process, which matches with all of our thought process at early stages of finding the solution for new problems and also explained why it won't work. Thank you soo much for your contribution to ever lasting best tutorials on youtube! Best of Luck!!
you are able to convey sliding 3 ptr window in the most intuitive way, thank you!
This can also be solved with one trick and simple 2 pointers
You'll realise it is easier to find all subarrays with
Thats a nice trick! 2 times sliding window to find all sub arrays with
You mean subtract
@@upamanyumukharji3157 you are correct.
Another way to solve is like this -
Subarrays with "EXACTLY" K Different Integers = Subarrays with 5 Subarrays
So, subarrays with Exactly K different Integers = 12 - 5 => 7
So, we can iterate over the array twice, once to find number of subarrays with at most K different integers, and once to find the Number of subarrays with at most K - 1 different integers. And for both, we will use Sliding Window technique.
In this way, the overall time complexity will be O(2N) => O(N)
Here is my explanation on Leetcode for the same -> leetcode.com/problems/subarrays-with-k-different-integers/discuss/2582425/Python-Sliding-Window-%2B-Dictionary
This is a technique we can use on other Sliding Window Problems as well which ask us to find subarrays with "EXACTLY" K something.
For example this problem -> leetcode.com/problems/binary-subarrays-with-sum/
Or this problem -> leetcode.com/problems/count-number-of-nice-subarrays/
One thing to take care of is that the while loop which checks the length of the hash map should always come in first.
I think that maybe this is because of the fact that the priority to check the length of the hash map is simply higher than the priority to check if we have more than one occurrence of a particular number.
I almost solved this one on my own. Git to the 3 pointers idea but just couldnt work out the fine details. Ddnt help that it was like midnight lol
Exciting because I think this was the first hard I almost solved on my own.
Thank you for your efforts to provide quality tutorials/solutions. Truly appreciated!
C++ implementation :
```
class Solution {
public:
int subarraysWithKDistinct(vector& nums, int k) {
unordered_map freq;
int len = nums.size(), leftNear=0,leftFar=0, distinct=0, res=0;
for(int right=0;rightk){ // left pointer will always point to the element whose frequency is 1.
// while(distinct>k){
freq[nums[leftNear]]--;
// if(!freq[nums[leftNear]]) // not needed as left will always point to the element whose frequency is 1.
distinct--;
leftNear++;
leftFar = leftNear;// will update more times than we need. but it's okay
}
while(freq[nums[leftNear]]>1){
freq[nums[leftNear]]--;
leftNear++;
}
if(distinct==k)
res += leftNear-leftFar +1;
}
return res;
}
};
```
The fact that companies ask this in real interviews
this explanation is way more intuitive than the editorial
Nice! But I think a simpler way would be to use the 'At Most k, At Most k - 1' technique right?
correct
Yes it is more intuitive
Yup
true, but this is faster since it's one pass only
@@MustafaAli-hr2vp it doesn’t matter. Both are O(n)
Great way of explaining the sliding window problem with three pointers.
Thank you! Great algorithm with 3 pointers 👍👍
atMost(k) - atMost(k-1) is way easier to code and understand but I really appreciate this other solution because I learned a new pattern :)
Neetcode >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Everyone
Great job!! I've definitely heard about this 3 ptr technique, however forget. Thanks a lot for reminding!!
the best leetcode videos you can find
Great solution. I don't know how you come up with this.
Thank you for such video. With your explanation, this hard problem looks like an easy one!
After 4 hours I gave up on this problem and came here. After watching it I think that I would answer by myself if I spent a month.
all thanks to you i was capable of solving this problem using the hashmap last index trick and a sliding window
wow even the same 3ptrs technique
Got asked this in Uber telephonic. Got an O(n^2) solution with sliding window. Not possible to solve it in O(n) without looking at it beforehand.
interesting solution @NeetCodeIO.Well done!!!
i dont understand how people come up with getting no of sub arrays with two pointer
like subtracting them we get subarrays
I stuck in thinking but I know it works and know why does it work but still I can code myself in new problem
for this too I thought 3 pointer but don't know how do make subarrays and over complicated taking 2 hashmaps and shifting farpointer and can even pass the base cases
This was just wow man. Loved it 💯
Beautiful explanation as always. Thank you
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def subA(nums,k):
d = defaultdict(int)
res = 0
l = 0
for r in range(len(nums)):
d[nums[r]] += 1
while len(d) > k:
d[nums[l]] -= 1
if d[nums[l]] == 0:
del d[nums[l]]
l += 1
res += r - l + 1
return res
return subA(nums,k)-subA(nums,k-1)
your skills are topnotch
Damn! Thanks for making the explanation so simple! I understood it in one go.
another easy way, atmost(k) - atmost(k-1) , atmost(k) can be easily done by sliding window
Is it true that for any subarray problems, an approach with window ending at a given index always works efficiently (and so, we never need to think about the alternative approach where the window starts at some index )?
atMost trick neetcode did few videos ago for Leetcode 930. Binary Subarrays With Sum make implementation easy.
damn I forgot about 3 pointers sliding window technique, gorgeous solution as always
Thanks to you and hints I was able to solve today's hard question (2444)
In the scenario where len(count)> k, I see we aren't explicitly deleting all elements between l_far and l_near before the two pointers become equal. Is it implicitly being handled somehow? Ideally all the elements to the left of l_far should be made removed from hashmap.
I used to count subarry with less than equal to k and also less than equal to k -1 and then subtract the result to get the answer
for someone who codes in cpp
here is the solution
class Solution {
public:
int subarraysWithKDistinct(vector& nums, int k) {
int n = nums.size();
int l_far = 0,l_near = 0,r = -1,ans = 0;
unordered_map umap;
while(++r < n){
umap[nums[r]]++;
while(umap.size() > k){
umap[nums[l_near]]--;
if(umap[nums[l_near]] == 0) umap.erase(nums[l_near]);
l_near++;
l_far = l_near;
}
while(umap[nums[l_near]] > 1){
umap[nums[l_near]]--;
l_near++;
}
if(umap.size() == k){
ans = ans+(l_near-l_far+1);
}
}
return ans;
}
};
why you initialized r=-1?
@@tarifahmed4956 i used it to make pre increment work in first while loop.
U can also use r=0 and increment r at the end of first while loop
Solved it !
Nice Explanation!!
which app/website do you use for drawing?
Now that I’ve started to think that I begin to understand that “sliding window” thing, Neetcode says: “Ok, now we are gonna have two left pointers…”:)))
hi neetcode, where r videos for todays contest and DCC?
I just realised 2019 was 5 years ago!
Yeah I'm slowly becoming a boomer. I still think of myself as a newgrad
great one pass solution, is (k) - (k-1) solution good enough for interview? I can only come up with that solution
How did you come with the counting part?
Wow, cool cool cool!
did you write code in python on google interview ?
yes
Maybe I’m spending too much time doing leetcode…
If we swap While loops inside a for loop it FAILSSSS why?????
anyone have a list of sliding 3 ptr window problems?
Count Vowel Substrings of a String is a good one
NeetCode, pls explain 12:27 where from the result=6 is? Firstly, 1-0+1 = 2(6-2=4). Ok. Further 2 - 0 + 1 != 4 🤔
Other explanation is ok. But this moment I can’t catch …
Position One: FAR.position = NEAR.position = 0 | 0-0+1=1 (count = 1)
Position Two: FAR.position = 0, NEAR.position = 1 | 1-0+1=2 (incrementing count by 2 gives us 3)
Position Three: FAR.position = 0, NEAR.position = 2 | 2-0+1=3 (incrementing count further by 3 gives us 6)
@@weihyac . Thank you for explanation.
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
HashMap map = new HashMap();
int res = 0;
int l_far = 0, l_near = 0, r = 0;
while (r < nums.length) {
map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
while (map.size() > k) {
map.put(nums[r], map.getOrDefault(nums[r], 0) - 1);
if (map.get(nums[r]) == 0) {
map.remove(nums[r]);
}
if(l_near < nums.length ) l_near+=1;
l_far = l_near;
}
while ( map.get(nums[l_near]) != null || map.get(nums[l_near]) > 1) {
map.put(nums[r], map.getOrDefault(nums[r], 0) - 1);
if(l_near < nums.length ) l_near+=1;
}
if (map.size() == k) {
res += (l_near - l_far + 1 );
}
r++;
}
return res;
}
} i am getting error can any 1 point out why and how to solvey them
where is todays's video
While else also works
First