Subarrays With K Different Integers - Leetcode Solution

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<Integer,Integer> map=new HashMap<>(); int left=0,distinct=0; for(int right=0;right<n;right++){ if(map.getOrDefault(nums[right],0)==0){ distinct++; } map.put(nums[right],map.getOrDefault(nums[right],0)+1); while(distinct>k){ 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)

1