# Subarrays with K Different Integers Leetcode Solution

Difficulty Level Hard
Array Counting Hashing Let Netlfix Sliding WindowViews 1857

## Problem Statement

The Subarrays with K Different Integers LeetCode Solution – “Subarrays with K Different Integers” states that you’re given an integer array nums and an integer k. We need to find a total number of good subarrays of nums.

A good array is defined as an array with exactly k distinct integers, whereas a subarray is defined as a contiguous part of an array.

## Example:

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

Explanation:

• There is a total of 15 subarrays.
• Subarrays with exactly k distinct integers are: [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 with exactly 3 distinct integers are: [1,2,1,3], [2,1,3], [1,3,4].

## Approach

### Idea:

1. The main idea to solve this problem is to use Hashmap and the sliding window technique.
2. Let S(k) be the total number of subarrays with at most k distinct elements.
3. Then, we need to find S(k) – S(k-1).
4. To calculate S(k), we will use the sliding window technique to find the required number of elements.
1. We’ll keep two pointers i and j, and each time we’ll increment the forward pointer i by 1 unit.
2. Also, for each forward pointer i, we’ll try to find the least index j such that j<=i and the number of distinct elements in the range [j, i] is not greater than k.
3. For each position of i, we’ll add the required valid subarrays i – j + 1 to our answer.
5. We’ll return our answer as S(k) – S(k-1).

## Code

### Subarrays with K Different Integers Leetcode C++ Solution:

```class Solution {
public:
int AtmostK(vector<int>& nums,int k){
unordered_map<int,int> freq;
int n = nums.size(),ans = 0,j = 0;
for(int i=0;i<n;i++){
freq[nums[i]]++;
if(freq[nums[i]]==1){
k--;
}
while(k<0){
freq[nums[j]]--;
if(!freq[nums[j]]){
k++;
}
j++;
}
ans += i - j + 1;
}
return ans;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
int ans = AtmostK(nums,k) - AtmostK(nums,k-1);
return ans;
}
};```

### Subarrays with K Different Integers Leetcode Java Solution:

```class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
return atMostK(A, K) - atMostK(A, K - 1);
}
int atMostK(int[] A, int K) {
int i = 0, res = 0;
Map<Integer, Integer> count = new HashMap<>();
for (int j = 0; j < A.length; ++j) {
if (count.getOrDefault(A[j], 0) == 0) K--;
count.put(A[j], count.getOrDefault(A[j], 0) + 1);
while (K < 0) {
count.put(A[i], count.get(A[i]) - 1);
if (count.get(A[i]) == 0) K++;
i++;
}
res += j - i + 1;
}
return res;
}
}```

## Complexity Analysis for Subarrays with K Different Integers Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N) since we traverse the entire array in a linear time and a good hash function allows insertion and deletion in O(1) time, where N =  size of the input array. We can also use a hashmap that allows insertion and deletion in logarithmic time.

### Space Complexity

The space complexity of the above code is O(N) since the maximum size of the hashmap can be O(N).

Translate »