Subarrays with K Different Integers

Hard
774.

Subarrays with K Different Integers

Subarrays with K Different Integers is a hard coding problem on arrays, hash table and two pointers, asked in Amazon, Google, Microsoft and Morgan Stanley interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subarrays with K Different Integers — Problem & Solution

Subarrays with K Different Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Subarrays with K Different Integers is a hard coding problem on arrays, hash table and two pointers, asked in Amazon, Google, Microsoft and Morgan Stanley interviews.

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

Hints for Subarrays with K Different Integers

  1. Hint 1

    A window with exactly k distinct values is not monotone, so a single sliding window cannot count it directly.

  2. Hint 2

    A window with at most k distinct values is monotone — shrinking it never raises the distinct count.

  3. Hint 3

    exactly(k) = atMost(k) − atMost(k − 1).

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

  1. 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.
  2. Each r contributes r - l + 1 subarrays — every window ending at r and starting at or after l.
  3. 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)

Java

private static int atMostKDistinct(int[] nums, int limit) {
    if (limit < 0) return 0;
    int[] cnt = new int[nums.length + 1];
    int distinct = 0, l = 0, res = 0;
    for (int r = 0; r < nums.length; r++) {
        if (cnt[nums[r]]++ == 0) distinct++;
        while (distinct > limit) {
            if (--cnt[nums[l]] == 0) distinct--;
            l++;
        }
        res += r - l + 1;
    }
    return res;
}

public static int subarraysWithKDistinct(int[] nums, int k) {
    return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}

C++

static int atMostKDistinct(vector<int>& nums, int limit) {
    if (limit < 0) return 0;
    vector<int> cnt(nums.size() + 1, 0);
    int distinct = 0, l = 0, res = 0;
    for (int r = 0; r < (int) nums.size(); r++) {
        if (cnt[nums[r]]++ == 0) distinct++;
        while (distinct > limit) {
            if (--cnt[nums[l]] == 0) distinct--;
            l++;
        }
        res += r - l + 1;
    }
    return res;
}

int subarraysWithKDistinct(vector<int>& nums, int k) {
    return atMostKDistinct(nums, k) - atMostKDistinct(nums, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets