1852. Distinct Numbers in Each Subarray

Problem Description

Given an integer array nums and an integer k, the task is to construct an array ans of size n-k+1 (where n is the length of nums). Each element ans[i] represents the number of distinct numbers in the subarray nums[i:i+k-1].

Solution Approach

The most efficient approach utilizes a sliding window technique combined with a hash table (or an array if the input range is known and relatively small).

1. Initialization:

   • Create a hash table (or array) to store the frequency of each number within the current window.
   • Initialize the window with the first k elements of nums, updating the frequency count in the hash table.
   • The first element of ans is the number of unique elements (size of hash table).

2. Sliding Window:

   • Iterate through nums starting from index k.
   • For each element:
     • Increment its frequency count in the hash table.
     • Decrement the frequency count of the element that just left the window (at i - k).
     • If the frequency count of the element that left the window becomes 0, remove it from the hash table.
     • Append the size of the hash table (number of distinct elements) to ans.

3. Return: Return the ans array.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of nums. We iterate through the array once using the sliding window. Hash table operations (insertion, deletion, lookup) are on average O(1).

• Space Complexity:

  • Hash Table Approach: O(k) in the average case, where k is the window size. This is because the hash table stores at most k distinct elements. In the worst case (all elements are unique), it could be O(k).
  • Array Approach: O(M), where M is the maximum value in nums. This approach is space-efficient only if the range of numbers is relatively small.

Code Implementation (Python)

from collections import Counter
 
class Solution:
    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums[:k])
        ans = [len(cnt)]
        for i in range(k, len(nums)):
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            if cnt[nums[i - k]] == 0:
                del cnt[nums[i - k]]
            ans.append(len(cnt))
        return ans
 

Code Implementation (Java)

import java.util.*;
 
class Solution {
    public int[] distinctNumbers(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < k; i++) {
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
        }
        int[] ans = new int[nums.length - k + 1];
        ans[0] = cnt.size();
        for (int i = k; i < nums.length; i++) {
            cnt.put(nums[i], cnt.get(nums[i]) + 1);
            cnt.put(nums[i - k], cnt.get(nums[i - k]) - 1);
            if (cnt.get(nums[i - k]) == 0) {
                cnt.remove(nums[i - k]);
            }
            ans[i - k + 1] = cnt.size();
        }
        return ans;
    }
}

Note: Implementations in other languages (C++, Go, TypeScript) would follow a very similar structure, using appropriate data structures for hash tables/maps and arrays in their respective languages. The core logic remains the same.