LeetCode 992: Subarrays with K Different Integers Solution

Master LeetCode problem 992 (Subarrays with K Different Integers), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

992. Subarrays with K Different Integers

Hard

Array Hash Table Sliding Window Counting

Problem Explanation

Explanation:

To solve this problem, we can use a sliding window approach. We maintain a window that contains at most k different integers. We keep expanding the window until we have exactly k different integers. Once we have more than k different integers, we contract the window from the left until we have exactly k different integers again.

We can keep track of the count of subarrays with exactly k different integers by counting the number of valid subarrays that can be formed when a new element is added to the window.

Solution Code

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
    }
    
    private int atMostKDistinct(int[] nums, int k) {
        int n = nums.length;
        int left = 0, count = 0, result = 0;
        Map<Integer, Integer> freqMap = new HashMap<>();
        
        for (int right = 0; right < n; right++) {
            int num = nums[right];
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            
            if (freqMap.get(num) == 1) {
                count++;
            }
            
            while (count > k) {
                int leftNum = nums[left];
                freqMap.put(leftNum, freqMap.get(leftNum) - 1);
                if (freqMap.get(leftNum) == 0) {
                    count--;
                }
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 992 (Subarrays with K Different Integers)?

This page provides optimized solutions for LeetCode problem 992 (Subarrays with K Different Integers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 992 (Subarrays with K Different Integers)?

The time complexity for LeetCode 992 (Subarrays with K Different Integers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 992 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 992 in Java, C++, or Python.

Back to LeetCode Solutions