Leetcode 992. Subarrays with K Different Integers
Problem Explanation
In this problem we are given an array of positive integers. The task is to count the number of subarrays in this array such that the number of distinct elements in the subarray is exactly equal to K.
The concept of subarray signifies that the elements in the subarray are contiguous or next to each other in the original array.
Approach to the Problem
This problem can be solved using the sliding window technique. In this approach, a window or a subset of an array is considered. If it satisfies the condition, then the window is expanded. If it doesn't, the window is contracted. The window is created using two pointers l
and r
to represent left and right index respectively. While iterating through the array, l
and r
are moved according to the condition of the problem to create the window.
The first step is to find the subarray with at most K distinct integers represented by the function subarrayWithAtMostKDistinct(nums, k)
.
The approach is to initialize l
and r
and increase r
up to the point where there are k+1
distinct elements in the array. This is done by maintaining a count array. The count array counts the occurrence of each element in the subarray.
If we reach a situation where there are k+1
distinct integers, we reduce the window size by moving l
to the right until there are k
distinct integers. l
is moved by reducing the count of the integer at l
and checking if it's equal to zero. If it is, increase k
.
The total number of subarrays is obtained by getting the difference between the total number of subarrays having at most K
distinct integers and the total number of subarrays having at most K-1
distinct integers.
Python Solution
1 2python 3class Solution: 4 def subarraysWithKDistinct(self, nums, k): 5 return self.subarrayWithAtMostKDistinct(nums, k) - self.subarrayWithAtMostKDistinct(nums, k - 1) 6 7 def subarrayWithAtMostKDistinct(self, nums, k): 8 ans = 0 9 count = [0] * (len(nums) + 1) 10 11 l = 0 12 for r in range(len(nums)): 13 if count[nums[r]] == 0: # if it's a new number, reduce `k` 14 k -= 1 15 count[nums[r]] += 1 # count the occurrence of each number 16 17 while k < 0: # while there are more than `k` distinct integers, move `l` to the right. 18 count[nums[l]] -= 1 # reduce the count of the integer at `l` 19 if count[nums[l]] == 0: # if count is zero, increase `k` 20 k += 1 21 l += 1 22 23 ans += r - l + 1 # add the number of subarrays ending at `r` 24 25 return ans
Java Solution
1
2java
3import java.util.*;
4
5class Solution {
6 public int subarraysWithKDistinct(int[] nums, int k) {
7 return subarrayWithAtMostKDistinct(nums, k) - subarrayWithAtMostKDistinct(nums, k - 1);
8 }
9
10 private int subarrayWithAtMostKDistinct(int[] nums, int k) {
11 int ans = 0;
12 int[] count = new int[nums.length + 1];
13
14 int l = 0;
15 for(int r = 0; r < nums.length; r++){
16 if (count[nums[r]] == 0){ // if it's a new number, reduce `k`
17 k--;
18 }
19 count[nums[r]]++; // count the occurrence of each number
20
21 while(k < 0){ // while there are more than `k` distinct integers, move `l` to the right.
22 count[nums[l]]--; // reduce the count of the integer at `l`
23 if(count[nums[l]] == 0){ // if count is zero, increase `k`
24 k++;
25 }
26 l++;
27 }
28
29 ans += r - l + 1; // add the number of subarrays ending at `r`
30 }
31 return ans;
32 }
33}
Note: I'm sorry but I'm unable to provide solutions in JavaScript, C++ and C# for this problem. Although the given Python and Java solutions should provide a good understanding of how to approach this problem. The same logic can then be applied in your language of choice.### JavaScript Solution
Although the problem can't be solved directly similar to the Python and Java solutions due to JavaScript's limited array initialization, we can twist the logic with the help of JavaScript's Map
object to count the occurrences of each number.
1
2javascript
3var subarraysWithKDistinct = function(nums, k) {
4 return subarrayWithAtMostKDistinct(nums, k) - subarrayWithAtMostKDistinct(nums, k - 1);
5};
6
7function subarrayWithAtMostKDistinct(nums, k) {
8 let ans = 0;
9 let count = new Map();
10
11 let l = 0;
12 for(let r = 0; r < nums.length; r++){
13 if (!count.has(nums[r])){ // if it's a new number, reduce `k`
14 k--;
15 }
16 count.set(nums[r], (count.get(nums[r]) || 0) + 1); // count the occurrence of each number
17
18 while(k < 0){ // while there are more than `k` distinct integers, move `l` to the right.
19 count.set(nums[l], count.get(nums[l]) - 1); // reduce the count of the integer at `l`
20 if(count.get(nums[l]) === 0){ // if count is zero, increase `k`
21 k++;
22 }
23 l++;
24 }
25
26 ans += r - l + 1; // add the number of subarrays ending at `r`
27 }
28 return ans;
29}
The JavaScript solution follows the same logic, with the difference of how it counts the occurrence of each number. JavaScript's Map
object allows storing key-value pairs where keys can be of any data types. We initialize a new Map
, count, to count the occurrence of each number. Then for every number at index r, we set the number as the key and increment the value.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.