Subarrays with Exactly K Different Integers | Sliding Window Approach

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]

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.

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)

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

import java.util.HashMap;

public class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }

    private int atMostK(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int left = 0, result = 0, distinct = 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) distinct++;

            while (distinct > k) {
                count.put(nums[left], count.get(nums[left]) - 1);
                if (count.get(nums[left]) == 0) distinct--;
                left++;
            }

            result += right - left + 1;
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 1, 2, 3};
        int k = 2;
        System.out.println(sol.subarraysWithKDistinct(nums, k)); // 7
    }
}

function subarraysWithKDistinct(nums, k) {
  function atMostK(nums, k) {
    const count = new Map();
    let left = 0, result = 0, distinct = 0;

    for (let right = 0; right < nums.length; right++) {
      count.set(nums[right], (count.get(nums[right]) || 0) + 1);
      if (count.get(nums[right]) === 1) distinct++;

      while (distinct > k) {
        count.set(nums[left], count.get(nums[left]) - 1);
        if (count.get(nums[left]) === 0) distinct--;
        left++;
      }

      result += right - left + 1;
    }

    return result;
  }

  return atMostK(nums, k) - atMostK(nums, k - 1);
}

// Example usage
const nums = [1, 2, 1, 2, 3];
const k = 2;
console.log(subarraysWithKDistinct(nums, k)); // 7

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NUM 100000

int subarraysWithKDistinct(int* nums, int numsSize, int k) {
    int count[MAX_NUM] = {0};
    int left = 0, result = 0, distinct = 0;

    int atMostK(int k) {
        int freq[MAX_NUM] = {0};
        int left = 0, res = 0, distinct = 0;
        for (int right = 0; right < numsSize; right++) {
            if (freq[nums[right]] == 0) distinct++;
            freq[nums[right]]++;
            while (distinct > k) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) distinct--;
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }

    return atMostK(k) - atMostK(k - 1);
}

int main() {
    int nums[] = {1, 2, 1, 2, 3};
    int k = 2;
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", subarraysWithKDistinct(nums, size, k)); // 7
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }

private:
    int atMostK(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int left = 0, result = 0, distinct = 0;

        for (int right = 0; right < nums.size(); right++) {
            count[nums[right]]++;
            if (count[nums[right]] == 1) distinct++;

            while (distinct > k) {
                count[nums[left]]--;
                if (count[nums[left]] == 0) distinct--;
                left++;
            }

            result += right - left + 1;
        }

        return result;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 1, 2, 3};
    int k = 2;
    cout << sol.subarraysWithKDistinct(nums, k) << endl; // 7
    return 0;
}

package main

import "fmt"

func atMostK(nums []int, k int) int {
    count := make(map[int]int)
    left, result, distinct := 0, 0, 0

    for right := 0; right < len(nums); right++ {
        count[nums[right]]++
        if count[nums[right]] == 1 {
            distinct++
        }

        for distinct > k {
            count[nums[left]]--
            if count[nums[left]] == 0 {
                distinct--
            }
            left++
        }

        result += right - left + 1
    }
    return result
}

func subarraysWithKDistinct(nums []int, k int) int {
    return atMostK(nums, k) - atMostK(nums, k-1)
}

func main() {
    nums := []int{1, 2, 1, 2, 3}
    k := 2
    fmt.Println(subarraysWithKDistinct(nums, k)) // 7
}

use std::collections::HashMap;

fn at_most_k(nums: &[i32], k: usize) -> i32 {
    let mut count = HashMap::new();
    let mut left = 0;
    let mut result = 0;
    let mut distinct = 0;

    for right in 0..nums.len() {
        let counter = count.entry(nums[right]).or_insert(0);
        if *counter == 0 {
            distinct += 1;
        }
        *counter += 1;

        while distinct > k {
            let left_count = count.get_mut(&nums[left]).unwrap();
            *left_count -= 1;
            if *left_count == 0 {
                distinct -= 1;
            }
            left += 1;
        }

        result += (right - left + 1) as i32;
    }
    result
}

fn subarrays_with_k_distinct(nums: &[i32], k: usize) -> i32 {
    at_most_k(nums, k) - at_most_k(nums, k - 1)
}

fn main() {
    let nums = vec![1, 2, 1, 2, 3];
    let k = 2;
    println!("{}", subarrays_with_k_distinct(&nums, k)); // 7
}

fun atMostK(nums: IntArray, k: Int): Int {
    val count = mutableMapOf<Int, Int>()
    var left = 0
    var result = 0
    var distinct = 0

    for (right in nums.indices) {
        count[nums[right]] = count.getOrDefault(nums[right], 0) + 1
        if (count[nums[right]] == 1) distinct++

        while (distinct > k) {
            count[nums[left]] = count[nums[left]]!! - 1
            if (count[nums[left]] == 0) distinct--
            left++
        }

        result += right - left + 1
    }
    return result
}

fun subarraysWithKDistinct(nums: IntArray, k: Int): Int {
    return atMostK(nums, k) - atMostK(nums, k - 1)
}

fun main() {
    val nums = intArrayOf(1, 2, 1, 2, 3)
    val k = 2
    println(subarraysWithKDistinct(nums, k)) // 7
}

func atMostK(_ nums: [Int], _ k: Int) -> Int {
    var count = [Int: Int]()
    var left = 0, result = 0, distinct = 0

    for right in 0 ..< nums.count {
        count[nums[right], default: 0] += 1
        if count[nums[right]] == 1 {
            distinct += 1
        }

        while distinct > k {
            count[nums[left]]! -= 1
            if count[nums[left]] == 0 {
                distinct -= 1
            }
            left += 1
        }

        result += right - left + 1
    }

    return result
}

func subarraysWithKDistinct(_ nums: [Int], _ k: Int) -> Int {
    return atMostK(nums, k) - atMostK(nums, k - 1)
}

let nums = [1, 2, 1, 2, 3]
let k = 2
print(subarraysWithKDistinct(nums, k)) // 7

function subarraysWithKDistinct(nums: number[], k: number): number {
  function atMostK(nums: number[], k: number): number {
    const count = new Map<number, number>();
    let left = 0, result = 0, distinct = 0;

    for (let right = 0; right < nums.length; right++) {
      count.set(nums[right], (count.get(nums[right]) || 0) + 1);
      if (count.get(nums[right]) === 1) distinct++;

      while (distinct > k) {
        count.set(nums[left], count.get(nums[left])! - 1);
        if (count.get(nums[left]) === 0) distinct--;
        left++;
      }

      result += right - left + 1;
    }

    return result;
  }

  return atMostK(nums, k) - atMostK(nums, k - 1);
}

// Example
const nums = [1, 2, 1, 2, 3];
const k = 2;
console.log(subarraysWithKDistinct(nums, k)); // 7

Time complexity

Space complexity

O(k)

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.