992. Subarrays with K Different Integers

Problem Statement

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

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

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

• 1 <= nums.length <= 2 * 104

• 1 <= nums[i], k <= nums.length

Intuition

Approach :
Use atmost approach to get exactly k elements

Basically at every point in high-low+1

We add extra subarrays

example 
1 2 1 2 3
l h

h-l+1
adds 2 here which is, 2, 1 2
Count 

Links

https://leetcode.com/problems/subarrays-with-k-different-integers/description/

Video Links

Approach 1:

Atmost Sliding Window

C++

class Solution {
public:
    int Atmost(vector<int>& nums, int k){
        unordered_map<int, int> mp;
        int low=0;
        int ans=0;

        for(int high=0; high<nums.size(); high++){
            mp[nums[high]]++;

            while(mp.size() > k){
                if(mp[nums[low]] == 1)
                    mp.erase(nums[low]);
                else
                    mp[nums[low]]--;

                low++;
            }

            ans += high-low+1;
        } 

        return ans;
    }

    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return Atmost(nums, k) - Atmost(nums, k-1);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems

https://leetcode.com/problems/binary-subarrays-with-sum/description/ https://leetcode.com/problems/count-number-of-nice-subarrays/description/