Subarrays with K Different Integers Leetcode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg Google Uber
Array Counting Hashing Let Netlfix Sliding WindowViews 2935

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 »