Course4all
Join us on telegram
Home/dsa/Sliding Window/Subarrays with K Different Integers

Subarrays with K Different Integers

Master this topic with zero to advance depth.

Subarrays with K Different Integers

Count the number of 'good' subarrays where the number of different integers is exactly k.

Visual Representation

nums = [1, 2, 1, 2, 3], k = 2 Exactly(K) = AtMost(K) - AtMost(K-1) AtMost(2) Subarrays: [1], [2], [1,2], [1,2,1], [2,1,2] ... AtMost(1) Subarrays: [1], [2], [1], [2], [3] Exactly(2) = 12 - 5 = 7
Hard

Examples

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Approach 1

Level I: Brute Force

Intuition

Iterate through all possible substrings nums[i...j]. For each substring, count the number of unique integers. If the count is exactly k, increment the total result.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Maintain a set of unique elements encountered so far in nums[i...j].
  4. If set.size() == k, res++.
  5. If set.size() > k, break inner loop (since distinct elements only increase).
⏱ O(N^2)💾 O(K)

Detailed Dry Run

ijSubarrayDistinctResult
00[1]10
01[1, 2]21
02[1, 2, 1]22
04[1, 2, 1, 2, 3]3STOP
java
import java.util.*;
public class Main {
    public static int subarraysWithKDistinct(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> distinct = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                distinct.add(nums[j]);
                if (distinct.size() == k) count++;
                else if (distinct.size() > k) break;
            }
        }
        return count;
    }

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

Level II: Sliding Window with 3 Pointers (O(N))

Intuition

We can use three pointers to find the number of subarrays with exactly k distinct integers directly. We maintain two 'left' pointers: left1 (minimum index to satisfy k distinct) and left2 (minimum index to satisfy k-1 distinct). The number of valid subarrays ending at right is left2 - left1.

Thought Process

  1. Maintain count1 (frequencies for left1) and count2 (frequencies for left2).
  2. As we expand right, update both maps.
  3. Move left1 as far as possible such that the window [left1, right] has k distinct elements.
  4. Move left2 as far as possible such that the window [left2, right] has k-1 distinct elements.
  5. For each right, any start index in the range [left1, left2) produces a valid subarray.

Pattern: Multi-pointer Sliding Window

⏱ O(N)💾 O(N) for frequency maps.
java
public class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        Window w1 = new Window(), w2 = new Window();
        int left1 = 0, left2 = 0, res = 0;
        for (int x : nums) {
            w1.add(x); w2.add(x);
            while (w1.distinct > k) w1.remove(nums[left1++]);
            while (w2.distinct >= k) w2.remove(nums[left2++]);
            res += left2 - left1;
        }
        return res;
    }
    
    class Window {
        Map<Integer, Integer> count = new HashMap<>();
        int distinct = 0;
        void add(int x) { if (count.getOrDefault(x, 0) == 0) distinct++; count.put(x, count.getOrDefault(x, 0) + 1); }
        void remove(int x) { count.put(x, count.get(x) - 1); if (count.get(x) == 0) distinct--; }
    }
}
Approach 3

Level III: Optimal (Sliding Window - Two Pass)

Intuition

Thought Process

Finding 'exactly K' is difficult with a single sliding window because shrinking doesn't always reduce the count of distinct elements. However, finding 'at most K' is a standard sliding window problem. Using the property Exactly(K) = AtMost(K) - AtMost(K-1) simplifies the problem significantly.

Patterns

  1. Complement Rule: Exactly(K) = AtMost(K) - AtMost(K-1).
  2. Frequency Map: Track counts of each number in the current window.
⏱ O(N)💾 O(K)

Detailed Dry Run

XAtMost(X)
212
15
Result12 - 5 = 7
java
import java.util.*;
public class Main {
    public static int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    private static int atMost(int[] nums, int k) {
        int left = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            if (count.getOrDefault(nums[right], 0) == 0) k--;
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
            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;
    }

    public static void main(String[] args) {
        System.out.println(subarraysWithKDistinct(new int[]{1,2,1,2,3}, 2));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the count map logic. Incrementing AtMost(K) means counting ALL subarrays with ≤K\le K distinct elements.

← Previous QuestionGet Equal Substrings Within Budget
Next Question →Frequency of the Most Frequent Element