We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subarrays with K Different Integers

Number: 1034

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Microsoft, Roblox, Morgan Stanley, TikTok, Oracle, Meta, Adobe, Uber, Squarepoint Capital

Problem Description

Given an array of integers, nums, and an integer k, return the number of contiguous subarrays (good subarrays) that contain exactly k different integers. A good subarray is defined as one having exactly k unique integers.

Key Insights

  • Count subarrays with exactly k distinct integers by leveraging the sliding window technique.
  • Use the trick: the number of subarrays with exactly k distinct = subarrays with at most k distinct - subarrays with at most (k-1) distinct.
  • Maintain a hash map (or dictionary) to count frequency of array elements as you expand and contract the sliding window.
  • Carefully update your window boundaries to ensure the count is maintained correctly.

Space and Time Complexity

Time Complexity: O(n) for each helper sliding window (total O(n) since each element is processed a constant number of times) Space Complexity: O(n) in the worst case, due to the hash map storing frequencies of unique numbers.

Solution

To solve the problem, we use a sliding window technique combined with a helper function that counts subarrays with at most k distinct integers. The idea is:

  1. Create a helper function countAtMost(K) that returns the number of subarrays with at most K distinct integers.
  2. In the helper, maintain two pointers (left and right) for the sliding window and a frequency map.
  3. For each position of right pointer, update the frequency map. If the number of distinct integers exceeds K, move the left pointer to reduce it.
  4. The total subarrays ending at the current right are added to the answer.
  5. The final answer is: countAtMost(k) - countAtMost(k - 1).

This approach ensures we efficiently count valid subarrays without needing to re-calculate subarray properties repeatedly.

Code Solutions

# Python code solution with line-by-line comments
def subarraysWithKDistinct(nums, k):
    # Helper function to count subarrays with at most K distinct integers
    def atMostKDistinct(K):
        count = {}  # dictionary to hold frequency of elements
        left = result = 0
        # Iterate over nums using the right pointer
        for right, value in enumerate(nums):
            count[value] = count.get(value, 0) + 1  # update frequency
            # If distinct integers exceed K, move left pointer to adjust window
            while len(count) > K:
                count[nums[left]] -= 1  # reduce frequency for element at left
                if count[nums[left]] == 0:
                    del count[nums[left]]  # remove element if frequency is zero
                left += 1  # shrink window from left
            # All subarrays ending at right with at most K distinct integers
            result += right - left + 1
        return result

    # The number of subarrays with exactly k distinct integers
    return atMostKDistinct(k) - atMostKDistinct(k - 1)

# Example usage:
#print(subarraysWithKDistinct([1,2,1,2,3], 2))  # Output: 7
← Back to All Questions