Count Distinct Elements in Subarray
Given an array of integers and a window size k, calculate the number of distinct elements in every subarray of size k. Return an array of these counts for each subarray.
[ [ 1, 2, 1, 3, 4, 2, 3 ], 4 ]
Explanation. The distinct counts for subarrays are: [1,2,1,3] -> 3 distinct elements, [2,1,3,4] -> 4 distinct elements, [1,3,4,2] -> 4 distinct elements, [3,4,2,3] -> 3 distinct elements.
[ [ 1, 1, 1, 1 ], 2 ]
Explanation. Each subarray of size 2 has the same element repeated, so there is only 1 distinct element.
[ [ 5, 2, 7, 7, 7, 8, 10 ], 3 ]
Explanation. Distinct counts change as the window slides through the array. Distinct elements in subarrays are [5,2,7] -> 3, [2,7,7] -> 2, [7,7,7] -> 1, [7,7,8] -> 2, [7,8,10] -> 2.
Follow-up: Can you solve this problem using a sliding window technique to avoid re-calculating the count for overlapping parts of subarrays?
- The array contains only integers.\n- The size of the array is at least `k`.
- Views
- 3