Count Distinct In Every Window of Size K

Last Updated : 14 Mar, 2026

Given an array arr[] and an integer k, return the count of distinct numbers in all windows of size k.

Examples:

Input: arr[] = [1, 2, 1, 3, 4, 2, 3], k = 4
Output: [3, 4, 4, 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.
Input: arr[] = [4, 1, 1], k = 2
Output: [2, 1]
Explanation: First window is [4, 1], count of distinct numbers is 2.
Second window is [1, 1], count of distinct numbers is 1.

Try it on GfG Practice

Table of Content

[Naive Approach] Traversal and Hashing - O(n × k) Time and O(1) Space
[Expected Approach] Sliding Window and Hashing - O(n) Time and O(k) Space

[Naive Approach] Traversal and Hashing - O(n × k) Time and O(1) Space

Traverse the given array considering every window of size k in it and keep a count on the distinct elements of the window.

C++

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> countDistinct(vector<int> &arr, int k) {
    int n = arr.size();  
    vector<int> res;
  
    // Iterate over every window
    for (int i = 0; i <= n - k; i++) {
      
        // Hash Set to count unique elements
        unordered_set<int> st;
        for(int j = i; j < i + k; j++)
        	st.insert(arr[j]);
      
        // Size of set denotes the number of unique elements
        // in the window
        res.push_back(st.size());
    }
    return res;
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
    int k = 4;

    vector<int> res = countDistinct(arr, k);
    for(int ele: res)
        cout << ele << " ";
    return 0;
}

Java

import java.util.ArrayList;
import java.util.HashSet;

class GfG {
    static ArrayList<Integer> countDistinct(int[] arr, int k) {
        int n = arr.length;  
        ArrayList<Integer> res = new ArrayList<>();
      
        // Iterate over every window
        for (int i = 0; i <= n - k; i++) {
          
            // Hash Set to count unique elements
            HashSet<Integer> st = new HashSet<>();
            for(int j = i; j < i + k; j++)
                st.add(arr[j]);
          
            // Size of set denotes the number of unique elements
            // in the window
            res.add(st.size());
        }
        return res;
    }

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

        ArrayList<Integer> res = countDistinct(arr, k);
        for(int ele: res)
            System.out.print(ele + " ");
    }
}

Python

def countDistinct(arr, k):
    n = len(arr)  
    res = []
  
    # Iterate over every window
    for i in range(n - k + 1):
      
        # Hash Set to count unique elements
        st = set()
        for j in range(i, i + k):
            st.add(arr[j])
      
        # Size of set denotes the number of unique elements
        # in the window
        res.append(len(st))
    return res


if __name__ == "__main__":
    arr = [1, 2, 1, 3, 4, 2, 3]
    k = 4

    res = countDistinct(arr, k)
    for ele in res:
        print(ele, end=" ")

C#

using System;
using System.Collections.Generic;

class GfG {
    static List<int> countDistinct(int[] arr, int k) {
        int n = arr.Length;  
        List<int> res = new List<int>();
  
        // Iterate over every window
        for (int i = 0; i <= n - k; i++) {
      
            // Hash Set to count unique elements
            HashSet<int> st = new HashSet<int>();
            for (int j = i; j < i + k; j++)
                st.Add(arr[j]);
      
            // Size of set denotes the number of unique elements
            // in the window
            res.Add(st.Count);
        }
        return res;
    }

    static void Main() {
        int[] arr = {1, 2, 1, 3, 4, 2, 3};
        int k = 4;

        List<int> res = countDistinct(arr, k);
        foreach (int ele in res)
            Console.Write(ele + " ");
    }
}

JavaScript

function countDistinct(arr, k) {
    let n = arr.length;  
    let res = [];
  
    // Iterate over every window
    for (let i = 0; i <= n - k; i++) {
      
        // Hash Set to count unique elements
        let st = new Set();
        for (let j = i; j < i + k; j++)
            st.add(arr[j]);
      
        // Size of set denotes the number of unique elements
        // in the window
        res.push(st.size);
    }
    return res;
}

// Driver Code
let arr = [1, 2, 1, 3, 4, 2, 3];
let k = 4;
let res = countDistinct(arr, k);
console.log(res.join(' '));

Output

3 4 4 3

[Expected Approach] Sliding Window and Hashing - O(n) Time and O(k) Space

