Skip to main content
Talentd

Count Subarrays With K Distinct Integers - Solution & Explanation

HardArrayHash TableSliding WindowCounting6 min read
Practice this problem

Problem Statement

You are given an integer array nums and two integers k and m.

Return an integer denoting the count of subarrays of nums such that:

  • The subarray contains exactly k distinct integers.
  • Within the subarray, each distinct integer appears at least m times.

 

Example 1:

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

Output: 2

Explanation:

The possible subarrays with k = 2 distinct integers, each appearing at least m = 2 times are:

Subarray Distinct
numbers		 Frequency
[1, 2, 1, 2] {1, 2} → 2 {1: 2, 2: 2}
[1, 2, 1, 2, 2] {1, 2} → 2 {1: 2, 2: 3}

Thus, the answer is 2.

Example 2:

Input: nums = [3,1,2,4], k = 2, m = 1

Output: 3

Explanation:

The possible subarrays with k = 2 distinct integers, each appearing at least m = 1 times are:

Subarray Distinct
numbers		 Frequency
[3, 1] {3, 1} → 2 {3: 1, 1: 1}
[1, 2] {1, 2} → 2 {1: 1, 2: 1}
[2, 4] {2, 4} → 2 {2: 1, 4: 1}

Thus, the answer is 3.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k, m <= nums.length

Approach Overview

Problem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays contain exactly k distinct integers. The challenge is efficiently tracking unique elements while expanding and shrinking subarray boundaries.

Approach 1: Brute Force with Set Tracking (O(n²) time, O(n) space)

Start every subarray from index i. Extend the right boundary one element at a time and track unique numbers using a set or hash map. Each extension updates the number of distinct elements. When the count becomes exactly k, increment the result. Stop extending once the count exceeds k. This approach checks all possible starting positions, which leads to quadratic time complexity. Useful for understanding the problem but too slow for large inputs.

Approach 2: Sliding Window with At-Most Trick (O(n) time, O(n) space)

The key observation: counting subarrays with exactly k distinct elements can be reduced to counting subarrays with at most k distinct elements. The formula is:

exactly(k) = atMost(k) - atMost(k-1)

Implement a sliding window using two pointers and a frequency hash table. Expand the right pointer and update counts. When distinct elements exceed k, shrink the left pointer until the window becomes valid again. For each valid position, add the window length contribution (right - left + 1). This counts all subarrays ending at right that satisfy the constraint.

The helper function atMost(k) runs once for k and once for k-1. Each element enters and leaves the window at most once, giving linear complexity. This technique is a classic pattern combining sliding window with frequency counting on an array.

Approach 3: Sliding Window with Two Left Pointers (O(n) time, O(n) space)

Another optimized strategy maintains two sliding windows simultaneously: one tracking at most k distinct elements and another tracking at most k-1. Both windows expand with the same right pointer but shrink independently. The difference between their valid starting indices directly gives the number of subarrays ending at the current index with exactly k distinct elements. This avoids calling a helper function twice but follows the same underlying logic.

Recommended for interviews: The sliding window atMost(k) - atMost(k-1) technique is the expected solution. It demonstrates strong understanding of window invariants, frequency maps, and counting strategies. Brute force shows baseline reasoning, but the linear sliding window solution is what interviewers want to see for hard array problems.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with SetO(n²)O(n)Conceptual understanding or very small arrays
Sliding Window (atMost(k) - atMost(k-1))O(n)O(n)General optimal solution for unsorted arrays
Dual Sliding WindowsO(n)O(n)Alternative linear method without calling helper twice

Video Solution

LeetCode Problem 3859 | Count Subarrays With K Distinct Integers • Repovive TV • 712 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Count Subarrays With K Distinct Integers easy or hard?
The problem is typically labeled Hard because the direct brute-force idea is simple but inefficient. The real challenge is recognizing the atMost(K) − atMost(K−1) transformation and implementing a correct sliding window with frequency tracking.
Count Subarrays With K Distinct Integers Python/Java solution
Most implementations use the sliding window atMost technique. A helper function counts subarrays with at most K distinct values using a hash map and two pointers. The final answer is computed as atMost(K) minus atMost(K-1), and the same logic translates directly to Python, Java, C++, Go, or TypeScript.
How to solve Count Subarrays With K Distinct Integers in O(n)?
Use a sliding window with a frequency hash map to count subarrays with at most K distinct elements. Then compute the result using exactly(k) = atMost(k) − atMost(k−1). Each window expansion and contraction updates the distinct count while maintaining valid boundaries, resulting in linear traversal.
What is the best approach for Count Subarrays With K Distinct Integers?
The most efficient approach uses a sliding window with the formula exactly(k) = atMost(k) − atMost(k−1). A hash map tracks element frequencies while two pointers maintain a valid window. This method processes each element at most twice, giving O(n) time complexity and O(n) space.
Is Count Subarrays With K Distinct Integers asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests sliding window patterns, hash map usage, and subarray counting logic. Interviewers often expect the optimized O(n) sliding window solution.
What data structure is used in Count Subarrays With K Distinct Integers?
A hash table (or hash map) stores element frequencies inside a sliding window. Two pointers track the window boundaries, while the map quickly updates counts as elements enter or leave the window.
What is the time complexity of Count Subarrays With K Distinct Integers?
The optimal sliding window solution runs in O(n) time because each element is added and removed from the window at most once. The hash map operations are constant on average. Space complexity is O(n) in the worst case if all elements in the array are distinct.

Ready to solve this problem?

Practice Count Subarrays With K Distinct Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays