Subarrays with K Different Integers

LeetCode 1034 | Difficulty: Hard

Hard

Problem Description

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

- For example, `[1,2,3,1,2]` has `3` different integers: `1`, `2`, and `3`.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: 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
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

- `1 <= nums.length <= 2 * 10^4`

- `1 <= nums[i], k <= nums.length`

Topics: Array, Hash Table, Sliding Window, Counting

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 144 ms)

Metric	Value
Runtime	144 ms
Memory	45.4 MB
Date	2022-02-08

Solution

public class Solution {
    public int SubarraysWithKDistinct(int[] nums, int k) {
        return SubarrayAtmostK(nums, k) - SubarrayAtmostK(nums, k - 1);
}
private int SubarrayAtmostK(int[] nums, int k)
{
    Dictionary<int, int> d = new Dictionary<int, int>();
    int result = 0;
    int i = 0;
    for (int j = 0; j < nums.Length; j++)
    {
        if (d.ContainsKey(nums[j]))
        {
            d[nums[j]]++;
        }
        else
        {
            d.Add(nums[j], 1);
        }
        if (d[nums[j]] == 1) k--;

        while (k < 0)
        {
            d[nums[i]]--;
            if (d[nums[i]] == 0) k++;
            i++;
        }
        result += j - i + 1;
    }
    return result;
}
    
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 144 ms, 45.7 MB

public class Solution {
    public int SubarraysWithKDistinct(int[] nums, int k) {
        return SubarrayAtmostK(nums, k) - SubarrayAtmostK(nums, k-1);
}
private int SubarrayAtmostK(int[] nums, int k)
{
    Dictionary<int, int> d = new Dictionary<int, int>();
    int result = 0;
    int i = 0;
    for (int j = 0; j < nums.Length; j++)
    {
        if (d.ContainsKey(nums[j]))
        {
            if (d[nums[j]] == 0) k--;
            d[nums[j]]++;
        }
        else {
            k--;
            d.Add(nums[j], 1);
        }
        while (k < 0)
        {
            d[nums[i]]--;
            if (d[nums[i]] == 0) k++;
            i++;
        }
        result += j - i + 1;
    }
    return result;
}
    
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Try generating all possible subarrays and check for the number of unique integers. Increment the count accordingly.

Hint 2: How about using a map to store the count of integers?

Hint 3: Think about the Sliding Window and 2-pointer approach.