# Solution For Subarrays With K Different Integers

Problem Statement:
You are given an integer array nums and an integer k.
Return the number of contiguous subarrays that contain at least k distinct integers.

Example:
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: The subarray [1,2,1,2] contains 2 different integers, [1,2,1,2,3] contains 3 different integers, [2,1,2,3] contains 3 different integers, [1,2,3] contains 3 different integers, [2,3] contains 2 different integers, [1,2] contains 2 different integers, and  contains 1 different integer.

Approach:
The problem can be solved using the sliding window approach. The basic idea is to maintain a window of integers that contains at least k distinct integers. We start with a window of size one and keep on increasing its size until it contains k distinct integers. After that, we start sliding the window while keeping track of the number of subarrays that satisfy the condition of containing at least k distinct integers.

Algorithm:

1. Initialize two pointers left and right to the start of the array and a hashmap to store the count of distinct integers.
2. Initialize a variable count to store the number of subarrays that contain at least k distinct integers and another variable distinct to store the number of distinct integers in the current window.
3. Loop through the array until right< length of the array:
4. If the count of the current integer in the hashmap is zero, increment the distinct variable and add the current integer to the hashmap with count 1.
5. If the count of the current integer in the hashmap is greater than zero, increment its count.
6. If the value of the distinct variable is greater than k, remove the leftmost integer from the hashmap and decrement the distinct variable until it becomes less than k.
7. Increment the count variable by right-left+1.
8. Increment the left pointer by 1.
9. Return the count variable.

Code:

class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
int n=nums.length;
int count=0;
Map map=new HashMap<>();
int left=0,distinct=0;
for(int right=0;rightk){
map.put(nums[left],map.get(nums[left])-1);
if(map.get(nums[left])==0){
distinct–;
}
left++;
}
if(distinct==k){
int j=left;
while(map.get(nums[j])>1){
map.put(nums[j],map.get(nums[j])-1);
j++;
}
count+=j-left+1;
}
}
return count;
}
}

Time Complexity: O(N)
Space Complexity: O(N)

## Step by Step Implementation For Subarrays With K Different Integers

```class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
// TODO: Write your code here
int windowStart = 0, result = 0, distinctCount = 0;
Map map = new HashMap<>();

for (int windowEnd = 0; windowEnd < A.length; windowEnd++) {
int rightElement = A[windowEnd];
if (map.containsKey(rightElement)) {
map.put(rightElement, map.get(rightElement) + 1);
} else {
map.put(rightElement, 1);
distinctCount++;
}

while (distinctCount > K) {
int leftElement = A[windowStart];
map.put(leftElement, map.get(leftElement) - 1);
if (map.get(leftElement) == 0) {
distinctCount--;
}
windowStart++;
}

if (distinctCount == K) {
result += 1;
}
}

return result;
}
}```
```Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

def subarraysWithKDistinct(A, K):

# keep track of the number of good subarrays with exactly K distinct integers
num_good_subarrays = 0

# keep track of the number of good subarrays with at most K distinct integers
num_subarrays_at_most_K = 0

# dictionary to keep track of the number of occurrences of each integer
num_occurrences = {}

# loop through the array
for i in range(len(A)):

# update the dictionary
if A[i] in num_occurrences:
num_occurrences[A[i]] += 1
else:
num_occurrences[A[i]] = 1

# if we have seen this integer before, there is nothing new to add
if num_occurrences[A[i]] > 1:
continue

# update the number of good subarrays with at most K distinct integers
num_subarrays_at_most_K += 1

# if we have K distinct integers already, we need to remove one
if len(num_occurrences) == K:

# find the leftmost integer that we need to remove
leftmost = -1
for j in range(i-1, -1, -1):
if A[j] in num_occurrences:
leftmost = j
break

# remove it from the dictionary
num_occurrences[A[leftmost]] -= 1
if num_occurrences[A[leftmost]] == 0:
del num_occurrences[A[leftmost]]

# update the number of good subarrays with at most K distinct integers
num_subarrays_at_most_K -= 1

# update the number of good subarrays with exactly K distinct integers
num_good_subarrays += num_subarrays_at_most_K

return num_good_subarrays```
```var subarraysWithKDifferentIntegers = function(A, K) {
// create a hash map to store the counts of each integer
let map = {};
// create a variable to store the number of subarrays with K different integers
let count = 0;

// iterate through the array
for (let i = 0; i < A.length; i++) {
// if the integer is not in the hash map, add it with a count of 1
if (!(A[i] in map)) {
map[A[i]] = 1;
// if the integer is in the hash map, increment the count
} else {
map[A[i]]++;
}

// create a variable to store the number of different integers
let numDifferentIntegers = Object.keys(map).length;

// if the number of different integers is equal to K
if (numDifferentIntegers === K) {
// increment the count
count++;
// if the number of different integers is greater than K
} else if (numDifferentIntegers > K) {
// remove the first integer from the hash map
map[A[i-K]]--;
// if the count of the first integer is now 0, remove it from the hash map
if (map[A[i-K]] === 0) {
delete map[A[i-K]];
}
}
}

return count;
};```
```There are several ways to solve this problem. One approach is to use a hashtable to keep track of the number of times each number appears in the subarray. Then, we can iterate through the array and check if the current number has appeared less than k times. If so, we add it to the subarray. Otherwise, we remove the first number from the subarray and add the current number.

Another approach is to use a sliding window. We can keep a running count of the number of times each number appears in the subarray. Then, we can check if the current number has appeared less than k times. If so, we add it to the subarray. Otherwise, we remove the first number from the subarray and add the current number.```
```using System;

public class GFG {

// Returns count of subarrays with exactly k distinct
// elements.
static int countSubarrays(int[] arr,
int k)
{

// Initialize result
int res = 0;

// Consider all subarrays
for (int i = 0; i < arr.Length; i++)
{
// Initialize count of different
// elements as k
int cnt = k;

// Consider all subarrays starting
// from arr[i]
for (int j = i; j < arr.Length; j++)
{
// If this is a new element,
// increment count.
if (cnt > 0 &&
(!arr[j].Equals(arr[j - 1])))
cnt--;

// If all the 'k' elements
// become distinct,
// then increment count of
// subarrays.
if (cnt == 0)
res++;
}
}
return res;
}

// Driver code
public static void Main()
{
int[] arr = { 2, 1, 2, 1, 6 };
int k = 2;
Console.WriteLine(countSubarrays(arr, k));
}
}

// This code is contributed by Akanksha Rai(Abinash)```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]