Count Distinct Elements In Every Window

Problem Statement:

“Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.”

Examples:

Example 1:
Input: 
K=4,
array[] = {1,2,1,3,4,2,3}
Output: 3  4  3  3
Explanation:
First window is {1, 2, 1, 3}, count of distinct numbers is 3
Second window is {2, 1, 3, 4} count of distinct numbers is 4
Third window is {1, 3, 4, 2} count of distinct numbers is 4
Fourth window is {3, 4, 2, 3} count of distinct numbers is 3


Example 2:
Input: 
K=3
array[]={2,3,1,4,2}
Output:  3 3 3
Explanation:
First window is {2,3,1}, count of distinct numbers is 3
Second window is {3,1,4} count of distinct numbers is 3
Third window is {1,4,2} count of distinct numbers is 3

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive approach:

Intuition :

What we can think is to traverse through the array and for each window int keep a count of the distinct elements in it.

Approach:

For the given array, traverse through from index 0 to n-k(to avoid array out of bound exception).and then traverse array from i to i+k.

Traverse the window and if the element is not present in the prefix of that window then count++

Print the count.

CODE:

C++ Code

#include <bits/stdc++.h>
using namespace std;


int windows(int arr[], int k)
{
    int count = 0;

    for (int i = 0; i < k; i++) {
       
        int j;
        for (j = 0; j < i; j++)
            if (arr[i] == arr[j])
                break;
        if (j == i)
            count++;
    }
    return count;
}


void countDistinct(int arr[], int n, int k)
{
   
    for (int i = 0; i <= n - k; i++)
        cout << windows(arr + i, k) << " ";
}


int main()
{
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    countDistinct(arr, n, k);
    return 0;
}

Output: 3 4 4 3

Time Complexity: O(n* k*k)- as we are traversing through the array and the window of size k is using two loops so k*k.

Space Complexity:-O(1) no extra space required.

Java Code

import java.util.*;

class TUF{
static int windows(int arr[], int num,int k)
{
    int count = 0;

    for (int i = num; i <num+k; i++) {
       
        int j;
        for (j = num; j <num+k; j++)
            if (arr[i] == arr[j])
                break;
        if (j == i)
            count++;
    }
    return count;
}


static void countDistinct(int arr[], int n, int k)
{
   
    for (int i = 0; i <= n - k; i++)
        System.out.print(windows(arr,i, k)+" ");
}


public static void main(String args[])
{
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
    int n = arr.length;
    countDistinct(arr, n, k);
    
}
}

Output: 3 4 4 3

Time Complexity: O(n* k*k)- as we are traversing through the array and the window of size k is using two loops so k*k.

Space Complexity:-O(1) no extra space required.

Solution 2: Using Maps

Intuition :

What we really need is to store the distinct element in of window so we can use the unordered map. For storing the frequency of every element in the window.

Approach

  • Take an unordered map,
  • Traverse through the first window and insert it into the map.
  • When the index(j) is reached to window size now push the size of the map in a vector, as there will be all distinct keys in the map so the size of the map will be equal to distinct elements.
  • Her index(i) is the starting point of each window so when we move ahead in each window, we have to remove the element of present in index i, so we are erasing arr[i] from the map.
  • At last print all the elements of the vector.

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std;
void countDistinct(int A[], int n, int k)
{
   
     vector<int> ans;
        unordered_map<int,int> mp;
        int j=0,i=0;
        while(j<n)
        {
           mp[A[j]]++;
            
            if(j-i+1==k)
            {
                ans.push_back(mp.size());
                mp[A[i]]--;
                if(mp[A[i]]==0)
                {
                    mp.erase(A[i]);
                }
                i++;
            }
            j++;
        }
       for(auto x: ans)
        cout<<x<<" ";
   
}
int main()
{
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    countDistinct(arr, n, k);
    return 0;
}

Output: 3 4 4 3

Time Complexity: 

O(n)- as we are traversing through the array only once.

Space Complexity:

O(n)- if all the elements are unique in the array so every element will take space and hashing requires linear space.

Java Code

import java.util.*;

class TUF{
static void countDistinct(int A[], int n, int k)
{
   
        ArrayList<Integer> ans=new ArrayList<>(); 
        HashMap<Integer,Integer> map=new HashMap<>();
        int j=0,i=0;
        while(j<n)
        {
           map.put(A[j], map.getOrDefault(A[i],0)+1);
            
            if(j-i+1==k)
            {
                ans.add(map.size());
                map.put(A[i],map.get(A[i])-1);
                if(map.get(A[i])==0)
                map.remove(A[i]);
                i++;
            }
            j++;
        }
       for(int x: ans)
        System.out.print(x+" ");
}


public static void main(String args[])
{
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
    int n = arr.length;
    countDistinct(arr, n, k);
    
}
}

Output: 3 4 4 3

Time Complexity: 

O(n)- as we are traversing through the array only once.

Space Complexity:

O(n)- if all the elements are unique in the array so every element will take space and hashing requires linear space.

Special thanks to Ayush Pandey for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article