Subarrays with K Different Integers

Hard Arrays & Hashing Sliding Window · Hash Map Original on LeetCode

Subarrays with K Different Integers is a hard arrays & hashing problem solved with the sliding window · hash map pattern. The best approach, optimal (at most k minus at most k - 1), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend from every start) up.

Problem

Given an integer array nums and an integer k, count the subarrays (contiguous, non-empty) that contain exactly k different values.

For example, [4, 2, 4, 6] contains three different values: 2, 4 and 6.

Examples

Example 1

Input
nums = [2, 1, 2, 3], k = 2
Output
4
Why
The subarrays with exactly two distinct values are [2, 1], [1, 2], [2, 1, 2] and [2, 3].

Example 2

Input
nums = [3, 3, 1, 3, 2], k = 3
Output
3
Why
Only [3, 3, 1, 3, 2], [3, 1, 3, 2] and [1, 3, 2] contain all of 1, 2 and 3.

Example 3

Input
nums = [3, 3, 3], k = 1
Output
6
Why
Every one of the 6 subarrays contains only the value 3.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= nums.length
  • 1 <= k <= nums.length

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (extend from every start)O(n²)O(n)
Optimal (at most k minus at most k - 1)O(n)O(n)

1Brute force (extend from every start)

TimeO(n²)Each of the n starts may extend over the rest of the array.
SpaceO(n)A frequency array indexed by value (values are at most n).

For every starting index, grow the subarray to the right while keeping a frequency table and a distinct counter. Count the ends where the distinct count is exactly k, and stop as soon as it exceeds k because it can never drop again.

  1. For each i, reset a frequency array and distinct = 0.
  2. For j from i: add nums[j]; if its frequency became 1, increment distinct.
  3. If distinct > k, break; if distinct == k, increment the answer.
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        int n = nums.length, count = 0;
        for (int i = 0; i < n; i++) {
            int[] freq = new int[n + 1];
            int distinct = 0;
            for (int j = i; j < n; j++) {
                if (freq[nums[j]]++ == 0) distinct++;
                if (distinct > k) break;
                if (distinct == k) count++;
            }
        }
        return count;
    }
}

2Optimal (at most k minus at most k - 1)

TimeO(n)Each atMost pass moves both pointers at most n times, and there are two passes.
SpaceO(n)The frequency array indexed by value.

A sliding window easily counts subarrays with at most k distinct values: for every right end, shrink the left end until the window has at most k distinct values; then all right - left + 1 subarrays ending at right and starting inside the window qualify. Subarrays with exactly k distinct values are those counted for k but not for k - 1, so the answer is atMost(k) - atMost(k - 1).

  1. Write atMost(m): frequency array, left = 0, distinct = 0, total = 0.
  2. For each right: add nums[right] (increment distinct on a new value).
  3. While distinct > m: remove nums[left] (decrement distinct when its count hits 0) and move left forward.
  4. Add right - left + 1 to total.
  5. Return atMost(k) - atMost(k - 1).
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int m) {
        int[] freq = new int[nums.length + 1];
        int left = 0, distinct = 0, total = 0;
        for (int right = 0; right < nums.length; right++) {
            if (freq[nums[right]]++ == 0) distinct++;
            while (distinct > m) {
                if (--freq[nums[left]] == 0) distinct--;
                left++;
            }
            total += right - left + 1;
        }
        return total;
    }
}

Edge cases to test

  • k larger than the number of distinct values in the whole array (answer 0)
  • All elements equal with k = 1 (every subarray counts: n(n + 1) / 2)
  • All elements distinct (exactly n - k + 1 subarrays)
  • A single element
  • Long runs of a repeated value inside a window, which add many valid starting points

Hints

Hint 1

Fix the left end and extend the right end, tracking how many distinct values are inside. When can you stop extending?

Hint 2

Counting windows with exactly k distinct values is awkward for a sliding window, but counting windows with at most k distinct values is easy.

Hint 3

exactly(k) = atMost(k) - atMost(k - 1). For atMost, every right end contributes right - left + 1 subarrays once the window is shrunk to be valid.

FAQ

What is the best time complexity for Subarrays with K Different Integers?

Optimal (at most k minus at most k - 1) runs in O(n) time and O(n) extra space. Each atMost pass moves both pointers at most n times, and there are two passes.

Which pattern does Subarrays with K Different Integers use?

It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters, Minimum Window Substring, Longest Substring with At Most K Distinct Characters.

Is there a brute force solution for Subarrays with K Different Integers?

Yes. Brute force (extend from every start) takes O(n²) time and O(n) space. For every starting index, grow the subarray to the right while keeping a frequency table and a distinct counter.

Which edge cases should I test for Subarrays with K Different Integers?

k larger than the number of distinct values in the whole array (answer 0); All elements equal with k = 1 (every subarray counts: n(n + 1) / 2); All elements distinct (exactly n - k + 1 subarrays); A single element; Long runs of a repeated value inside a window, which add many valid starting points.