992. subarrays with k different integers

Guri Bee

2 min read

·

21-10-2024

1

0

Share

Mastering Subarrays with K Different Integers: A Comprehensive Guide

Counting subarrays with a specific number of distinct elements can be a tricky problem in programming. This article explores the "992. Subarrays with K Different Integers" problem on LeetCode, providing a clear understanding of its solution using a sliding window technique.

Understanding the Problem

Given an array of integers nums and an integer k, the task is to find the number of subarrays that contain exactly k different integers. Let's break down the problem:

• Subarray: A contiguous sequence of elements within the array.
• Distinct Integers: Unique integers within a subarray.

Example:

For nums = [1, 2, 1, 3, 4] and k = 3, the subarrays with exactly 3 different integers are:

• [1, 2, 1, 3]
• [2, 1, 3, 4]

Solution using Sliding Window

The most efficient way to solve this problem is using a sliding window approach. This involves the following steps:

1. Initialization:

   • Initialize two pointers, left and right, both pointing to the beginning of the array.
   • Create a dictionary (or hashmap) called freq to store the frequency of each element within the current window.
   • Initialize a counter count to keep track of the number of distinct elements in the current window.

2. Sliding Window:

   • Expand the window: Increment the right pointer, adding the new element to the freq dictionary and updating the count.
   • Shrink the window: If the count becomes greater than k, move the left pointer to the right until the count is equal to k. This involves removing the element at the left pointer from the freq dictionary and updating the count.
   • Calculate Subarray Count: For every valid window (where count equals k), increment the result counter.

3. Return the Result: The final result counter will hold the number of subarrays with exactly k different integers.

Python Implementation:

def subarraysWithKDistinct(nums, k):
    """
    Counts the number of subarrays with exactly k distinct integers.

    Args:
        nums (list): The input array of integers.
        k (int): The target number of distinct integers.

    Returns:
        int: The number of subarrays with exactly k distinct integers.
    """
    left = 0
    right = 0
    freq = {}
    count = 0
    result = 0

    while right < len(nums):
        # Expand the window
        freq[nums[right]] = freq.get(nums[right], 0) + 1
        if freq[nums[right]] == 1:
            count += 1

        # Shrink the window if count exceeds k
        while count > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                count -= 1
            left += 1

        # Update the result if the count equals k
        if count == k:
            result += right - left + 1

        right += 1

    return result

Key Points:

• Time Complexity: O(n) - The sliding window approach ensures each element is processed at most twice (once for expanding and once for shrinking the window).
• Space Complexity: O(n) - The dictionary freq can store up to n unique elements.

Example Usage:

nums = [1, 2, 1, 3, 4]
k = 3

count = subarraysWithKDistinct(nums, k)
print(f"Number of subarrays with {k} distinct integers: {count}") 

Output:

Number of subarrays with 3 distinct integers: 2

Further Insights:

• This problem demonstrates the power of sliding windows for solving problems involving contiguous subarrays.
• The use of a dictionary to track element frequencies efficiently maintains the count of distinct elements in the window.
• The code can be easily adapted to handle cases where k is zero or negative, simply returning 0 for such scenarios.

Conclusion:

Understanding the sliding window technique and its applications is crucial for efficiently solving problems related to subarrays. This article provides a comprehensive explanation of the "992. Subarrays with K Different Integers" problem, empowering you with the knowledge to tackle similar problems with confidence.