Optimal Approach

Algorithm

Instead of checking each element in the window individually to count distinct values (as in the brute-force approach), we can use a HashMap to efficiently track frequencies of elements in the current window.

As the window slides, we:

Increment the count of the newly included element in the map.
Once the window size hits k, the number of keys in the map gives the count of distinct elements.
Before sliding the window forward, we decrement the count of the outgoing element and remove it from the map if its frequency becomes 0.

Approach:

Initialize two pointers i and j to define the window boundaries.
Use a HashMap to store the frequency of elements in the current window.
Slide the window by incrementing j in each step and adjusting i to maintain window size.
Record the number of distinct elements (map size) whenever the window size reaches k.

Code