#992

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Subarrays with K Different Integers

Find subarrays with exactly k distinct integers in an integer array using sliding window and hash lookup techniques.

array hash table sliding window counting

Problem Statement

Given an integer array nums and an integer k, the task is to return the number of good subarrays of nums. A good subarray is defined as a subarray where the number of distinct integers in the array is exactly k.

A subarray is a contiguous part of the array. You need to calculate how many subarrays have exactly k unique integers. Constraints are such that the array length can go up to 20,000, so an efficient approach is necessary.

Examples

Example 1

Input: nums = [1,2,1,2,3], k = 2

Output: 7

Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2

Input: nums = [1,2,1,3,4], k = 3

Output: 3

Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints

1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length

Solution Approach

Sliding Window + Hash Map

The solution involves using a sliding window to examine all subarrays, with the window expanding and contracting while maintaining the count of distinct integers using a hash map. By expanding the window to include new integers, and shrinking it when there are too many distinct values, we can efficiently count valid subarrays.

Count Subarrays with At Most K Distinct Integers

To solve this, break the problem into two parts: count the subarrays with at most k distinct integers and the subarrays with at most k-1 distinct integers. The difference between these counts gives the number of subarrays with exactly k distinct integers.

Time Complexity Optimization

This approach ensures an optimal time complexity of O(n), where n is the length of the array. By leveraging hash maps and only passing through the array a constant number of times, the algorithm avoids the inefficiencies of brute-force enumeration of all subarrays.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because each element in the array is processed at most twice (once when expanding the window and once when contracting it). The space complexity is O(n) due to the space used by the hash map to store the counts of distinct elements within the current window.

What Interviewers Usually Probe

Candidate efficiently uses sliding window and hash map for optimal subarray counting.
Understanding of counting subarrays with at most k distinct integers and leveraging this for exactly k.
Candidate implements efficient window size adjustments without unnecessary operations.

Common Pitfalls or Variants

Common pitfalls

Failure to correctly adjust the window size when encountering more than k distinct integers.
Mistaking the problem for one requiring brute-force enumeration of all subarrays, leading to a time complexity of O(n^2).
Inaccurate handling of the edge case when the array contains fewer than k distinct integers.

Follow-up variants

Subarrays with at most k distinct integers.
Count subarrays where the number of distinct integers is exactly k, but with negative integers.
Subarrays with k distinct integers in a rotated array.

FAQ

What is the approach to solving Subarrays with K Different Integers?

The optimal approach is to use a sliding window along with a hash map to count subarrays with at most k distinct integers and subtract subarrays with fewer than k distinct integers.

How can I improve the time complexity for Subarrays with K Different Integers?

The time complexity is optimized to O(n) using a sliding window approach with hash lookups, ensuring the algorithm only passes through the array a limited number of times.

What are the common mistakes when solving Subarrays with K Different Integers?

Common mistakes include failing to adjust the window properly when the number of distinct integers exceeds k or trying a brute-force solution that leads to O(n^2) complexity.

How do sliding windows and hash maps help with Subarrays with K Different Integers?

Sliding windows and hash maps allow for efficient counting of distinct integers within subarrays, enabling the solution to operate in linear time while minimizing unnecessary recalculations.

Can I apply this technique to similar problems?

Yes, this sliding window approach with hash maps is useful for problems that require counting distinct elements within subarrays or subranges, including variations with negative numbers or rotated arrays.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def f(k):
            pos = [0] * len(nums)
            cnt = Counter()
            j = 0
            for i, x in enumerate(nums):
                cnt[x] += 1
                while len(cnt) > k:
                    cnt[nums[j]] -= 1
                    if cnt[nums[j]] == 0:
                        cnt.pop(nums[j])
                    j += 1
                pos[i] = j
            return pos

        return sum(a - b for a, b in zip(f(k - 1), f(k)))

Continue Practicing

#594 longest harmonious subsequence #1010 pairs of songs with total durations divisible by 60 #930 binary subarrays with sum