Count Distinct Elements in Every Window

In this class, We discuss Count Distinct Elements in Every Window.

Readers can prepare an entire competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given an array of N elements and a window size K.

Our task is to find the distinct element count in each window.

Example:

N = 7 and K = 4

A = [1, 2, 1, 3, 4, 2, 3]

Output: [3, 4, 4, 3]

The first window is [1, 2, 1, 3].

The distinct elements in the window are 3.

Similarly, the remaining windows count.

Time complexity: O(N)

Space Complexity: O(N)

Logic:

We use a hash table to maintain the distinct elements.

The step-by-step explanation is provided in the video.

Code: