You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.
Note:
1. The size of ‘ARR’ will always be greater than or equal to the ‘K’.
2. Here window refers to a subarray of ‘ARR’. Hence ‘K’ sized window means a subarray of size ‘K’.
3. You are not required to print the output explicitly. It has already been taken care of. Just implement the function and return an array of the count of all distinct elements in the ‘K’ size window.
Example
Consider ARR = [ 1, 2, 1, 3, 4, 2, 3 ] and K = 3.
As per the given input, we have a sequence of numbers of length 7, and we need to find the number of distinct elements present in all the windows of size 3.
Window-1 has three elements { 1, 2, 1 } and only two elements { 1, 2 } are distinct because 1 is repeating two times.
Window-2 has three elements { 2, 1, 3 } and all three elements are distinct { 2, 1, 3 }.
Window-3 has three elements { 1, 3, 4 } and all three elements are distinct { 1, 3, 4 }.
Window-4 has three elements { 3, 4, 2 } and all three elements are distinct { 3, 4, 2 }.
Window-5 has three elements { 4, 2, 3 } and all three elements are distinct { 4, 2, 3 }.
Hence, the count of distinct elements in all K sized windows is { 2, 3, 3, 3, 3 }.
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and ‘K’, denoting the number of elements in the array and the size of the window.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
For each test case, print an array that contains the number of distinct elements in all ‘K’ size windows, and the count of distinct elements must be from the left to the right window.
Print the output of each test case in a separate line.
1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= K <= N
1 <=ARR[i] <= 10 ^ 9
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, ‘K’ denotes the size of the window, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'.
Time limit: 1 second
2
7 4
1 2 1 3 4 2 3
5 3
1 1 2 1 3
3 4 4 3
2 2 3
Test Case 1:
Window-1 has four elements { 1, 2, 1, 3 } and only three elements { 1, 2, 3 } are distinct because 1 is repeating two times.
Window-2 has four elements { 2, 1, 3, 4 } and all four elements { 2, 1, 3, 4 } are distinct.
Window-3 has four element { 1, 3, 4, 2 } and all four elements { 1, 3, 4, 2 } are distinct.
Window-4 has four element { 3, 4, 2, 3 } and only three elements { 3, 4, 2 } are distinct because 3 is repeating two times.
Hence, the count of distinct elements in all windows is { 3, 4, 4, 3}.
Test case 2:
Window-1 has three elements { 1, 1, 2 } and only two elements { 1, 2 } are distinct because 1 is repeating two times.
Window-2 has three elements { 1, 2, 1 } and only two elements { 2, 1 } are distinct.
Window-3 has three elements { 2, 1, 3 } and all three elements { 2, 1, 3 } are distinct.
Hence, the count of distinct elements in all windows is { 2, 2, 3 }.
2
4 1
2 3 1 2
5 2
2 2 3 2 1
1 1 1 1
1 2 2 2
Try to find the total number of distinct elements for every window.
The basic idea of this approach is to check every window of size K and count the number of distinct elements in each window.
Our approach will be to maintain an array answer, which will store the count of the distinct elements in every window. We will traverse through each window and find the number of distinct elements in the current window.
We will return the array answer.
Algorithm:
O((N - K) * (K ^ 2)), Where N denotes the number of elements in the array, and K denotes the size of the window.
We are doing N - K iterations, and in each iteration, it takes O(K ^ 2) time to count the number of distinct elements in the window. Hence, the overall Time Complexity = O(N - K) * (K ^ 2) = O((N - K) * (K ^ 2)).
O(1).
Constant space is being used. Hence, the overall Space Complexity is O(1).
All tags
Sort by
Interview problems
Java Solution
public static ArrayList<Integer> countDistinctElements(ArrayList<Integer> arr, int k) {
// Write your code here
int l = 0;
int r = 0;
int n = arr.size();
ArrayList<Integer> list = new ArrayList<>();
HashMap<Integer,Integer> map = new HashMap<>();
while(r<n)
{
map.put(arr.get(r),map.getOrDefault(arr.get(r), 0)+1);
if(r>=k-1)
{
while(r-l+1>k)
{
int t = arr.get(l);
map.put(t, map.get(t)-1);
if(map.get(t)==0)
map.remove(t);
l++;
}
list.add(map.size());
}
r++;
}
return list;
}
Interview problems
unordered_map (better than 99.98%) in easy way
#include <bits/stdc++.h>
vector<int> countDistinctElements(vector<int> &arr, int k)
{
vector<int> v;
unordered_map<int, int> mp;
int n = arr.size(), i=0, j=0;
while(j<n){
mp[arr[j]]++;
if(j-i+1==k){
v.push_back(mp.size());
if(mp[arr[i]] == 1) mp.erase(arr[i]);
else mp[arr[i]]--;
i++;
}
j++;
}
return v;
}
Interview problems
Sliding Window Concept
#include <bits/stdc++.h>
vector<int> countDistinctElements(vector<int> &arr, int k)
{
unordered_map<int,int> map;
vector<int> ans;
int n=arr.size();
int l=0,r=0;
while(r < n)
{
map[arr[r]]++;
if(r-l + 1 == k)
{
ans.push_back(map.size());
if(map[arr[l]] == 1)
{
map.erase(arr[l]);
}
else
{
map[arr[l]]--;
}
l++;
}
r++;
}
return ans;
}
Interview problems
C++ Hashmap Easy to Understand Solution
#include <bits/stdc++.h>
vector<int> countDistinctElements(vector<int> &arr, int k)
{
unordered_map<int,int> mp;
vector<int> res;
int n = arr.size();
// first creating a window of k size
for(int i =0; i<k; i++)
{
mp[arr[i]]++;
}
res.push_back(mp.size());
// now traversing all left elements
for(int i =k; i<n; i++)
{
// dealing with the (i-k)th element
// if the frequency is 1,
// then that element is not part of current window
// and hence should be removed
if(mp[arr[i-k]] == 1)
mp.erase(arr[i-k]);
// if frequency is greater than 1
// then that element is part of the current window
// and hence only frequency should be decremented
else
mp[arr[i-k]]--;
// adding the current element to the map
mp[arr[i]]++;
// pushing the count of distinct elements for the current
// k size window
res.push_back(mp.size());
}
return res;
}
Interview problems
C++ solution
#include <bits/stdc++.h>
vector<int> countDistinctElements(vector<int> &arr, int k)
{
vector<int>v;
int n=arr.size();
unordered_map<int,int>m;
int ct=0;
for(int i=0;i<k;i++)
{
if(m[arr[i]]==0) ct++;
m[arr[i]]++;
}
v.push_back(ct);
for(int i=k;i<n;i++)
{
if(m[arr[i-k]]==1) ct--;
m[arr[i-k]]--;
if(m[arr[i]]==0) ct++;
m[arr[i]]++;
v.push_back(ct);
}
return v;
}
Interview problems
Easy python solution
def countDistinctElements(arr, k):
lis = []
for i in range(len(arr)-k+1):
lis.append(len(set(arr[i: i+k])))
return lis
Interview problems
C++ Solution
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> countDistinctElements(vector<int> &arr, int k) {
vector<int> ans;
unordered_map<int, int> freqMap;
int distinctCount = 0;
// Initialize the frequency map with the first 'k' elements
for (int i = 0; i < k; ++i) {
if (freqMap[arr[i]] == 0) {
distinctCount++;
}
freqMap[arr[i]]++;
}
ans.push_back(distinctCount);
// Slide the window over the rest of the elements
for (int i = k; i < arr.size(); ++i) {
// Remove the element going out of the window
if (freqMap[arr[i - k]] == 1) {
distinctCount--;
}
freqMap[arr[i - k]]--;
// Add the new element coming into the window
if (freqMap[arr[i]] == 0) {
distinctCount++;
}
freqMap[arr[i]]++;
// Store the current count of distinct elements
ans.push_back(distinctCount);
}
return ans;
}
Interview problems
C++ solution
#include <bits/stdc++.h>
vector<int> countDistinctElements(vector<int> &a, int k)
{
// Write your code here
unordered_map<int,int>m;
vector<int>r;
int n=a.size();
for(int i=0;i<k;i++) m[a[i]]++;
r.push_back(m.size());
for(int i=1;i<=n-k;i++)
{
if(m[a[i-1]]==1) m.erase(a[i-1]);
else m[a[i-1]]--;
m[a[i+k-1]]++;
r.push_back(m.size());
}
return r;
}
Interview problems
cpp sol
#include <bits/stdc++.h>
using namespace std;
void adda(int ele, unordered_map<int, int>&fre){
if(fre.find(ele)==fre.end()){
fre[ele]=1;
}
else{
fre[ele]++;
}
}
void ramba(int ele, unordered_map<int, int>&fre){
if(fre.find(ele)!=fre.end()){
if(fre[ele]==1){
fre.erase(ele);
}
else{
fre[ele]--;
}
}
else{
return;
}
}
vector<int> countDistinctElements(vector<int> &arr, int k)
{
// Write your code here
unordered_map<int, int>fre;
for(int i=0; i<k-1; i++){
adda(arr[i], fre);
}
vector <int> ans;
for(int i=0, e=k-1; e<arr.size(); ++i, ++e){
adda(arr[e], fre);
ans.push_back(fre.size());
ramba(arr[i], fre);
}
return ans;
}
Interview problems
Using sliding window
import java.util.* ;
import java.io.*;
public class Solution {
public static ArrayList<Integer> countDistinctElements(ArrayList<Integer> arr, int k) {
Map<Integer,Integer> map = new HashMap<>();
ArrayList<Integer> result = new ArrayList<>();
int i=0,j=0;
//sliding window problem
while(j<arr.size()){
int window = j-i+1;
int elemAtJ = arr.get(j);
map.put(elemAtJ,map.getOrDefault(elemAtJ, 0) + 1);
if(window == k){
result.add(map.size());
int elemAtI = arr.get(i);
map.put(elemAtI, map.get(elemAtI) - 1);
if(map.get(elemAtI) == 0){
map.remove(elemAtI);
}
i++;
}
j++;
}
return result;
}
}
