Subarrays with distinct integers #Interviewbit C++ Code Explanation Intuition

Given an array A of positive integers,call a (contiguous,not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly B.

(For example: [1, 2, 3, 1, 2] has 3 different integers 1, 2 and 3)

Return the number of good subarrays of A.

Problem Constraints

Input Format
The first argument given is the integer array A.

The second argument given is an integer B.

Output Format
Return an integer denoting the number of good subarrays of A.

Example Input
Input 1:

A = [1, 2, 1, 2, 3]
B = 2
Input 2:

A = [1, 2, 1, 3, 4]
B = 3

Example Output
Output 1:

7
Output 2:

3

Example Explanation
Explanation 1:

Subarrays formed with exactly 2 different integers: [1, 2], [2, 1], [1, 2], [2, 3], [1, 2, 1], [2, 1, 2], [1, 2, 1, 2].
Explanation 2:

Subarrays formed with exactly 3 different integers: [1, 2, 1, 3], [2, 1, 3], [1, 3, 4].

[phantom]

A note to myself (CPP implementation)

//WHY WE NEED THIS HELPER() fn AGAIN
//When you notice,
//We HAVE to find exactly k distinct vals
//We know atmost one is easier.
//Doing Atmost Technique (k (-) k-1)
//we get to our answer efficiently

//As for counting total no of subarr
//why we doing count += (j-i+1) ?
//cuz if we do a dry run, we observe this only

#include <unordered_map>
int helper(vector<int>&arr, int n, int k){
//This is basically
//finding total subarr with atmost k distinct int
unordered_map<int, int> mp;
int i=0, j=0, count=0;
while(j<n){
mp[arr[j]]++;
if(mp.size()<=k){
count += j-i+1;
}
else{
while(mp.size()>k){
mp[arr[i]]--;
if(mp[arr[i]]==0) mp.erase(arr[i]);
i++;
}
count+=j-i+1;
}
j++;
}
return count;
}
int &arr, int n, int k)
{
return helper(arr, n, k)-helper(arr, n, k-1);
}

[muditkhandelwal]

I watched neetcode video but couldn't understand the solution. This video saved the day. Thanks.

[amanjain]

This is one of the clearest and most detailed explanations for this problem. Kudos to you Alisa.

[piragna]

I hav reached minute 1:42 and I am alreazy amazed because of the expalantion, thank you su much! you´re amazing!

[PRINCEKUMAR-mltb]

Just Phenomenal! One of the best explanation of this problem.

[Yash]

Alisha, good work, you're the only one who not only describes the intuition but also explains why and how it works! 💯

[shashankbankar]

God level explained, I simply can't thank you enough, please continue making such videos, you are awesome..

[kusumjoshi]

This is one of the best explanations I have seen soo far.

[Anuragkumar-dcdr]

what an explanation! you have solved problem logically. And also understand concept behind writing every line of code . Thank You Alisha

[krishnasingh]

Brilliant explanation Ma'am. I was stuck on this Question for a while but the way you dry ran the code helped me understand the code. And i was able to code it myself🙏🏽⭐

[saketmehta]

One of the best explanation for this hard problem!
Watch this video guys you'll be able to solve many problems of sliding window!
Kudos alisha! Hats OFF!

[rutikdeshmukh]

wowww, very intutive technique and detailed explanation!! thanks

[technologicalvivek]

Nice explanation.Thank you didi .I got stuff to solve this question.After spending a lot of time.Thanks finally I understand the correct approach behind this question.

[omkarkawatgi]

Yar ye hota hai explanation... bahut sahi ! Thank you ...

[awesomesheen]

Amazing intuition! Best video on this question I have seen!

[Sanjaysview]

Yo, that was smooth explanation. Thanks Sister!!

[preethi]

mam ur explanation is awesome .thank u

[anuragtiwari]

Came for 1 question learnt 2. Excellent work, wish ur channel to explode 🔥

[KomedyReels]

wooow, in leetcode this question is marked as hard, i spent whole day to figure out how to solve this but i failed, after seeing your approach, i felt like this is "this one so simple", Thank you so much for the vd and ur explanation is really good, I am gonn post this vd on leetcode😅

[niteshgupta]

Amazing explanation. Was struggling on this question from so many hours.