HardCoding

Subarrays with K Different Integers

Asked atHHashedIn

Microsoft

NetApp

ServiceNow

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an integer array **nums **and an integer k. Return the number of good subarrays of nums.

A good subarray is defined as a contiguous subarray of **nums **that contains exactly k distinct integers. A subarray is a contiguous part of the array.

Input: nums = [1, 2, 1, 2, 3], k = 2 Output: 7 **Explanation: **The 7 subarrays with exactly 2 different integers are: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Input: nums = [1, 2, 1, 3, 4], k = 3 Output: 3 Explanation: The 3 subarrays with exactly 3 different integers are: [1,2,1,3], [2,1,3], [1,3,4]

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

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

cpp

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        # Your code goes here

javascript

class Solution {
    subarraysWithKDistinct(nums, k) {
        // Your code goes here
    }
}

csharp

class Solution {
    public int SubarraysWithKDistinct(int[] nums, int k) {
        // Your code goes here
    }
}

func subarraysWithKDistinct(nums []int, k int) int {
    // Your code goes here
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Define atMost(K) as the number of subarrays containing at most K distinct values.
02Compute atMost with a frequency map and a shrinking left boundary.
03Return atMost(k) minus atMost(k - 1).
04Make the helper return zero for a negative distinct-count limit.

Reference answer

Counting exactly k distinct values directly is awkward, but exactly(k) = atMost(k) - atMost(k - 1). To compute atMost(limit), expand a right pointer and add the new value to a frequency map. While the map has more than limit keys, remove values from the left, erasing a key when its count reaches zero. After restoring validity, every subarray ending at right and starting anywhere from left through right is valid, contributing right - left + 1. Sum that contribution for every right endpoint. Run the helper for k and k - 1 and subtract. Each helper is O(n) time because both pointers move forward, with O(number of distinct values) space. The helper should return zero for a negative limit, which cleanly handles k = 0.

Then expect these follow-ups

Why does a valid window contribute right - left + 1 subarrays?
Tests: counting proof
Where else can exactly(K) = atMost(K) - atMost(K-1) be used?
Tests: pattern transfer

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question