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

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 the 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:

• Dutch National Flag Problem
• Construction of an Expression Tree
• Create a mirror of an m–ary Tree
• Find a Pair with the given sum in a BST
• In-place vs out-of-place algorithms
• Quicksort using Dutch National Flag Algorithm
• Hybrid QuickSort Algorithm
• Count Inversions
• Merge Sort for Linked Lists
• Find and remove loops in a Linked List