Subarrays with K Different Integers - Sliding Window - 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❯

  1. We define a helper function atMostK(nums, k) that returns the number of subarrays with at most k different integers.
  2. This function uses a sliding window with two pointers: left and right.
  3. Maintain a frequency map to track how many times each integer appears in the current window.
  4. Each time we expand the right boundary by moving right, add the current number to the frequency map.
  5. 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.
  6. 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.
  7. Finally, to find the number of subarrays with exactly k different integers, compute:
    exactlyK = atMostK(nums, k) - atMostK(nums, k - 1)

Code

Python
Java
JS
C
C++
Go
Rust
Kotlin
Swift
TS
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❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(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 CaseO(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.

Mallikarjuna Mallisetty, author
About the author

Mallikarjuna Mallisetty

General programming

Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.

View LinkedIn profile ↗