Subarrays with K Different Integers solution and explanation
Google
Infosys
IBM
9 more videos on this problem
Subarrays with K Different Integers - Leetcode 992 - PythonNeetCodeIO · 17:31 · 29K views
Subarrays with K Different Integers | Approach-1 | With Reasons | Leetcode 992 | codestorywithMIKcodestorywithMIK · 35:08 · 20K views
LeetCode 992. Subarrays with K Different IntegersHappy Coding · 16:14 · 10K views
Subarrays with K Different Integers | Approach-2 | One Pass | Leetcode 992 | codestorywithMIKcodestorywithMIK · 29:18 · 10K views
992. Subarrays with K Different Integers | Sliding Window | 2 Pointers | FAANGAryan Mittal · 18:47 · 5K views
Subarrays with K Different Integers | From Brute Force to Optimal Sliding Window | C++, Java, PythonRisingBrain · 26:15 · 5K views
992. Subarrays with K Different Integers | Leetcode | Hard | Java | Sliding Window and Two PointersAlgorithmHQ · 14:34 · 4K views
Daily LeetCode Challenge: 992. Subarrays with K Different Integers | C++ | Sliding WindowSHWETA BHAGAT · 31:27 · 1K views
Leetcode 992. Subarrays with K Different IntegersAlgorithms for Big Bucks · 12:31 · 762 views
L11. Subarray with k different integers | 2 Pointers and Sliding Window Playlisttake U forward · 20:49 · 185K views
The problem
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]has3different integers:1,2, and3.
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 * 1041 <= 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.
def subarraysWithKDistinct(nums, k):
def atMost(k):
from collections import Counter
count = Counter()
left = 0
res = 0
for right in range(len(nums)):
if count[nums[right]] == 0:
k -= 1
count[nums[right]] += 1
while k < 0:
count[nums[left]] -= 1
if count[nums[left]] == 0:
k += 1
left += 1
res += right - left + 1
return res
return atMost(k) - atMost(k - 1)import java.util.HashMap;
public class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap<>();
int left = 0, res = 0;
for (int right = 0; right < nums.length; right++) {
count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
if (count.get(nums[right]) == 1) k--;
while (k < 0) {
count.put(nums[left], count.get(nums[left]) - 1);
if (count.get(nums[left]) == 0) k++;
left++;
}
res += right - left + 1;
}
return res;
}
}#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private:
int atMost(vector<int>& nums, int k) {
unordered_map<int, int> count;
int left = 0, res = 0;
for (int right = 0; right < nums.size(); ++right) {
if (count[nums[right]]++ == 0) k--;
while (k < 0) {
if (--count[nums[left]] == 0) k++;
left++;
}
res += right - left + 1;
}
return res;
}
};function subarraysWithKDistinct(nums, k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
function atMost(nums, k) {
const count = new Map();
let left = 0, result = 0;
for (let right = 0; right < nums.length; right++) {
if (!count.has(nums[right])) k--;
count.set(nums[right], (count.get(nums[right]) || 0) + 1);
while (k < 0) {
count.set(nums[left], count.get(nums[left]) - 1);
if (count.get(nums[left]) === 0) {
count.delete(nums[left]);
k++;
}
left++;
}
result += right - left + 1;
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int atMost(int* nums, int numsSize, int k) {
int* count = (int*)calloc(numsSize + 1, sizeof(int));
int left = 0, right = 0, result = 0;
for (; right < numsSize; ++right) {
if (count[nums[right]]++ == 0) k--;
while (k < 0) {
if (--count[nums[left]] == 0) k++;
left++;
}
result += right - left + 1;
}
free(count);
return result;
}
int subarraysWithKDistinct(int* nums, int numsSize, int k) {
return atMost(nums, numsSize, k) - atMost(nums, numsSize, k - 1);
}using System;
using System.Collections.Generic;
public class Solution {
public int SubarraysWithKDistinct(int[] nums, int k) {
return AtMost(nums, k) - AtMost(nums, k - 1);
}
private int AtMost(int[] nums, int k) {
Dictionary<int, int> count = new Dictionary<int, int>();
int left = 0, res = 0;
for (int right = 0; right < nums.Length; right++) {
if (!count.ContainsKey(nums[right])) {
count[nums[right]] = 0;
}
count[nums[right]]++;
if (count[nums[right]] == 1) k--;
while (k < 0) {
count[nums[left]]--;
if (count[nums[left]] == 0) {
count.Remove(nums[left]);
k++;
}
left++;
}
res += right - left + 1;
}
return res;
}
}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.
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.
Approach 2: Default Approach
func subarraysWithKDistinct(nums []int, k int) (ans int) {
f := func(k int) []int {
n := len(nums)
pos := make([]int, n)
cnt := make([]int, n+1)
s, j := 0, 0
for i, x := range nums {
cnt[x]++
if cnt[x] == 1 {
s++
}
for ; s > k; j++ {
cnt[nums[j]]--
if cnt[nums[j]] == 0 {
s--
}
}
pos[i] = j
}
return pos
}
left, right := f(k), f(k-1)
for i := range left {
ans += right[i] - left[i]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Map | O(n²) | O(n) | Small arrays or when first reasoning about the problem |
| Sliding Window using atMost(k) Trick | O(n) | O(n) | General case and expected interview solution |
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.