Frontend School

Count Distinct Elements in Sliding Windows

DSA
medium

Count Distinct Elements in Sliding Windows

Medium
Arrays
Hashing
Sliding Window

Overview

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."

What you need to do / Task

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:

  • Window 1: [1, 2, 1, 3] (indices 0 to 3) has distinct elements {1, 2, 3}. Count = 3.
  • Window 2: [2, 1, 3, 4] (indices 1 to 4) has distinct elements {1, 2, 3, 4}. Count = 4.
  • Window 3: [1, 3, 4, 2] (indices 2 to 5) has distinct elements {1, 2, 3, 4}. Count = 4.
  • Window 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].

Input & output

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:

  • An array of integers, where 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.

Clarifications

  • The window size k will always be a positive integer.
  • You should only consider full windows of size k. If nums.length < k, the output array should be empty.

Examples

1

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).

2

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.

3

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length
  • -10^9 <= nums[i] <= 10^9

Out of scope

  • Handling non-integer inputs or nums arrays containing non-numeric types.
  • Optimizing for memory beyond what is typically required for a hash map storing at most k unique elements.

What interviewers evaluate

  • Correctness: Does the solution accurately count distinct elements for every sliding window?
  • Efficiency: Does the solution achieve optimal time complexity, leveraging data structures appropriately?
  • Edge Cases: Is the solution robust to boundary conditions, such as k being 1 or k being equal to nums.length?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand?

Loading editor...