Use a sliding window of size k and store element frequencies in a hash map.
Initialize the first window with the first k elements; the map size gives the number of distinct elements.
Slide the window, add the new element, remove the old one (if its frequency becomes 0 remove it), and store the map size as the result.

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> countDistinct(vector<int> &arr, int k) {
    int n = arr.size();  
    vector<int> res;
    unordered_map<int, int> freq;
  
    // Store the frequency of elements of first window
    for(int i = 0; i < k; i++)
        freq[arr[i]] += 1;
  
    // Store the count of distinct element of first window
    res.push_back(freq.size());
  
    for(int i = k; i < n; i++) {
    	freq[arr[i]] += 1;
        freq[arr[i - k]] -= 1;
      
        // If the frequency of arr[i - k] becomes 0 remove 
        // it from hash map
        if(freq[arr[i - k]] == 0)
            freq.erase(arr[i - k]);
      
        res.push_back(freq.size());
    }
      
    return res;
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
    int k = 4;

    vector<int> res = countDistinct(arr, k);
    for(int ele: res)
        cout << ele << " ";
    return 0;
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class GfG {

    static ArrayList<Integer> countDistinct(int[] arr, int k) {
        int n = arr.length;  
        ArrayList<Integer> res = new ArrayList<>();
        Map<Integer, Integer> freq = new HashMap<>();
      
        // Store the frequency of elements of the first window
        for (int i = 0; i < k; i++) {
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
        }
      
        // Store the count of distinct elements of the first window
        res.add(freq.size());
      
        for (int i = k; i < n; i++) {
            freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
            freq.put(arr[i - k], freq.get(arr[i - k]) - 1);
          
            // If the frequency of arr[i - k] becomes 0, remove it
            if (freq.get(arr[i - k]) == 0) {
                freq.remove(arr[i - k]);
            }
          
            res.add(freq.size());
        }
      
        return res;
    }

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

        ArrayList<Integer> res = countDistinct(arr, k);
        for (int ele : res) {
            System.out.print(ele + " ");
        }
    }
}

Python

from collections import defaultdict

def countDistinct(arr, k):
    n = len(arr)  
    res = []
    freq = defaultdict(int)
  
    # Store the frequency of elements of the
    # first window
    for i in range(k):
        freq[arr[i]] += 1
  
    # Store the count of distinct elements of
    # the first window
    res.append(len(freq))
  
    for i in range(k, n):
        freq[arr[i]] += 1
        freq[arr[i - k]] -= 1
      
        # If the frequency of arr[i - k] becomes 0 remove 
        # it from the hash map
        if freq[arr[i - k]] == 0:
            del freq[arr[i - k]]
      
        res.append(len(freq))
      
    return res


if __name__=="__main__":
    arr = [1, 2, 1, 3, 4, 2, 3]
    k = 4
    res = countDistinct(arr, k)
    print(*res)

C#

using System;
using System.Collections.Generic;

class GfG {
  
    static List<int> CountDistinct(int[] arr, int k) {
        int n = arr.Length;
        List<int> res = new List<int>();
        Dictionary<int, int> freq = new Dictionary<int, int>();

        // Store the frequency of elements of the first window
        for (int i = 0; i < k; i++) {
            if (freq.ContainsKey(arr[i]))
                freq[arr[i]] += 1;
            else
                freq[arr[i]] = 1;
        }

        // Store the count of distinct elements of 
        // the first window
        res.Add(freq.Count);

        for (int i = k; i < n; i++) {
          
            // Add the new element to the frequency map
            if (freq.ContainsKey(arr[i]))
                freq[arr[i]] += 1;
            else
                freq[arr[i]] = 1;

            // Remove the element that is sliding
            // out of the window
            freq[arr[i - k]] -= 1;

            // If the frequency of arr[i - k] becomes 0
            // remove it from the dictionary
            if (freq[arr[i - k]] == 0)
                freq.Remove(arr[i - k]);

            // Store the count of distinct elements in the
            // current window
            res.Add(freq.Count);
        }

        return res;
    }

    static void Main(string[] args) {
        int[] arr = { 1, 2, 1, 3, 4, 2, 3 };
        int k = 4;

        List<int> res = CountDistinct(arr, k);
        foreach (int ele in res) {
            Console.Write(ele + " ");
        }
    }
}

JavaScript

function countDistinct(arr, k) {
    let n = arr.length;  
    let res = [];
    let freq = new Map();
  
    // Store the frequency of elements of the first window
    for (let i = 0; i < k; i++) {
        freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
    }
  
    // Store the count of distinct elements of the first window
    res.push(freq.size);
  
    for (let i = k; i < n; i++) {
        // Add the new element to the frequency map
        freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
        
        // Remove the element that is sliding out of the window
        freq.set(arr[i - k], freq.get(arr[i - k]) - 1);
      
        // If the frequency of arr[i - k] becomes 0
        // remove it from the map
        if (freq.get(arr[i - k]) === 0) {
            freq.delete(arr[i - k]);
        }
      
        // Store the count of distinct elements in the current window
        res.push(freq.size);
    }
  
    return res;
}

// Driver code
let arr = [1, 2, 1, 3, 4, 2, 3];
let k = 4;
let res = countDistinct(arr, k);
console.log(res.join(" "));

Output

3 4 4 3

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem