Is Distinct Numbers in Each Subarray easy or hard?

Distinct Numbers in Each Subarray is classified as a Medium problem. The difficulty comes from recognizing that recomputing distinct counts for every subarray is inefficient and that a sliding window with incremental updates reduces the complexity to linear time.

Distinct Numbers in Each Subarray Python/Java solution

Most implementations use a sliding window with a dictionary in Python or a HashMap in Java. Each step updates element frequencies as the window expands and shrinks. The algorithm runs in O(n) time and works efficiently for large arrays.

How to solve Distinct Numbers in Each Subarray in O(n)?

Use a fixed-size sliding window and maintain a frequency map. Insert the current element when expanding the window and update the map count. When the window size exceeds k, remove the leftmost element by decreasing its frequency and deleting it if the count becomes zero. The number of keys in the map gives the distinct count for that window.

What is the best approach for Distinct Numbers in Each Subarray?

The optimal approach uses a sliding window with a hash table (frequency map). As the window moves across the array, increment the count of the new element entering the window and decrement the count of the element leaving it. The number of keys in the map represents the number of distinct elements in the current window. This method runs in O(n) time and O(k) space.

Is Distinct Numbers in Each Subarray asked at Google/Amazon/Meta?

Sliding window problems with frequency maps are common in interviews at companies like Amazon, Google, and Meta. Variations of this problem appear in questions about counting unique elements, substring frequency tracking, and window-based analytics on arrays or strings.

What data structure is used in Distinct Numbers in Each Subarray?

A hash table (or dictionary) is typically used to store the frequency of elements in the current window. In cases where the value range is small, a fixed-size frequency array can replace the hash map to reduce hashing overhead while keeping the same sliding window logic.

What is the time complexity of Distinct Numbers in Each Subarray?

The optimal sliding window solution runs in O(n) time because each element is added to and removed from the frequency structure at most once. Space complexity is O(k), where k is the window size, since the hash table stores frequencies of elements currently inside the window.

1852. Distinct Numbers in Each Subarray - Practice Online

You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in every subarray of size k within nums.

Return an array ans such that ans[i] is the count of distinct elements in nums[i..(i + k - 1)] for each index 0 <= i < n - k.

Example 1:

Input: nums = [1,2,3,2,2,1,3], k = 3
Output: [3,2,2,2,3]
Explanation: The number of distinct elements in each subarray goes as follows:
- nums[0..2] = [1,2,3] so ans[0] = 3
- nums[1..3] = [2,3,2] so ans[1] = 2
- nums[2..4] = [3,2,2] so ans[2] = 2
- nums[3..5] = [2,2,1] so ans[3] = 2
- nums[4..6] = [2,1,3] so ans[4] = 3

Example 2:

Input: nums = [1,1,1,1,2,3,4], k = 4
Output: [1,2,3,4]
Explanation: The number of distinct elements in each subarray goes as follows:
- nums[0..3] = [1,1,1,1] so ans[0] = 1
- nums[1..4] = [1,1,1,2] so ans[1] = 2
- nums[2..5] = [1,1,2,3] so ans[2] = 3
- nums[3..6] = [1,2,3,4] so ans[3] = 4

Constraints:

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