Find count of distinct elements in every sub-array of size k

Given an array and an integer k, find the count of distinct elements in every sub-array of size k in the array.


 

For example,


Input: 
arr[] = { 2, 1, 2, 3, 2, 1, 4, 5 };
k = 5;

Output:
The count of distinct elements in the sub-array { 2, 1, 2, 3, 2 } is 3
The count of distinct elements in the sub-array { 1, 2, 3, 2, 1 } is 3
The count of distinct elements in the sub-array { 2, 3, 2, 1, 4 } is 4
The count of distinct elements in the sub-array { 3, 2, 1, 4, 5 } is 5

 

The naive solution would be to consider every sub-array in the given array and count all distinct elements in it using two nested loops as shown below. The time complexity of this approach is O(nk2).

C

Download   Run Code

Output:

The count of distinct elements in the sub-array [0, 4] is 3
The count of distinct elements in the sub-array [1, 5] is 3
The count of distinct elements in the sub-array [2, 6] is 4
The count of distinct elements in the sub-array [3, 7] is 5


 

 
We know that a set doesn’t store duplicate elements. We can take advantage of this fact and insert all elements of the current sub-array in a set and then the set size would be the distinct element count. This reduces the time complexity to O(nk) but uses O(k) extra space. We can even extend the solution to print the contents of the set as shown here.

C++

Download   Run Code

Output:

The count of distinct elements in the sub-array [0, 4] is 3
The count of distinct elements in the sub-array [1, 5] is 3
The count of distinct elements in the sub-array [2, 6] is 4
The count of distinct elements in the sub-array [3, 7] is 5


 

 
We can further reduce the time complexity to O(n) by using Sliding Window technique. The idea is to store frequency of elements in the current window in a map and also keep track of count of distinct elements in current window (of size k). The optimization here is that we can derive count of elements in any window using the count of elements in the previous window by inserting the new element to the previous window from its right and removing an element from its left. This approach is shown below:

C++

Download   Run Code

Output:

The count of distinct elements in the sub-array [0, 2] is 2
The count of distinct elements in the sub-array [1, 3] is 2
The count of distinct elements in the sub-array [2, 4] is 3

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz