Subarrays with Exactly K Different Integers | Sliding Window Approach - DSA Visualization

Problem Statement❯

Given an integer array nums and an integer k, return the number of subarrays with exactly k different integers.

A subarray is a contiguous, non-empty sequence of elements within an array.

Example:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: The 7 subarrays are:
[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,3]

Examples❯

nums	k	Output	Description
[1, 2, 1, 2, 3]	2	7	Subarrays with exactly 2 distinct integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,3]
[1, 2, 1, 3, 4]	3	6	6 subarrays have exactly 3 distinct integers: [1,2,1,3], [2,1,3], [1,3,4], etc.
[1, 2, 1, 2, 1]	1	5	Single-element subarrays: [1], [2], [1], [2], [1]; and overlapping identical values like [1,2,1] are excluded
[1, 2, 3]	0	0	k = 0 is invalid for subarrays with different integers; return 0
[]	1	0	Empty array has no subarrays; return 0
[1, 2, 1, 3, 4]	5	0	Array has only 4 distinct integers; can't form a subarray with 5 distinct values
[1, 2, 1, 2, 3]	3	3	Subarrays with exactly 3 distinct integers: [1,2,1,2,3], [2,1,2,3], [1,2,3]
[1, 1, 1, 1]	1	10	All possible subarrays are valid as only 1 distinct element is present: 4 + 3 + 2 + 1 = 10
[1, 2, 3, 4]	4	1	Only one subarray ([1,2,3,4]) contains exactly 4 distinct integers
[1]	1	1	Single-element array with k = 1 results in one valid subarray

Solution❯

Understanding the Problem

We are given an array of integers nums and an integer k. Our task is to find how many subarrays (continuous sequences of elements) contain exactly k different integers.

This is not about finding the subarrays — it's about counting how many there are. For example, if nums = [1,2,1,2,3] and k = 2, we want to count all the subarrays that contain exactly 2 different numbers.

Subarrays must be contiguous. So, [1,2] is valid, but [1,3] is not if they’re not next to each other.

Step-by-Step Solution with Example

step 1: Understand the approach

We will use the sliding window technique with two pointers (left and right) and a frequency map to track the number of unique integers in the current window.

To count exactly k unique elements, we cleverly compute:

exactlyK = atMostK(k) - atMostK(k - 1)

This works because atMostK(k) includes all subarrays with up to k unique values, and atMostK(k-1) removes those with fewer than k.

step 2: Create a helper function atMostK(nums, k)

This function counts how many subarrays have at most k different numbers.

We initialize:

left = 0
right = 0 (looping pointer)
count = 0 (result)
freq = {} (a map to count frequencies of numbers)

step 3: Slide the window using two pointers

We move the right pointer one step at a time, and for each new number:

Increase its count in the frequency map
If it’s a new number (not seen before), decrease k

Then, if the number of unique elements exceeds k, we shrink the window from the left until we have ≤ k unique elements again.

step 4: Count valid subarrays

At each step, the number of valid subarrays ending at right is:

right - left + 1

This is because all subarrays starting from left to right are valid.

step 5: Return result using the difference formula

Now, the final answer becomes:

subarraysWithKDistinct(nums, k) = atMostK(nums, k) - atMostK(nums, k - 1)

step 6: Let's walk through the given example

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

atMostK(2) → Counts subarrays with ≤ 2 unique integers
atMostK(1) → Counts subarrays with ≤ 1 unique integer
Result = atMostK(2) - atMostK(1) = 10 - 3 = 7

The 7 valid subarrays with exactly 2 different integers are:

[1,2]
[2,1]
[1,2]
[2,3]
[1,2,1]
[2,1,2]
[1,2,3]

Edge Cases

Empty array: nums = [] → Result is 0
k is 0: → No subarray can have 0 distinct elements
k larger than number of unique elements in nums: → Result is 0
All elements same: nums = [1,1,1], k = 1 → Counts all possible subarrays

Final Thoughts

This problem teaches a powerful trick: if you can count “at most k” and “at most k - 1,” you can derive “exactly k.”

The two-pointer (sliding window) technique is not just efficient — it's intuitive once you understand how to track a valid window and how to expand and shrink it.

By walking through the example and thinking in terms of subarray ranges, even a beginner can confidently build this logic step by step.

Algorithm Steps❯

We define a helper function atMostK(nums, k) that returns the number of subarrays with at most k different integers.
This function uses a sliding window with two pointers: left and right.
Maintain a frequency map to track how many times each integer appears in the current window.
Each time we expand the right boundary by moving right, add the current number to the frequency map.
If the number of distinct integers in the window exceeds k, shrink the window from the left by incrementing left until the number of distinct integers is ≤ k.
After adjusting the window, all subarrays ending at right and starting anywhere from left to right are valid — add right - left + 1 to the result.
Finally, to find the number of subarrays with exactly k different integers, compute:
exactlyK = atMostK(nums, k) - atMostK(nums, k - 1)

Code

Python

Java

C++

Rust

Kotlin

Swift

from collections import defaultdict

def subarrays_with_k_distinct(nums, k):
    def at_most_k(nums, k):
        count = defaultdict(int)
        left = 0
        result = 0
        distinct = 0
        for right in range(len(nums)):
            if count[nums[right]] == 0:
                distinct += 1
            count[nums[right]] += 1

            while distinct > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    distinct -= 1
                left += 1

            result += right - left + 1
        return result

    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# Example
nums = [1, 2, 1, 2, 3]
k = 2
print(subarrays_with_k_distinct(nums, k))  # Output: 7

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	In the best case, each element is processed at most twice — once when the right pointer includes it in the window, and possibly once when the left pointer excludes it. Thus, the algorithm runs in linear time with respect to the number of elements.
Average Case	O(n)	On average, the sliding window advances both pointers across the array, and each element is added and removed from the frequency map at most once per distinct value of k. Hence, total work is proportional to n.
Worst Case	O(n)	Even in the worst case — when the number of distinct elements is close to n — each element is still added and removed from the frequency map in amortized constant time. Therefore, total time complexity remains O(n).

Space Complexity❯

O(k)

Explanation: The algorithm uses a hash map to store the frequency of elements in the current window. In the worst case, this map contains up to k unique integers.

⬅ Previous TopicLongest Substring with At Most K Distinct Characters

Next Topic ⮕Minimum Window Substring Using Sliding Window

Comments

Loading comments...

Subarrays with K Different Integers - Sliding Window - Visualization - Visualization

Contents

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

step 1: Understand the approach

step 2: Create a helper function atMostK(nums, k)

step 3: Slide the window using two pointers

step 4: Count valid subarrays

step 5: Return result using the difference formula

step 6: Let's walk through the given example

Edge Cases

Final Thoughts

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Subarrays with K Different Integers - Sliding Window - Visualization - Visualization

Contents

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

step 1: Understand the approach

step 2: Create a helper function atMostK(nums, k)

step 3: Slide the window using two pointers

step 4: Count valid subarrays

step 5: Return result using the difference formula

step 6: Let's walk through the given example

Edge Cases

Final Thoughts

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Welcome to ProgramGuru

Player Settings