Subarrays with Distinct Integers

About the problem:

Given a vector of integers, a subarray is taken into consideration differently if there are exactly k distinct integers in it, and the output will be the quantity of such subarrays.

Example 1:

Input: [ 2 , 5 , 2 , 6 , 5 , 4 , 3 ] ,K = 3

Output: 7

Explanation: Subarrays are- [ 2 , 5 , 2 , 6 ] , [ 5 , 2 , 6 ] , [ 2 , 6 , 5 ] , [ 5 , 2 , 6 , 5 ] , [ 6 , 5 , 4 ] , [ 5 , 4 , 3 ] , [ 2 , 5 , 2 , 6 , 5 ]

Example 2:

Input: [ 7 , 6 , 8 , 1 , 5, 1 , 3 , 4 , 5 ] ,K = 4

Output: 7

Explanation: Subarrays are- [ 7 , 6 , 8 , 1 ] , [ 6 , 8 , 1 , 5 ] , [ 8 , 1 , 5 , 1 , 3 ] , [ 1 , 5 , 1 , 3 , 4 ] , [ 5 , 1 , 3 , 4 ] , [ 1 , 3 , 4 , 5 ] , [ 1 , 5 , 1 , 3 , 4 , 5  ]

Approach #1: Brute Force

Using this approach we iterate over each subarray using nested loops. Here, from i to j where i is the first loop and j is the second and push those into a set, then check if the set size is k or not.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int subarraysWithKDistinct(vector < int > & nums, int k) {

  int count = 0;
  int n = nums.size();

  for (int x = 0; x < n; x++)
    for (int y = i; y < n; y++) {
      if (y - x + 1 < k) continue;

      set < int > sd;
      for (int z = x; z <= y; z++) sd.insert(nums[z]);

      if (sd.size() == k) count++;
    }

  return count;
}

Time complexity: O(n³), we are using three nested loops.
Space complexity: O(n), for storing integers in the set.

Approach #2: Using an Explicit Set

In this approach, to reduce complexity we insert into a set until the set size is equal to k then increment the ans variable. Then we again insert into the set if the size doesn’t change and increment the ans each time.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int subarraysWithKDistinct(vector < int > & nums, int k) {

  int count = 0;
  int n = nums.size();

  for (int i = 0; i < n; i++) {
    set < int > ss;

    int j = i;
    while (j < n && ss.size() < k) ss.insert(nums[j++]);

    if (ss.size() == k) {
      count++;
      while (j < n) {
        ss.insert(nums[j]);
        if (ss.size() == k) {
          count++;
          j++;
        } else break;
      }
    }
  }

  return count;
}

Time complexity: O(n²), we are using two nested loops.
Space complexity: O(k), as the size of the set can be at most k.

Approach #3: Sliding Window

In this approach, we first count the subarrays with at most k distinct integers and then count subarrays with at most k-1 distinct integers. The result will be the difference between these two.
To calculate the at most k values we can use the sliding window technique. In the sliding window approach we expand right until the count of distinct integers is less than or equal to k and increment the ans by end -start + 1, when the count is greater than k, now start incrementing the starting position until the count is less than k.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int at_most(vector < int > A, int k) {
  int n = A.size(), s = 0, ans = 0, j = 0, i = 0;
  unordered_map < int, int > mp;
  while (j < n) {
    mp[A[j]]++;
    while (mp.size() > k) {
      mp[A[i]]--;
      if (mp[A[i]] == 0) mp.erase(A[i]);
      i++;
    }
    ans += (j - i + 1);
    j++;
  }
  return ans;
}

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

Time complexity: O(n), we are iterating over nums array once.
Space complexity: O(k), as the size of the map can be at most k.