Data Structures and Algorithms (DSA)  

Count Distinct Elements in Every Window

This is a classic sliding window + hashmap frequency problem

Problem Summary

In this problem, you are given:

  • An array arr[]

  • A window size k

Your task is to find:

  • The number of distinct elements in every contiguous subarray (window) of size k

In simple words, you need to move a window of size k across the array and, for each position, count how many unique elements are present in that window.

Key Insight

Instead of recalculating distinct elements for every window from scratch, which would be inefficient, we use an optimized approach:

  • A Sliding Window to represent the current subarray of size k

  • A HashMap to store the frequency (count) of elements inside the current window

This allows us to efficiently track how many distinct elements exist in the current window at any moment.

Idea

The main idea is to dynamically maintain the count of elements as the window moves.

Instead of recomputing everything:

  • When a new element enters the window, we add it to the map and increase its frequency

  • When an element leaves the window, we decrease its frequency

  • If the frequency of any element becomes 0, we remove it from the map

At any point, the size of the HashMap represents the number of distinct elements in the current window.

Algorithm

Step 1: Build the First Window

  • Take the first k elements of the array

  • Insert each element into the HashMap

  • Store their frequencies using:

    • key = element

    • value = count of that element

  • The size of the map gives the number of distinct elements in the first window

Step 2: Slide the Window

Now move the window one element at a time from left to right.

For each new index i:

  • Add the new element arr[i] to the map

    • Increase its frequency by 1

  • Remove the old element arr[i - k] from the map

    • Decrease its frequency by 1

    • If its frequency becomes 0, remove it from the map completely

  • Record the current number of distinct elements

    • This is simply map.size()

Example

Input:

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

Windows and distinct counts:

  • Window: 1 2 1 3 → Distinct: 3

  • Window: 2 1 3 4 → Distinct: 4

  • Window: 1 3 4 2 → Distinct: 4

  • Window: 3 4 2 3 → Distinct: 3

Output:

[3, 4, 4, 3]

Java Solution

import java.util.*;

class Solution {
    ArrayList<Integer> countDistinct(int arr[], int k) {

        ArrayList<Integer> result = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        int n = arr.length;

        // first window
        for (int i = 0; i < k; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        result.add(map.size());

        // sliding window
        for (int i = k; i < n; i++) {

            // add new element
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);

            // remove old element
            int old = arr[i - k];

            map.put(old, map.get(old) - 1);

            if (map.get(old) == 0) {
                map.remove(old);
            }

            result.add(map.size());
        }

        return result;
    }
}

Complexity

  • Time Complexity: O(n)

    • Each element is added and removed at most once

  • Space Complexity: O(k)

    • In the worst case, the HashMap stores k distinct elements

Key Takeaways

  • Use HashMap for frequency tracking of elements

  • Use Sliding Window to avoid recomputation

  • Always remove elements from the map when their frequency becomes 0

  • This is a very common interview pattern in array and hashing problems

Pattern Recognition

If you encounter problems with:

  • “count distinct in window”

  • “frequency in subarray”

  • “dynamic window statistics”

You should think of:

  • Sliding Window + HashMap technique

Summary

This problem is a standard example of combining the sliding window technique with a HashMap to efficiently track the number of distinct elements in a fixed-size subarray. By updating the frequency map dynamically as the window moves, we avoid redundant computations and achieve optimal performance. This approach is widely used in coding interviews and real-world scenarios involving continuous data processing and window-based analysis.

Membership not found