Given an array of size n and an integer k, return the of count of distinct numbers in all windows of size k.

Example:

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

Explanation:
First window is {1, 2, 1, 3}, count of distinct numbers is 3
Second window is {2, 1, 3, 4} count of distinct numbers is 4
Third window is {1, 3, 4, 2} count of distinct numbers is 4
Fourth window is {3, 4, 2, 3} count of distinct numbers is 3

A Simple Solution is to traverse the given array, consider every window in it and count distinct elements in the window. Below is C++ implementation of simple solution.

[pastacode lang=”cpp” manual=”%2F%2F%20Simple%20C%2B%2B%20program%20to%20count%20distinct%20elements%20in%20every%0A%2F%2F%20window%20of%20size%20k%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Counts%20distinct%20elements%20in%20window%20of%20size%20k%0Aint%20countWindowDistinct(int%20win%5B%5D%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20dist_count%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ck%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20element%20arr%5Bi%5D%20exists%20in%20arr%5B0..i-1%5D%0A%20%20%20%20%20%20%20%20int%20j%3B%0A%20%20%20%20%20%20%20%20for%20(j%3D0%3B%20j%3Ci%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20if%20(win%5Bi%5D%20%3D%3D%20win%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20if%20(j%3D%3Di)%0A%20%20%20%20%20%20%20%20%20%20%20%20dist_count%2B%2B%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20dist_count%3B%0A%7D%0A%20%0A%2F%2F%20Counts%20distinct%20elements%20in%20all%20windows%20of%20size%20k%0Avoid%20countDistinct(int%20arr%5B%5D%2C%20int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20Traverse%20through%20every%20window%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3C%3Dn-k%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20countWindowDistinct(arr%2Bi%2C%20k)%20%3C%3C%20endl%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%201%2C%203%2C%204%2C%202%2C%203%7D%2C%20%20k%20%3D%204%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20countDistinct(arr%2C%20n%2C%20k)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

3
4
4
3

Time complexity of the above solution is O(nk2). We can improve time complexity to O(nkLok) by modifying countWindowDistinct() to use sorting. The function can further be optimized to use hashing to find distinct elements in a window. With hashing the time complexity becomes O(nk). Below is a different approach that works in O(n) time.

An Efficient Solution is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements of current widow. When we slide the window, we remove an element from hash and add an element. We also keep track of distinct elements. Below is algorithm.

1) Create an empty hash map. Let hash map be hM

2) Initialize distinct element count ‘dist_count’ as 0.

3) Traverse through first window and insert elements of first window to hM. The elements are used as key and their counts as value in hM. Also keep updating ‘dist_count’

4) Print ‘dist_count’ for first window.

3) Traverse through remaining array (or other windows).
….a) Remove the first element of previous window.
…….If the removed element appeared only once
…………..remove it from hM and do “dist_count–”
…….Else (appeared multiple times in hM)
…………..decrement its count in hM

….a) Add the current element (last element of new window)
…….If the added element is not present in hM
…………..add it to hM and do “dist_count++”
…….Else (the added element appeared multiple times)
…………..increment its count in hM

Below is implementation of above approach.

[pastacode lang=”cpp” manual=”%23include%20%3Ciostream%3E%0A%23include%20%3Cmap%3E%0Ausing%20namespace%20std%3B%0A%20%0Avoid%20countDistinct(int%20arr%5B%5D%2C%20int%20k%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Creates%20an%20empty%20hashmap%20hm%0A%20%20%20%20map%3Cint%2C%20int%3E%20hm%3B%0A%20%0A%20%20%20%20%2F%2F%20initialize%20distinct%20element%20count%20for%20current%20window%0A%20%20%20%20int%20dist_count%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20first%20window%20and%20store%20count%0A%20%20%20%20%2F%2F%20of%20every%20element%20in%20hash%20map%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20if%20(hm%5Barr%5Bi%5D%5D%20%3D%3D%200)%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20dist_count%2B%2B%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20hm%5Barr%5Bi%5D%5D%20%2B%3D%201%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%2F%2F%20Print%20count%20of%20first%20window%0A%20%20cout%20%3C%3C%20dist_count%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%2F%2F%20Traverse%20through%20the%20remaining%20array%0A%20%20%20for%20(int%20i%20%3D%20k%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%2F%2F%20Remove%20first%20element%20of%20previous%20window%0A%20%20%20%20%20%2F%2F%20If%20there%20was%20only%20one%20occurrence%2C%20then%20reduce%20distinct%20count.%0A%20%20%20%20%20if%20(hm%5Barr%5Bi-k%5D%5D%20%3D%3D%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20dist_count–%3B%0A%20%20%20%20%7D%0A%20%20%20%2F%2F%20reduce%20count%20of%20the%20removed%20element%0A%20%20%20hm%5Barr%5Bi-k%5D%5D%20-%3D%201%3B%0A%20%0A%20%20%20%2F%2F%20Add%20new%20element%20of%20current%20window%0A%20%20%20%2F%2F%20If%20this%20element%20appears%20first%20time%2C%0A%20%20%20%2F%2F%20increment%20distinct%20element%20count%0A%20%0A%20%20if%20(hm%5Barr%5Bi%5D%5D%20%3D%3D%200)%0A%20%20%7B%0A%20%20%20%20%20dist_count%2B%2B%3B%0A%20%20%7D%0A%20%20hm%5Barr%5Bi%5D%5D%20%2B%3D%201%3B%0A%20%0A%20%20%2F%2F%20Print%20count%20of%20current%20window%0A%20%20cout%20%3C%3C%20dist_count%20%3C%3C%20endl%3B%0A%20%20%7D%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%201%2C%203%2C%204%2C%202%2C%203%7D%3B%0A%20%20%20int%20size%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20int%20k%20%3D%204%3B%0A%20%20%20countDistinct(arr%2C%20k%2C%20size)%3B%0A%20%0A%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

3
4
4
3

Time complexity of the above solution is O(n).

Categorized in: