Skip to main content

Subarrays with K Different Integers

Problem Statement:​

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] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

  • Example:

    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].

✅ Solution: Sliding Window + Inclusion-Exclusion (Count Subarrays with Exactly K Distinct Elements)​

Solution: Sliding Window with Map (At Most K Distinct)​

int counting(vector<int>& nums, int k) {
    int left = 0, right = 0;
    int count = 0;
    map<int, int> mpp;  // stores frequency of each element in the current window

    while (right < nums.size()) {
        if (k < 0) return 0;  // Edge case guard

        mpp[nums[right]]++;  // add nums[right] into window

        // shrink window until distinct elements count is at most k
        while (mpp.size() > k) {
            mpp[nums[left]]--;
            if (mpp[nums[left]] == 0) mpp.erase(nums[left]);
            left++;
        }

        count += right - left + 1;  // count valid subarrays ending at right
        right++;
    }

    return count;
}

int subarraysWithKDistinct(vector<int>& nums, int k) {
    return counting(nums, k) - counting(nums, k - 1);
}

📝 How It Works​

  • The problem asks to count subarrays with exactly k distinct elements.
  • We leverage the idea:
    • subarraysWithKDistinct = atMost(k) - atMost(k - 1).
    • atMost(k) means count of subarrays with at most k distinct elements.
  • The function counting uses the sliding window technique:
    • map<int, int> keeps frequency counts of elements inside the current window.
    • If the map’s size exceeds k, we shrink the window from left until size ≤ k.
    • At each step, right - left + 1 gives the number of valid subarrays ending at right.

🧩 Key Formula / Recurrence​

  • Main Formula:

    subarraysWithKDistinct(nums, k) = atMost(k) − atMost(k − 1).

  • Window Shrink Condition:

    While mpp.size() > k, move left forward.

⏱️ Time & Space Complexity​

MetricValue
Time ComplexityO(N) — Each element is processed at most twice.
Space ComplexityO(K) — For map storing up to K distinct elements.

⚠️ Edge Cases​

  • k = 0: Should return 0 because no valid subarray exists.
  • Array size < k: Should return 0.
  • All elements the same and k = 1: The whole array is valid.
  • All elements unique and k = array size: The whole array is counted once.

💡 Other Approaches​

ApproachTime ComplexityNotes
Brute ForceO(N²)Not efficient, checks all subarrays.
Prefix Sum + HashmapO(N²)For educational understanding.
Sliding Window + MapO(N) ✅Most efficient, interview standard.

🔁 Related Problems​

  • LeetCode 992: Subarrays with K Different Integers ✅
  • LeetCode 340: Longest Substring with At Most K Distinct Characters
  • LeetCode 3: Longest Substring Without Repeating Characters
  • GFG: Count subarrays with k different integers

🛠️ Other Notes (Optional)​

  • ✅ Use unordered_map instead of map if key ordering isn’t required for better average performance.
  • ✅ Real-world analogy: Counting the number of playlists with exactly k unique artists playing continuously.
💬

Discussion & Doubts