Subarrays with K Different Integers — Hard Problem & Solution

Count the subarrays of nums containing exactly k distinct integers.

Difficulty: Hard
Topics: Arrays, Hash Table, Two Pointers, Sliding Window, Counting
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the subarrays of nums containing exactly k distinct integers.

Example 1

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2].

Example 2

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: [1,2,1,3], [2,1,3] and [1,3,4].

Example 3

Input: nums = [5,5,5], k = 1
Output: 6
Explanation: Every subarray of a constant array has one distinct value.

Constraints

1 <= nums.length <= 20000
1 <= nums[i], k <= nums.length

How to solve Subarrays with K Different Integers

The 'exactly k' predicate is not monotone in the window's left edge, which breaks the usual two-pointer count. The 'at most k' predicate is, so count that twice and subtract.

Approach

Write atMost(limit): slide r over the array, tally the values, and shrink from l while more than limit distinct values are in the window.
Each r contributes r - l + 1 subarrays — every window ending at r and starting at or after l.
Return atMost(k) - atMost(k - 1).

Why it works

For a fixed right end, the set of valid left ends under 'at most limit' is a contiguous suffix, so r - l + 1 counts them all in constant time and l never moves backwards. Every subarray with at most k distinct values either has exactly k or at most k-1, and the two cases are disjoint, so the subtraction isolates the exact count.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Trying to maintain 'exactly k' with one window undercounts — the valid left ends form a range, not a suffix.
atMost(0) must be 0, not a crash, when k = 1.
Decrementing the tally without dropping zero entries leaves the distinct count wrong.

Reference solution

Python

from typing import List

def subarraysWithKDistinct(nums: List[int], k: int) -> int:
    def at_most(limit: int) -> int:
        if limit < 0:
            return 0
        cnt = {}
        distinct = 0
        l = 0
        res = 0
        for r, v in enumerate(nums):
            cnt[v] = cnt.get(v, 0) + 1
            if cnt[v] == 1:
                distinct += 1
            while distinct > limit:
                u = nums[l]
                cnt[u] -= 1
                if cnt[u] == 0:
                    distinct -= 1
                l += 1
            res += r - l + 1
        return res

    return at_most(k) - at_most(k - 1)

JavaScript

var subarraysWithKDistinct = function(nums, k) {
    var atMost = function(limit) {
        if (limit < 0) return 0;
        var cnt = {};
        var distinct = 0, l = 0, res = 0;
        for (var r = 0; r < nums.length; r++) {
            var v = nums[r];
            cnt[v] = (cnt[v] || 0) + 1;
            if (cnt[v] === 1) distinct++;
            while (distinct > limit) {
                var u = nums[l];
                cnt[u]--;
                if (cnt[u] === 0) distinct--;
                l++;
            }
            res += r - l + 1;
        }
        return res;
    };
    return atMost(k) - atMost(k - 1);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue