Count Distinct Elements in Sliding Windows
At Freshworks, we often deal with streams of data, like user activity logs or sensor readings. Understanding patterns and diversity within specific timeframes is crucial for insights, anomaly detection, and performance monitoring. This problem focuses on efficiently analyzing such data by identifying the unique elements within contiguous segments, often referred to as "sliding windows."
Given an array of integers nums and an integer k, your task is to calculate the number of distinct elements for every possible contiguous subarray (window) of size k. You should return an array where each element represents the count of distinct elements for its corresponding window.
For example, if nums = [1, 2, 1, 3, 4, 2, 3] and k = 4:
[1, 2, 1, 3] (indices 0 to 3) has distinct elements {1, 2, 3}. Count = 3.[2, 1, 3, 4] (indices 1 to 4) has distinct elements {1, 2, 3, 4}. Count = 4.[1, 3, 4, 2] (indices 2 to 5) has distinct elements {1, 2, 3, 4}. Count = 4.[3, 4, 2, 3] (indices 3 to 6) has distinct elements {2, 3, 4}. Count = 3.The final output should be [3, 4, 4, 3].
Function Signature:
function countDistinctElements(nums: number[], k: number): number[]
Input:
nums: An array of integers.k: An integer representing the fixed size of the sliding window.Output:
result[i] is the count of distinct elements in the window nums[i...i+k-1]. The length of the output array will be nums.length - k + 1.k will always be a positive integer.k. If nums.length < k, the output array should be empty.Examples
Example 1
Input:
nums = [1, 2, 1, 3, 4, 2, 3], k = 4
Output:
[3, 4, 4, 3]
Note:
Window [1, 2, 1, 3] has {1, 2, 3} (3 distinct). Window [2, 1, 3, 4] has {1, 2, 3, 4} (4 distinct). Window [1, 3, 4, 2] has {1, 2, 3, 4} (4 distinct). Window [3, 4, 2, 3] has {2, 3, 4} (3 distinct).
Example 2
Input:
nums = [1, 1, 1, 1, 1], k = 3
Output:
[1, 1, 1]
Note:
All windows contain only the element 1, so the count of distinct elements is always 1.
Example 3
Input:
nums = [5, 6, 7, 8, 9], k = 2
Output:
[2, 2, 2, 2]
Note:
Each window of size 2 contains two distinct elements. E.g., [5, 6] has {5, 6}, [6, 7] has {6, 7} etc.
Constraints
1 <= nums.length <= 10^51 <= k <= nums.length-10^9 <= nums[i] <= 10^9nums arrays containing non-numeric types.k unique elements.k being 1 or k being equal to nums.length?Loading editor...