Find the count of distinct elements in every subarray of size k

Posted in

Find the count of distinct elements in every subarray of size k

Vinay Khatri
Last updated on June 8, 2022

    Problem

    Given an array of integers and a number k . Find the count of distinct elements in every subarray of size k in the array.

    Sample Input

    N = 3  k = 2
    [4, 1, 1]

    Sample Output

    2 1

    Explanation

    [4,1] is the first subarray and [1,1] is second

    Approach

    We can use Hashmap to solve this problem. Initially, we can keep the count of each element in the first subarray in hashmap. The size of the hashmap will be the number of distinct elements in the first subarray. Now, we slide the window by 1 and decrement the frequency of the starting element of the current window and increment the frequency of the next candidate element of the window. Also, if we are decrementing the starting element’s frequency in the current window and it becomes 0, we can remove this element from the map. This way, we will always keep a unique number of elements in the hashmap.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    void countDistinct (int arr[], int n, int k)
        {
            unordered_map<int,int>mp;
            for(int i=0;i<k;i++) mp[arr[i]]++;
            int i = 0, j=k;
            while(j<=n){
                    cout<<mp.size()<<" ";
                    mp[arr[i]]--;
                    if(!mp[arr[i]]) 
                      mp.erase(arr[i]);    //remove element if frequency becomes 0
                    mp[arr[j]]++;
                    j++,i++;         // move to next window
                        
            }
        }
        
    int main(){
        int arr[3] = {4, 1, 1};
    
        int n =  sizeof(arr)/sizeof(arr[0]);
        int k =2;
        countDistinct(arr, n, k);
    }

    Output

    2 1

    We can also use a variable instead of hashmap size in the above algorithm. Below is an implementation of this.

    Python Programming

    from collections import defaultdict
    
    def countDistinctElements(arr, k, n):
    
       mp = defaultdict(lambda:0)
       ans = 0
       for i in range(k):
           if mp[arr[i]] == 0:
               ans += 1
           mp[arr[i]] += 1
       print(ans)
       
       for i in range(k, n):
           if mp[arr[i - k]] == 1:
               ans -= 1
           mp[arr[i - k]] -= 1
       
           if mp[arr[i]] == 0:
               ans += 1
           mp[arr[i]] += 1
    
           print(ans)
    
    arr = [4, 1, 1]
    n = len(arr)
    k = 2
    countDistinctElements(arr, k, n)

    Output

    2
    1

    C# Programming

    using System;
    using System.Collections.Generic;
    
    public class Solution {
        static void countDistinct(int[] arr, int k)
        {
            Dictionary<int, int> mp = new Dictionary<int, int>();
    
            int ans = 0;
    
            for (int i = 0; i < k; i++) {
                if (!mp.ContainsKey(arr[i])) {
                    mp.Add(arr[i], 1);
                    ans++;
                }
                else {
                    int count = mp[arr[i]];
                    mp.Remove(arr[i]);
                    mp.Add(arr[i], count + 1);
                }
            }
            Console.WriteLine(ans);
    
            for (int i = k; i < arr.Length; i++) {
    
                if (mp[arr[i - k]] == 1) {
                    mp.Remove(arr[i - k]);
                    ans--;
                }
                else 
                {
                    int count = mp[arr[i - k]];
                    mp.Remove(arr[i - k]);
                    mp.Add(arr[i - k], count - 1);
                }
                if (!mp.ContainsKey(arr[i])) {
                    mp.Add(arr[i], 1);
                    ans++;
                }
                else
                {
                    int count = mp[arr[i]];
                    mp.Remove(arr[i]);
                    mp.Add(arr[i], count + 1);
                }
    
                Console.WriteLine(ans);
            }
        }
    
       public static void Main(String[] arg)
        {
            int[] arr = {4, 1, 1};
            int k = 2;
            countDistinct(arr, k);
        }
    }

    Output

    2
    1

    People are also reading:

    Leave a Comment on this Post

    0 Comments