Count distinct elements in every window

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Sliding window of size k. Use a frequency map. Track count of distinct elements (map size with non-zero counts).

Algorithm

1Populate frequency map with first k elements. Record distinct count.
2Slide window: add new element (increment freq, if new â†’ distinct++). Remove old (decrement, if 0 â†’ distinct--).
3Record distinct count for each position.

Common Pitfalls

•Remove element from map entirely (or just decrement and check 0) when its count drops to 0.

Count distinct elements in every window.java

Java

// Approach: Sliding window with a frequency HashMap. Track distinct count as window slides.
// Time: O(n) Space: O(k)
import java.util.*;

class Solution {
    ArrayList<Integer> countDistinct(int arr[], int k) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        int l = 0;
        int r = k - 1;

        while (r < arr.length) {
            HashSet<Integer> hs = new HashSet<Integer>();
            for (int i = l; i <= r; i++)
                hs.add(arr[i]);
            l++;
            r++;
            al.add(hs.size());
        }

        return al;
    }
}

// Version 2
class Solution1 {
    ArrayList<Integer> countDistinct(int arr[], int k) {
        ArrayList<Integer> res = new ArrayList<>();
        int i = 0, n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < n; j++) {
            map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);

            if (j - i + 1 == k) {
                res.add(map.size());
                if (map.containsKey(arr[i]) && map.get(arr[i]) > 1)
                    map.put(arr[i], map.get(arr[i]) - 1);
                else
                    map.remove(arr[i]);
                i++;
            }

        }

        return res;
    }
}

Was this solution helpful?