Skip to main content
Talentd

Subarrays with K Different Integers - Solution & Explanation

HardArrayHash TableSliding WindowCounting10 min readAsked at: Amazon, Microsoft, Meta +15
Practice this problem

Problem Statement

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

  • For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i], k <= 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 distinct values while expanding and shrinking a subarray window.

Approach 1: Brute Force with Frequency Map (O(n²) time, O(n) space)

Start a subarray at every index and extend it to the right while tracking frequencies of elements using a hash map. Each time you add a new element, update the map and check the number of distinct keys. If the map contains exactly k distinct integers, increment the result. If the count exceeds k, break early since extending further will only increase distinct elements. This method is straightforward and demonstrates the core requirement of counting distinct elements, but the nested iteration leads to O(n²) time in the worst case. The map storing frequencies requires O(n) space.

Approach 2: Sliding Window with Two-Pointer Technique (O(n) time, O(n) space)

The optimal solution uses a sliding window and the key observation that counting subarrays with exactly k distinct integers equals: atMost(k) - atMost(k-1). The helper function atMost(x) counts subarrays with at most x distinct elements.

Maintain two pointers (left and right) and a frequency map implemented with a hash table. Expand right while inserting elements into the map. If the number of distinct keys exceeds x, move left forward and decrease frequencies until the window becomes valid again. For each position of right, add right - left + 1 to the result because all subarrays ending at right and starting between left and right are valid.

Running atMost(k) and atMost(k-1) each takes linear time because every element enters and leaves the window at most once. The final answer is their difference. This approach relies on careful pointer movement and frequency updates but avoids redundant work, achieving O(n) time and O(n) space.

The technique combines array traversal with dynamic window resizing. Once you recognize the exactly K = atMost(K) - atMost(K-1) pattern, many “exactly K distinct” problems reduce to the same sliding window template.

Recommended for interviews: Interviewers expect the sliding window solution. The brute force approach shows you understand the requirement of counting distinct elements, but the atMost(k) trick demonstrates stronger algorithmic thinking and mastery of two-pointer window patterns.

Approach 1: Sliding Window with Two-Pointer Technique

The two-pointer technique can be employed with a sliding window approach to count subarrays with exactly k distinct numbers. The key idea is to maintain a window using two pointers that expand and shrink to keep track of the number of unique integers.

For this, we use the number of subarrays with at most k distinct numbers and at most (k-1) distinct numbers. The difference between these two values gives the number of subarrays with exactly k distinct integers.

This Python function calculates the number of subarrays with exactly k distinct integers. The function atMost(k) helps in calculating the number of subarrays with at most k distinct integers using a sliding window technique.

We then utilize this function to find the result by calculating atMost(k) - atMost(k - 1), which gives us the count of subarrays with exactly k distinct numbers.

Code

PythonJavaC++JavaScriptCC#

Python

Java

C++

JavaScript

C

C#

Complexity

Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice.

Space Complexity: O(n), due to the storage used by the hash map.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Two-Pointer Technique

Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice.

Space Complexity: O(n), due to the storage used by the hash map.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Frequency MapO(n²)O(n)Small arrays or when first reasoning about the problem
Sliding Window using atMost(k) TrickO(n)O(n)General case and expected interview solution

Video Solution

L11. Subarray with k different integers | 2 Pointers and Sliding Window Playlist • take U forward • 185,951 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Subarrays with K Different Integers easy or hard?
The problem is classified as Hard because the direct brute force approach is simple but inefficient. Recognizing the transformation exactlyK = atMost(K) − atMost(K−1) and implementing the sliding window correctly requires deeper understanding of two-pointer counting techniques.
Subarrays with K Different Integers Python/Java solution
Implement a helper function atMost(k) using a sliding window and a frequency map. Move the right pointer to expand the window, shrink with the left pointer when distinct elements exceed k, and accumulate valid subarray counts. The same logic works in Python, Java, C++, JavaScript, C, and C#.
How to solve Subarrays with K Different Integers in O(n)?
Use a sliding window that counts subarrays with at most K distinct integers. Maintain two pointers and a frequency hash map. Compute atMost(K) and atMost(K-1) separately, then subtract them to get the number of subarrays containing exactly K distinct values.
What is the best approach for Subarrays with K Different Integers?
The best approach uses a sliding window with the formula exactlyK = atMost(K) − atMost(K−1). A hash map tracks element frequencies while two pointers expand and shrink the window. Each element is processed at most twice, giving O(n) time and O(n) space.
Is Subarrays with K Different Integers asked at Google/Amazon/Meta?
Subarray counting and sliding window problems with distinct elements frequently appear in interviews at companies like Amazon, Google, and Meta. Variations such as longest substring with K distinct characters or subarrays with at most K distinct numbers are common interview patterns.
What data structure is used in Subarrays with K Different Integers?
A hash table (or dictionary) stores frequencies of numbers currently inside the sliding window. This structure allows constant-time updates when elements enter or leave the window while tracking how many distinct integers are present.
What is the time complexity of Subarrays with K Different Integers?
The optimal sliding window solution runs in O(n) time because each element enters and leaves the window once. The hash map stores element frequencies, giving O(n) space in the worst case if all numbers are unique.

Ready to solve this problem?

Practice Subarrays with K Different Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Complete Subarrays in an Array

Next

Count Vowel Substrings of a String