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 [3] 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):
    # write your code here
    
    # 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)