Count Distinct Elements in every Window of size k | HashMap Interview Problems | DSA-One Course #29

Hey guys, In this video, We're going to solve a popular HashMap Problem,
Count distinct elements in every window of size k. This problem is asked in Microsoft Interview.

Questions For Practice:

🥳 Join our Telegram Community:

🚀 Follow me on:

💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!

Hashtags:
#anujbhaiya #dsaone

Ignore these tags:

first negative integer in every window of size k
count distinct elements in every window
count distinct elements in every window of size k
count distinct elements in windows of size k
count distinct elements in every sub-array of size k
distinct elements in window of size k
distinct elements in windows of size k hashmaps
first negative number in window size of k
distinct elements in window
distinct elements in window hashmaps
hashmaps distinct elements in window
hashmap interview questions
hashmap interview problem
interview
how hashmap works internally
hashmap in java
hashmap
java interview questions and answers
hashmap internal working in java
coding interview
java collections interview questions
how hashmap works internally in java 8
hashmap implementation
how hashmap works internally in java with example
hashmap interview programs in java
hashmap vs hashtable
core java interview questions
hashmap internals
microsoft interview
microsoft interview questions
microsoft
microsoft interview experience
microsoft software engineer interview
microsoft interview rounds
microsoft mock interview
microsoft interview tips
microsoft phone interview
microsoft interview preparation
microsoft software engineering interview
microsoft software engineer
coding interview
mock interview
programming interview
microsoft coding interview questions
hashmap
hashmap in java
java hashmap
design hashmap
coding challenge
java hashmap tutorial
leetcode design hashmap
design hashmap leetcode
challenge
challenges
code challenge
hashmap interview questions
hashmap in selenium
hashmaps
hashmap vs hashtable
may leetcoding challenge
collection in hashmap
hashmap java
hashmap internals
hashmap vs hashset
custom hashmap
hashmap java example
java hashmap deutsch
hashmap java tutorial
hashmaps java

[AnujBhaiya]

I hope you're doing fine. Please find the Practice problems related to Hashing in the Description box 🙌

[LAVESHGARGPCECS]

Dsa one course plus interview bit questions deadliest combination 🔥🔥

[AmarKumar]

yes...!
Set<Integer> tmp;
for(int i=0; i<arr.length/2+1; i++){
tmp = new HashSet<>();
for(int j=i; j<((i+k)); j++){
tmp.add(arr[j]);
}

}

[jaadui_chirag]

C++ Code:
void countDistinctInK(vector<int> arr, int k) {
unordered_map<int, int> map;
// Handling the 1st K elements
for (int i = 0; i < k; i++)
map[arr[i]] = map[arr[i]] + 1;
cout << map.size() << " ";
for (int i = k; i < arr.size(); i++) {
// removing the (i-k)th element
if (map[arr[i - k]] == 1)
map.erase(arr[i - k]);
else
map[arr[i - k]] = map[arr[i - k]] - 1;
// Adding the nxt value in map
map[arr[i]] = map[arr[i]] + 1;
cout << map.size() << " ";
}
cout << endl;
}

[nupursarkar]

Another approach can be -



public static void countit(int[] arr, int first){
int last = first+3;
if(last==arr.length){
return;
}
Set<Integer> set = new HashSet<>();
for(int i=first;i<=last;i++){
set.add(arr[i]);
}

countit(arr, first+1);
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 1, 3, 1, 1, 3};
int first = 0;
countit(arr, first);

}


ignore the main part....just see the countit func

[Wander.Wheelz]

Bhaiya, I have taken GFG Dsa course still I am always waiting for your your videos 😀

[atharvsingh]

Thank you bhaiya for your efforts...u r doing to much to shape you future!!

[raghavsharma]

Thanks bhaiya just like this add practice problems for every topics easy to hard and main prblms

[mikansenpai]

anuj bhaiya you are an absolute wizard.
matlab aap jadu ki chari ghumate ho aur hum samaj jate hain(:

[notsifat]

apka explanaton is great. love from Bangladesh. I know hindi that's why I have opportunity to learn with this great tutorials. thanks bro

[shubhamjangir]

M Bangalore m top 15 colleges me ek college me 2nd sem me hu aur mere paas ek last attempt baaki h kya karu abhi kyuki mere liye paise bohot matter karte h

[kiranmoura]

Bhaiya I watch your all videos but i am having doubt about what type of laptop i should buy for my btech. So please make a video on that also ...pls as soon as possible

[darkstar_]

Similar approach
static void slidingWindow (int a[], int k)
{
int p=0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < a.length; i++)
{
map.put(a[i], map.getOrDefault(a[i], 0)+1);
if(i>=k-1)
{

if(map.get(a[p])==1)
map.remove(a[p]);
else
map.put(a[p], map.get(a[p])-1);
p=p+1;
}
}
}

[jishnuchakraborty]

Anuj bhaiya can you make a vedio for laptops for coding pls

[mihirsaini]

thank you sir. great explanation as always

[siddharthdwivedi]

Best explanation with the simplest code possible 🎉🎉 thanks a lot brother

[the-abhishek-yadav]

Please Bhaiya make a video on C++ STL 🔥🔥

[shashwatsharma]

What if we traverse the array elements by k and put it into hashset and print the size of it

[rishabhpathak]

can't we use this approach? :
unordered_set<int> s;
vector<int> arr = {1, 2, 2, 1, 3, 1, 1, 3};
for(auto i = 0;i < arr.size()-3; i++)
{
for(int j = i; j < i+4; j++)
s.insert(arr[j]);
cout<<s.size()<<endl;
s.clear();
}

[priyanshujain]

How to write this and previous lecture problem in c++ please help