Skip to main content

Sliding Window

Subarrays with K Different Integers Solution In C++/Java/Python/JS

Problem Description

Given an integer array nums and an integer k, return the number of good subarrays of nums.
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.
subarray is a contiguous part of an array.
Illustration of Subarrays with K Different Integers - Problem Description

Examples:

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]

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

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i], k <= nums.length

In this problem, we need to count all the subarrays that contain exactly `k distinct elements.
The first idea that naturally comes to mind is that we could go through every possible subarray of the given array and, for each one, check how many unique elements it has.
This is what we will explore in the brute force approach let's check it out...

Brute Force Approach

Intuition

The most straightforward approach we can think of is to go through every possible subarray of the given array.

How to Visit Every Subarray of an Array Using Nested Loops?

To implement this, we first fix the starting index i of the subarray in the array using an outer loop. This loop runs from i = 0 up to i = array.size - 1, ensuring that all possible starting points are covered.

For each fixed starting index i, we use an inner loop with index j to define the ending index of the subarray. This inner loop runs from j = i to j < array.size. We start with an empty subarray and append elements from array[j] one by one. This manual construction of subarrays helps beginners understand how subarrays can be formed using indices, without relying on built-in slice or subarray functions.

Note: We can also replace the inner loop and use built-in slicing methods instead, depending on the language and level of abstraction preferred.

Let’s consider an example to clarify this process. Suppose the array is: [1, 2, 3]. Using the nested loops:

  • At i = 0, we generate:
    • j = 0 → subarray: [1]
    • j = 1 → subarray: [1, 2]
    • j = 2 → subarray: [1, 2, 3]
  • At i = 1, we generate:
    • j = 1 → subarray: [2]
    • j = 2 → subarray: [2, 3]
  • At i = 2, we generate:
    • j = 2 → subarray: [3]

Each subarray starts at index i and ends at index j. After generating these subarrays, we can proceed to apply any additional logic needed, such as checking for a particular sum, length, or pattern.

For each subarray, we simply count the number of unique elements it contains.

If the number of unique elements is exactly k, we increase our count.

Once we’ve checked all the subarrays, we just return the total count of those that had exactly k distinct elements.

It’s a basic and easy-to-understand method, though not the most efficient for large arrays.

How to Find Unique Elements in the Subarray?

To determine the number of unique elements in a subarray, we can use a key-value data structure that allows storing elements along with how many times they occur. This structure lets us efficiently keep track of which elements have appeared and how often.

Here’s how it works:

  • As we go through the subarray, we insert each element into the data structure.
  • The element itself serves as the key, and the value represents the count of how many times that element has appeared so far.
  • If the element has already been added before, we simply update its count.
  • Once we've finished processing the subarray, the number of unique elements is equal to the number of keys in the data structure.

This method is a clear and effective way to count distinct elements in a subarray by keeping track of their frequencies. It doesn’t rely on any specific programming language and can be implemented using any environment that supports basic key-value storage.

Subarrays with K Different Integers Algorithm

Step 1. Initialize basic variables

First, determine the size of the input array. Then, initialize a variable to store the final count of valid subarrays. You’ll also need a data structure (like a map or dictionary) to keep track of how many times each element appears in the current window or subarray. This will help in managing the count of distinct elements efficiently.

Step 2. Start the outer loop to pick the index of the subarray

Use a loop variable i that runs from 0 to n-1. For each new starting index, clear the freq map since we are checking a new subarray.

Step 3. Start the inner loop to pick the ending index of the subarray

Use another loop variable, j, that runs from i to n-1. For each j, add nums[j] to the map and increase its frequency.

Step 4. Check if the current subarray has exactly k distinct elements

You can check this by using freq.size(), which gives the number of unique keys (i.e., distinct elements) in the subarray.

Step 5. Return the final count

After all subarrays have been checked, return the answer.

Illustration of Subarrays with K Different Integers - Brute Force Approach 1
Illustration of Subarrays with K Different Integers - Brute Force Approach 2

Subarrays with K Different Integers Example

Input: nums = [1,2,2,1], k = 2
Output: 5
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [1, 2, 2], [1,2, 2, 1], [2,2,1], [2,1]

  • n = 4 (array length)
  • k = 2 (want subarrays with exactly 2 distinct elements)
  • nums = [1, 2, 2, 1]

Function Behavior Recap

The function loops over all subarrays nums[i..j], uses a map freq to track the frequency of elements, and increments ans whenever the number of distinct keys in the map is exactly k.

Step-by-Step Dry Run

Let’s go through each pair of (i, j):

i = 0

  • freq = {}
  • j = 0: freq = {1:1} → distinct = 1 → No
  • j = 1: freq = {1:1, 2:1 → distinct = 2 → Yes count = 1
  • j = 2: freq = {1:1, 2:2} → distinct = 2 → Yes count = 2
  • j = 3: freq = {1:2, 2:2} → distinct = 2 → Yes count = 3

✔ Total count = 3

i = 1

  • freq = {}
  • j = 1: freq = {2:1} → distinct = 1 → No
  • j = 2: freq = {2:2} → distinct = 1 → No
  • j = 3: freq = {2:2, 1:1} → distinct = 2 → Yes count = 4

✔ Total count = 4

i = 2

  • freq = {}
  • j = 2: freq = {2:1} → distinct = 1 → No
  • j = 3: freq = {2:1, 1:1} → distinct = 2 → Yes count = 5

✔ Total count = 5

i = 3

  • freq = {}
  • j = 3: freq = {1:1} → distinct = 1 → No

✔ Total count remains = 5

Final Output: 5

Subarrays with K Different Integers Solution
Subarrays with K Different Integers Solution in C++
int subarraysWithKDistinct(vector<int>& nums, int k) {
    // Get the size of the array
    int n = nums.size();
    // Initialize answer to 0
    int ans = 0;
    // Map to store frequency of elements in current subarray
    map<int, int> freq;

    // Try every possible starting index for subarray
    for(int i = 0; i < n; ++i) {
        // Clear the frequency map for new starting index
        freq.clear();

        // Try every possible ending index for subarray starting at i
        for(int j = i; j < n; ++j) {
            // Increment the count of nums[j] in the frequency map
            freq[nums[j]]++;

            // If the number of distinct integers in current subarray is exactly k
            if(freq.size() == k) {
                // Increment the answer
                ans++;
            }
        }
    }
    // Return the total count
    return ans;
}

Subarrays with K Different Integers Solution in Java
class Solution {
    // Function to count subarrays with exactly K distinct integers
    public static int subarraysWithKDistinct(int[] nums, int k) {
        // Get the size of the array
        int n = nums.length;
        // Initialize answer to 0
        int ans = 0;
        // Map to store frequency of elements
        Map<Integer, Integer> freq = new HashMap<>();

        // Try every possible starting index for subarray
        for (int i = 0; i < n; ++i) {
            // Clear the frequency map for new starting index
            freq.clear();

            // Try every possible ending index for subarray starting at i
            for (int j = i; j < n; ++j) {
                // Increment count for nums[j]
                freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);

                // If the number of distinct integers is exactly k
                if (freq.size() == k) {
                    // Increment the answer
                    ans++;
                }
            }
        }
        // Return the total count
        return ans;
    }
}

Subarrays with K Different Integers Solution in Python
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        
        # Get the size of the array
        n = len(nums)
        # Initialize answer to 0
        ans = 0

        # Try every possible starting index for subarray
        for i in range(n):
            # Dictionary to store frequency of elements
            freq = {}

            # Try every possible ending index for subarray starting at i
            for j in range(i, n):
                # Increment count for nums[j]
                freq[nums[j]] = freq.get(nums[j], 0) + 1

                # If the number of distinct integers is exactly k
                if len(freq) == k:
                    # Increment the answer
                    ans += 1

        # Return the total count
        return ans

Subarrays with K Different Integers Solution in Javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function(nums, k) {
    // Get the size of the array
    const n = nums.length;
    // Initialize answer to 0
    let ans = 0;

    // Try every possible starting index for subarray
    for (let i = 0; i < n; ++i) {
        // Map to store frequency of elements
        const freq = new Map();

        // Try every possible ending index for subarray starting at i
        for (let j = i; j < n; ++j) {
            // Increment count for nums[j]
            freq.set(nums[j], (freq.get(nums[j]) || 0) + 1);

            // If the number of distinct integers is exactly k
            if (freq.size === k) {
                // Increment the answer
                ans++;
            }
        }
    }
    // Return the total count
    return ans;
    
};

Subarrays with K Different Integers Complexity Analysis

Time Complexity: O(n2 log n)

Outer Loop: for i = 0 to n - 1

  • Runs n times

Inner Loop: for j = i to n - 1

  • In worst case, runs n - i times
  • Over all i, this gives O(n²) total iterations

Inside Inner Loop:

  • freq is a std::map<int, int> → typically implemented as a balanced BST (like Red-Black Tree)
  • Inserting or updating a key (freq[nums[j]]++) is O(log D) time, where D is the number of distinct elements in the subarray so far (at most n)
  • freq.size() is constant time, since the map maintains size

So each inner iteration does O(log n) work in the worst case (when all elements are distinct).

Final Time Complexity

We do:

  • O(n²) iterations total
  • Each iteration does O(log n) operations on the map

Overall Time Complexity: O(n² * log n)

Space Complexity: O(n)

Auxiliary Space Complexity:

Auxiliary space refers to the extra memory used by the algorithm, excluding input and output.

In this brute-force solution:

  • A map<int, int> freq is used to store the frequency of elements in the current subarray.
    In the worst case, if all elements in a subarray are distinct, the map can grow to contain up to n entries (where n is the size of the input array). So, this takes O(n) space.
  • Aside from that, only a few scalar variables like i, j, n, and ans are used, which consume constant space O(1).

Auxiliary space complexity is O(n).

Total Space Complexity:

  1. Input space: The input vector nums contains n elements. Although passed by reference, the input still occupies O(n) space.
  2. Output space: The output is a single integer (ans), which uses O(1) space.
  3. Auxiliary space: As explained above, the map freq can take up to O(n) space in the worst case.

So, total space = input + output + auxiliary =
O(n) + O(1) + O(n) = O(n) (since O(n) dominates)

Total space complexity is O(n).

Is the Brute Force Approach Efficient?

The brute-force approach, while easy to understand and implement, is not efficient for larger inputs.

According to the problem constraints:

  • The size of the array can be as large as 2 × 10⁴
  • Each number in the array and the value of k can go up to n (the length of the array)

In the brute-force method, we go through every possible subarray, and for each one, we use a map to count unique elements. This results in a time complexity of O(n² × log n) in the worst case, which becomes extremely slow when n is around 20,000.

So while this approach might work for small arrays, it will time out or perform poorly for large inputs. That’s why we need to optimize the solution to handle bigger test cases within the time limits.


To optimize our solution, we can’t afford to visit every possible subarray that alone takes O(n²) time, which is too slow for large input sizes.
We need to do better than brute force by finding a smarter way to count subarrays with exactly k distinct elements without checking all of them one by one.
Let’s now explore how we can approach this more efficiently in the optimal solution.

Optimal Approach

Intuition

Let’s take a moment to understand what we’re trying to find here.

We need to count all the subarrays that have exactly k distinct elements.

Now, doing this directly can be a bit tricky. So instead, let’s make the problem a little easier by changing it slightly:

What if we count all the subarrays that have less than or equal to k distinct elements?

This version of the problem is simpler to solve. And here's the key idea:

If we count all the subarrays with at most k distinct elements, that includes:

  • Subarrays with exactly k distinct elements
  • Subarrays with exactly k - 1 distinct elements
  • Subarrays with exactly k - 2, k - 3, and so on, all the way down to 1 distinct element.

Now suppose, if we also find the count of subarrays with unique elements less than or equal to k-1. Then it will contain the following subarrays.

  • Subarrays with exactly k - 1
  • Subarrays with exactly k - 2, and so on, down to 1

Do you see what we can do here?

If we subtract the second count (at most k - 1) from the first count (at most k). We’ll be left with only the subarrays that have exactly k distinct elements, the ones we actually care about.

Now all we need to do is we need to subtract the count of subarrays with distinct elements less than or equal to k-1 from the count of subarrays with distinct elements less than or equal to k.

So, the final formula becomes:
Subarrays with exactly k distinct elements = Subarrays with at most k distinct elements - Subarrays with at most (k - 1) distinct elements

How to Count the Subarrays with Distinct Elements Less Than or Equal to K?

To solve this subproblem, we can’t afford to go through every possible subarray. That would take too long and wouldn’t be efficient, especially for large arrays.

So let’s think about it a bit differently.

Imagine we fix an index i somewhere in the array. Our goal is to count all valid subarrays that end at index i.
By "valid", we mean subarrays that contain at most k distinct elements.

To do this efficiently, we can use a sliding window approach with two pointers, one for the start of the window (l) and one for the end (r).

We’ll also use a map (in C++) or a dictionary (in Python) to keep track of how many times each element appears in the current window.

  • The key will be the element itself
  • The value will be the frequency of the elements (i.e., how many times it appears).

Here’s how it works step by step:

  • Start with both pointers, l and r at the beginning of the array.
  • Move the r pointer one step at a time to include a new element into the window.
  • For each new element added at r, update the map/dictionary to increase its frequency.
  • If the number of distinct elements in the current window (i.e., the size of the map) becomes more than k, it means the window is invalid.
    So we shrink the window from the left by moving l forward and decreasing the count of those elements in the map until the number of distinct elements becomes k or less again.
  • Once the window becomes valid again (i.e., it contains at most k distinct elements), we can count how many subarrays end at index r and are valid. These subarrays are:
    • Starting at l and ending at r
    • Starting at l + 1 and ending at r
    • Starting at r and ending at r
  • So, the number of such subarrays are: r - l + 1
  • We add this number to our final answer because all these subarrays ending at r are valid.
  • Then we move r forward and repeat the process until we reach the end of the array.

What is Sliding Window Technique?

Imagine you’re looking at a long line of items — like numbers in an array or letters in a string — and you want to examine small parts (subarrays or substrings) of it one at a time.

The Sliding Window Technique helps us do this efficiently, without starting over every time.

Instead of recalculating everything from scratch for each part, we slide a “window” over the data, reusing most of the previous work.

What is a “Window”?

A window is just a small segment or a range within the array or string.

For example:
Let’s say we have this array: arr = [1, 2, 3, 4, 5, 6]

If we want to look at subarrays of size 3:

  • First window: [1, 2, 3]
  • Next window: [2, 3, 4]
  • Then: [3, 4, 5], and so on...

Each time, we just move the window one step forward, dropping the first element and including the next.

Why Do We Use It?

Because it's efficient!

Let’s say we wanted the sum of each window of size 3:

Naive Way (Brute Force):

  • For every window, loop through the 3 elements and sum them → O(n * k), where n = length of array, k = window size.

Sliding Window Way:

Sum the first window once. For the next window:

  • Subtract the element going out of the window.
  • Add the element coming in.

This makes each new window sum in O(1) time → total O(n).

Types of Sliding Windows

There are mainly two types:

1. Fixed-size Sliding Window - Window size stays the same.

2. Variable-size Sliding Window - The window grows or shrinks based on conditions.

In this problem, we are using fixed size Sliding Window as the window size if fixed, i.e. length of p.

Subarrays with K Different Integers Algorithm

Step 1: Create the Helper Function (countAtMostK)

Write a separate function to count the number of subarrays that contain at most k distinct elements. This will use the sliding window approach.

Step 2: Prepare for the Sliding Window

Inside the helper function:

  • Get the size of the array.
  • Set up a map (or dictionary) to track the frequency of elements in the current window.
  • Initialise two pointers, l (left) and r (right), to represent the sliding window.
  • Also, initialise a variable to keep track of the total valid subarrays found.

Step 3: Slide the Right Pointer

Loop through the array using the right pointer r. At each step, add the current element to the frequency map and update its count.

Step 4: Shrink the Window if Needed

If the number of distinct elements in the window (i.e., the size of the map) becomes greater than k, shrink the window from the left by moving the l pointer forward. Decrease the frequency of the leftmost element, and if its count becomes zero, remove it from the map.

Step 5: Count Valid Subarrays

After making sure the window has at most k distinct elements, add the number of valid subarrays ending at index r (which is r - l + 1) to your answer.

Step 6: Repeat Until the End of the Array

Continue moving the r pointer and repeat steps 3 to 5 until the end of the array is reached.

Step 7: Return the Result

Once the loop ends, return the final count of subarrays with less than or equal to k distinct elements from the helper function.

Step 9: Compute Final Answer

Back in the main function, subtract the result of countAtMostK(k - 1) from countAtMostK(k) to get the number of subarrays with exactly k distinct elements, and return it.

0:00
/2:43

Animation of Subarrays with K Different Integers - Optimal Approach

Subarrays with K Different Integers Example

Input: nums = [1,2,2,1], k = 2
Output: 5
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [1, 2, 2], [1,2, 2, 1], [2,2,1], [2,1]

  • nums = [1, 2, 2, 1]
  • k = 2

The main idea of this code:

result = countAtMostK(nums, k) - countAtMostK(nums, k - 1)

So we will compute:

  • countAtMostK(nums, 2) → count of subarrays with at most 2 distinct elements
  • countAtMostK(nums, 1) → count of subarrays with at most 1 distinct element
  • Subtract the two to get exactly 2 distinct elements

Step 1: countAtMostK(nums, 2)

Let’s do a dry run of this using a sliding window

We’ll use:

  • mp to store counts of elements
  • Two pointers: l (left), r (right)

Initial values:

  • l = 0, r = 0, ans = 0, mp = {}

r = 0

  • Add 1: mp = {1:1}
  • size = 1 (≤ 2) → Yes
  • Add r - l + 1 = 1 → ans = 1

r = 1

  • Add 2: mp = {1:1, 2:1}
  • size = 2 (≤ 2) → Yes
  • Add r - l + 1 = 2 → ans = 3

r = 2

  • Add 2: mp = {1:1, 2:2}
  • size = 2 → Yes
  • Add r - l + 1 = 3 → ans = 6

r = 3

  • Add 1: mp = {1:2, 2:2}
  • size = 2 → Yes
  • Add r - l + 1 = 4 → ans = 10

Done — countAtMostK(nums, 2) = 10

Step 2: countAtMostK(nums, 1)

Reset:

  • l = 0, r = 0, ans = 0, mp = {}

r = 0

  • Add 1: mp = {1:1}
  • size = 1 → Yes
  • Add 1 → ans = 1

r = 1

  • Add 2: mp = {1:1, 2:1}
  • size = 2 (> 1) → No shrink from left
    • Remove 1: mp = {2:1}
    • l = 1
  • Add r - l + 1 = 1 → ans = 2

r = 2

  • Add 2: mp = {2:2}
  • size = 1 → Yes
  • Add r - l + 1 = 2 → ans = 4

r = 3

  • Add 1: mp = {2:2, 1:1}
  • size = 2 → No shrink
    • Remove 2: mp = {2:1, 1:1} → still 2
    • l = 2
    • Remove 2: mp = {1:1}
    • l = 3
  • size = 1 → Yes
  • Add r - l + 1 = 1 → ans = 5

Done — countAtMostK(nums, 1) = 5

Final Calculation: subarraysWithKDistinct(nums, 2) = 10 - 5 = 5

Subarrays with K Different Integers leetcode Solution
Subarrays with K Different Integers solution in C++
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        // Use the helper function: atMostK for k and k-1, and return their difference
        return countAtMostK(nums, k) - countAtMostK(nums, k - 1);
    }

    // Function to count subarrays with at most K distinct integers
    int countAtMostK(vector<int>& nums, int k) {
        // Get the size of the array
        int n = nums.size();
        // Map to store frequency of elements in the current window
        map<int, int> mp;
        // Initialize left and right pointers for window
        int l = 0, r = 0;
        // Initialize answer to 0
        int ans = 0;

        // Move the right pointer through the array
        while (r < n) {
            // Add nums[r] to the frequency map
            mp[nums[r]]++;

            // If we have more than k distinct elements, shrink the window from the left
            while (mp.size() > k) {
                mp[nums[l]]--;
                // If the count of nums[l] is zero, remove it from the map
                if (mp[nums[l]] == 0) mp.erase(nums[l]);
                // Move the left pointer to the right
                l++;
            }

            // Add the number of subarrays ending at r and starting from l to r
            ans += r - l + 1;
            // Move the right pointer to the right
            r++;
        }
        // Return the total count
        return ans;
    }
};

Subarrays with K Different Integers solution in Java
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // Use the helper function: atMostK for k and k-1, and return their difference
        return countAtMostK(nums, k) - countAtMostK(nums, k - 1);
    }

    // Function to count subarrays with at most K distinct integers
    public int countAtMostK(int[] nums, int k) {
        // Get the size of the array
        int n = nums.length;
        // Map to store frequency of elements in the current window
        Map<Integer, Integer> mp = new HashMap<>();
        // Initialize left and right pointers for window
        int l = 0, r = 0;
        // Initialize answer to 0
        int ans = 0;

        // Move the right pointer through the array
        while (r < n) {
            // Add nums[r] to the frequency map
            mp.put(nums[r], mp.getOrDefault(nums[r], 0) + 1);

            // If we have more than k distinct elements, shrink the window from the left
            while (mp.size() > k) {
                mp.put(nums[l], mp.get(nums[l]) - 1);
                // If the count of nums[l] is zero, remove it from the map
                if (mp.get(nums[l]) == 0) mp.remove(nums[l]);
                // Move the left pointer to the right
                l++;
            }

            // Add the number of subarrays ending at r and starting from l to r
            ans += r - l + 1;
            // Move the right pointer to the right
            r++;
        }
        // Return the total count
        return ans;
    }
}

Subarrays with K Different Integers solution in Python
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        # Use the helper function: atMostK for k and k-1, and return their difference
        return self.countAtMostK(nums, k) - self.countAtMostK(nums, k - 1)

    # Function to count subarrays with at most K distinct integers
    def countAtMostK(self, nums: List[int], k: int) -> int:
        # Get the size of the array
        n = len(nums)
        # Dictionary to store frequency of elements in the current window
        freq = {}
        # Initialize left pointer for window
        l = 0
        # Initialize answer to 0
        ans = 0

        # Move the right pointer through the array
        for r in range(n):
            # Add nums[r] to the frequency dictionary
            freq[nums[r]] = freq.get(nums[r], 0) + 1

            # If we have more than k distinct elements, shrink the window from the left
            while len(freq) > k:
                freq[nums[l]] -= 1
                # If the count of nums[l] is zero, remove it from the dictionary
                if freq[nums[l]] == 0:
                    del freq[nums[l]]
                # Move the left pointer to the right
                l += 1

            # Add the number of subarrays ending at r and starting from l to r
            ans += r - l + 1

        # Return the total count
        return ans

Subarrays with K Different Integers solution in Javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function(nums, k) {
    // Return the difference between atMostK for k and k-1
    return countAtMostK(nums, k) - countAtMostK(nums, k - 1);

    // Function to count subarrays with at most K distinct integers
    function countAtMostK(nums, k) {
        // Get the size of the array
        const n = nums.length;
        // Map to store frequency of elements in the current window
        const freq = new Map();
        // Initialize left pointer for window
        let l = 0;
        // Initialize answer to 0
        let ans = 0;

        // Move the right pointer through the array
        for (let r = 0; r < n; ++r) {
            // Add nums[r] to the frequency map
            freq.set(nums[r], (freq.get(nums[r]) || 0) + 1);

            // If we have more than k distinct elements, shrink the window from the left
            while (freq.size > k) {
                freq.set(nums[l], freq.get(nums[l]) - 1);
                // If the count of nums[l] is zero, remove it from the map
                if (freq.get(nums[l]) === 0) freq.delete(nums[l]);
                // Move the left pointer to the right
                l++;
            }

            // Add the number of subarrays ending at r and starting from l to r
            ans += r - l + 1;
        }
        // Return the total count
        return ans;
    }
};

Subarrays with K Different Integers Complexity Analysis

Time Complexity: O(n logn)

1. Function countAtMostK(nums, k)

This function uses the sliding window technique, where:

  • r goes from 0 to n - 1
  • l only moves forward when the distinct count exceeds k
  • The key insight: both l and r move at most n times

So, the entire while loop runs in O(n) time.

Each operation inside the loop involves:

  • Inserting or deleting from map<int, in> → takes O(log n) time (because std::map is implemented as a balanced BST)

Thus, each step takes O(log n) time, and there are O(n) steps → overall time:
O(n × log n)

2. Main Function subarraysWithKDistinct

It calls countAtMostK(nums, k) and countAtMostK(nums, k - 1), each of which runs in O(n × log n) time.

So:

Total Time Complexity = O(n × log n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

Auxiliary Space Complexity:

This refers to all extra memory used by the algorithm (excluding input and output).

In the optimal solution:

  • A map<int, int> (or unordered_map if used instead) is maintained to store the frequency of elements in the current sliding window.
    • In the worst case, if all elements in the array are distinct, the map will store up to n elements.
    • So, the frequency map takes O(n) space.
  • Other variables (l, r, ans, loop counters) are scalar values and use O(1) space.

So, auxiliary space complexity = O(n).

Total Space Complexity:

Total space includes:

  • Input space: the array nums, which contains n elements → O(n)
  • Output space: a single integer result → O(1)
  • Auxiliary space: from above → O(n)

Combining these:

Total Space = Input + Output + Auxiliary = O(n) + O(1) + O(n) = O(n)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

Given a string s, find the length of the longest substring without duplicate characters.

substring is a contiguous (non-empty) sequence of characters within a string.

vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Given an integer array nums and two integers k and p, return the number of distinct subarrays, which have at most k elements that are divisible by p.

Two arrays nums1 and nums2 are said to be distinct if:

  • They are of different lengths, or
  • There exists at least one index i where nums1[i] != nums2[i].

subarray is defined as a non-empty contiguous sequence of elements in an array.

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

  • The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

subarray is a contiguous non-empty part of an array.