Subarrays with K Different Integers

This solution addresses the classic problem of counting subarrays with exactly K distinct integers using a sliding window approach that efficiently handles the constraint of precise integer counts within subarrays.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the input array size and element values? (e.g., is it bounded, can elements be negative?)
2. Can we modify the input array in-place? (This affects space complexity considerations.)
3. Should we return the count of subarrays or actually enumerate them?
4. Are duplicate values in the array allowed, and how should they be handled?
5. What's the target time complexity for the follow-up? (e.g., O(n) or O(n log n) is preferred.)

Restated problem in my own words:

Given an integer array and a target integer K, I need to count how many contiguous subarrays contain exactly K distinct integers. A subarray is a contiguous portion of the array, and "distinct" means we count unique values regardless of how many times they appear.

Clarified inputs, outputs, and constraints:

• Input: An integer array nums of length n where 1 ≤ n ≤ 10^5, and each element can be any integer.
• Target: An integer k where 1 ≤ k ≤ n.
• Output: A count (integer) of subarrays that contain exactly k distinct integers.

Assumptions I'm making:

• The array elements can be negative or zero.
• We're counting subarrays, not returning their indices or contents.
• The input array can be mutated if that helps optimize space or time.

Data shape and hidden structure:

• The input is a 1D array of integers.
• This problem has a "sliding window" or "two pointers" structure because we're looking for contiguous subarrays with specific properties.
• It's a classic "at most K distinct" problem that can be solved by computing the difference between "at most K" and "at most K-1".

The problem is asking for a count of contiguous subarrays with exactly K distinct elements, which suggests we should use a sliding window technique to efficiently count valid subarrays without checking all possible subarrays.

2. Pattern Recognition

Most likely patterns:

• Sliding window technique - This is the primary pattern, as we're looking for subarrays with specific constraints (exactly K distinct integers)
• Two-pointer technique - The sliding window approach naturally uses two pointers to maintain a valid window
• Array subarray counting - The problem asks for counting subarrays, which often involves mathematical relationships between valid windows

Wording that signals the pattern:

• "subarrays with exactly K different integers" - This directly indicates we're looking for contiguous subarrays with a specific constraint
• "count of such subarrays" - The word "count" suggests we need to enumerate valid configurations rather than find one specific solution
• "different integers" - This signals we're dealing with unique element counting, which is a classic sliding window pattern

Why this fits the pattern:

This problem fits the sliding window pattern because:

1. We're looking for contiguous subarrays with specific constraints
2. The constraint (exactly K distinct integers) can be maintained using a sliding window approach
3. We can use the "at most K" technique to derive "exactly K" by computing (at most K) - (at most K-1)
4. The problem has a monotonic property where expanding the window can only increase the count of distinct elements

Core insight:

The key insight is that instead of directly counting subarrays with exactly K distinct integers, we can compute it as the difference between:

• Count of subarrays with at most K distinct integers
• Count of subarrays with at most K-1 distinct integers

This transformation simplifies the problem significantly and makes it amenable to sliding window technique where we can efficiently maintain the constraint while expanding and contracting our window.

3. Approach Evolution

My first instinct is to use a sliding window approach because this problem asks us to count subarrays with exactly K different integers, which naturally fits the sliding window pattern. However, a naive approach of checking every subarray would be O(n³) - O(n²) subarrays, each taking O(n) to count distinct elements.

Let me think about how to optimize this. I notice that if I maintain a window with at most K distinct integers, I can use the sliding window technique to efficiently count valid subarrays. But since we want exactly K distinct integers, I need to think differently.

The key insight is that subarrays with exactly K different integers = (subarrays with at most K distinct integers) - (subarrays with at most K-1 distinct integers). This is a classic "at most" to "exactly" transformation.

So I can solve this by:

1. Counting subarrays with at most K distinct integers
2. Counting subarrays with at most K-1 distinct integers
3. Subtracting the second from the first

This approach is O(n) time and O(1) space for each count, making the overall solution O(n) time and O(1) space.

The invariant I need to maintain is that my sliding window always contains at most K distinct integers, and I'm tracking the count of valid subarrays ending at each position.

Let me trace through this more carefully - if I expand the window by including a new element, and it increases the distinct count beyond K, I need to shrink the window from the left until the constraint is satisfied again. This maintains the sliding window property.

The key optimization here is recognizing that we can count subarrays with at most K distinct integers using a single pass, and the difference gives us exactly what we want.

This approach works because:

1. For any valid window with at most K distinct elements, all subarrays ending at the right pointer and starting anywhere within that window are valid
2. By maintaining a sliding window, we avoid redundant counting
3. The difference approach elegantly handles the "exactly K" constraint

This is much better than brute force because instead of checking every subarray individually, we use the sliding window technique to count valid subarrays in linear time.

4. Data Structure Choice

For this problem, I'll use a sliding window approach with HashMap as the primary data structure.

Primary Data Structures

1. HashMap<Integer, Integer> - Used to maintain the count of each element in the current window

   • Key: array element value
   • Value: count of that element in current window
   • Why needed: To efficiently track which elements are present and their frequencies within the sliding window
   • Time impact: O(1) average for insertions, deletions, and lookups
   • Space impact: O(k) where k is the number of distinct elements in current window

2. Two pointers (left and right) - Used to maintain the sliding window bounds

   • Why needed: To efficiently expand and contract the window while maintaining the constraint of exactly K distinct integers
   • Time impact: O(1) for pointer operations
   • Space impact: O(1) additional space

Why This Choice Is Optimal

The HashMap provides the perfect balance for this problem:

• It allows us to maintain a dynamic window with O(1) operations for element counting
• It naturally handles the "exactly K distinct integers" constraint by tracking element frequencies
• The sliding window technique with two pointers ensures we process each element at most twice, giving us linear time complexity

Helper Structures

I don't need any additional helper structures beyond the HashMap and two pointers, as the core logic can be implemented cleanly with these fundamental data structures.

The combination of HashMap for frequency tracking and two pointers for window management provides the optimal balance between code clarity, performance, and memory usage for this sliding window problem.

5. Algorithm Walkthrough

Let me trace through the solution with a concrete example to show how it works step-by-step.

Example: nums = [1,2,1,2,3], k = 2

Step 1: Initialize variables

• left = 0, right = 0
• map to track element frequencies: {}

Step 2: Expand window by moving right pointer

• right = 0: Add nums[0] = 1 → map = {1:1}
• right = 1: Add nums[1] = 2 → map = {1:1, 2:1}
• At this point, we have 2 distinct elements, which equals k

Step 3: Count valid subarrays ending at current right position

• When we have exactly k distinct elements, we can count how many valid subarrays end at position right
• We need to find the leftmost position where we still have exactly k distinct elements
• Start shrinking window from left while maintaining k distinct elements

Step 4: Process right = 1

• Current window: [1,2] (indices 0 to 1)
• We have exactly k=2 distinct elements
• Count valid subarrays:
  • Subarray [1,2] starting at index 0 → 1 subarray
  • We can shrink window from left while maintaining k elements

Step 5: Continue expanding and counting

• right = 2: Add nums[2] = 1 → map = {1:2, 2:1}
• Now we have 2 distinct elements (still k=2)
• Valid subarrays ending at index 2:
  • [1,2,1] (indices 0-2)
  • [2,1] (indices 1-2) → We need to count all subarrays that end at index 2 and have exactly k distinct elements

Step 6: The key insight - when we find a valid window with k distinct elements, we count all subarrays that end at current right pointer and start from valid left positions

Step 7: When we have more than k distinct elements, we shrink window from left until we're back to exactly k distinct elements

Step 8: Continue this process for remaining elements, maintaining the sliding window invariant that we always have at most k distinct elements in our current window

Key insight: For each valid window with exactly k distinct elements, we can count all subarrays that end at the current right pointer by tracking how far we can move the left pointer while maintaining exactly k distinct elements.

The algorithm terminates when we've processed all elements in the array, ensuring we count every subarray with exactly k distinct integers.

6. Java Solution

public class SubarraysWithKDistinct {
    
    public int subarraysWithKDistinct(int[] nums, int k) {
        // Return at most k distinct elements minus at most k-1 distinct elements
        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
    }
    
    private int atMostKDistinct(int[] nums, int k) {
        if (k <= 0) return 0;
        
        Map<Integer, Integer> freqMap = new HashMap<>();
        int left = 0;
        int result = 0;
        
        for (int right = 0; right < nums.length; right++) {
            // Add current element to window
            freqMap.put(nums[right], freqMap.getOrDefault(nums[right], 0) + 1);
            
            // Shrink window from left while we have more than k distinct elements
            while (freqMap.size() > k) {
                int leftElement = nums[left];
                freqMap.put(leftElement, freqMap.get(leftElement) - 1);
                
                if (freqMap.get(leftElement) == 0) {
                    freqMap.remove(leftElement);
                }
                
                left++;
            }
            
            // All subarrays ending at 'right' and starting from 'left' to 'right'
            // are valid (they contain at most k distinct elements)
            result += right - left + 1;
        }
        
        return result;
    }
}

This solution uses the sliding window technique with a frequency map to count subarrays with at most K distinct integers. The key insight is that the number of subarrays with exactly K distinct integers equals (at most K) - (at most K-1). This approach efficiently handles all edge cases and maintains optimal time complexity.

7. Complexity Analysis

Time Complexity: O(N)

The algorithm uses a sliding window technique with two pointers (left and right) that traverse the array once. Each element is visited at most twice (once by right and once by left), making the time complexity linear.

Space Complexity: O(K)

The space complexity is determined by the HashMap storing at most K+1 elements (since we're looking for exactly K distinct integers). In the worst case, when all elements are unique and K equals the array length, we store up to K elements in the map. The space used by the left and right pointers is constant.

Why these bounds are correct:

The linear time complexity stems from the fact that both pointers move forward through the array exactly once, and each operation on the HashMap (put, get, remove) is O(1) amortized. The space complexity is bounded by the maximum number of distinct elements we need to track, which cannot exceed K+1 in any valid subarray.

Optimality:

This solution is optimal for the problem as stated. Since we must examine each element at least once to determine distinct integers, O(N) time complexity is unavoidable. The space complexity of O(K) is also optimal since we need to store information about at most K distinct elements.

The solution achieves the best possible trade-off between time and space complexity for this constraint-based subarray counting problem.

8. Edge Cases & Pitfalls

Edge cases that require careful handling:

Empty input and single element arrays:

• Empty array [] with K=0 should return 0 (no valid subarrays)
• Single element array [1] with K=1 should return 1 (the single element subarray)
• Single element array [1] with K=0 should return 0 (no valid subarrays)

Duplicate values and repeated states:

• Arrays with many duplicates like [1,1,1,1] with K=2 require careful counting
• The sliding window approach must properly handle when the same element appears multiple times in a window

Boundary conditions:

• When K equals array length, we need to ensure we don't overcount subarrays
• When K exceeds array length, result should be 0 (impossible to have more distinct integers than array size)
• Subarrays that exactly match K distinct integers must be counted correctly

Common implementation mistakes:

1. Off-by-one errors in window management:

   • Incorrectly incrementing/decrementing pointers can cause subarrays to be counted multiple times or missed entirely
   • Failing to maintain proper bounds in the sliding window

2. Incorrect subarray counting logic:

   • Counting all subarrays within a valid window instead of only those that contain exactly K distinct integers
   • Not properly handling the case where a window contains more than K distinct elements

3. State management issues:

   • Not properly tracking the count of distinct integers in current window
   • Using incorrect data structures that don't support efficient updates

4. Array bounds violations:

   • Accessing array elements beyond their valid indices
   • Not checking for null or invalid array references

5. Integer overflow in counting:

   • When dealing with large arrays, intermediate counts could exceed integer limits (though this is less likely in typical constraints)

The solution must carefully maintain window boundaries and properly handle the transition between valid and invalid windows to avoid double-counting or missing subarrays.

9. Alternative Approaches

There are several alternative approaches to solving the "Subarrays with K Different Integers" problem, each with their own trade-offs:

Brute Force Approach: The most straightforward alternative is to check every possible subarray and count how many distinct integers it contains. For each subarray starting at index i and ending at index j, we would use a HashSet to count distinct elements. This approach has O(n³) time complexity because we have O(n²) subarrays and O(n) to count distinct elements in each. While simple to implement, it's inefficient for large inputs and doesn't leverage the sliding window pattern.

Two-Pass Sliding Window: Instead of directly computing subarrays with exactly K distinct integers, we can compute the number of subarrays with at most K distinct integers and subtract the number of subarrays with at most (K-1) distinct integers. This gives us exactly K distinct integers. The sliding window technique works by maintaining a window with at most K distinct elements and expanding/shrinking the window as needed. This approach is O(n) time and O(k) space, similar to our chosen solution but with a different conceptual framing.

HashMap-Based Counting: Rather than using a sliding window, we could maintain a HashMap that tracks the frequency of each element in the current window. When we encounter a new element, we increment its count; when we remove an element from the window, we decrement its count. This approach also uses sliding window technique but with a frequency map instead of a set, making it more flexible for counting problems.

Binary Search Approach: We could potentially use binary search on the answer, but this would require a helper function that counts subarrays with at most K distinct integers. This approach would be O(n log n) and more complex to implement correctly, making it less favorable than our chosen O(n) sliding window solution.

The key advantage of our chosen approach is its directness and optimal time complexity, while alternatives like the two-pass sliding window are more conceptually elegant but require careful handling of edge cases and potentially more complex boundary condition logic.

10. Test Cases

public class SubarraysWithKDistinctIntegers {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // Implementation here
    }
    
    // Test cases
    public static void main(String[] args) {
        SubarraysWithKDistinctIntegers solution = new SubarraysWithKDistinctIntegers();
        
        // Test case 1: Basic case
        int[] nums1 = {1, 2, 1, 2, 3};
        int k1 = 2;
        // Expected: 7
        // Subarrays with exactly 2 distinct integers:
        // [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
        
        // Test case 2: All elements same
        int[] nums2 = {1, 1, 1, 1};
        int k2 = 1;
        // Expected: 10
        // All subarrays have exactly 1 distinct integer
        
        // Test case 3: No valid subarrays
        int[] nums3 = {1, 2, 3};
        int k3 = 4;
        // Expected: 0
        // Cannot have 4 distinct integers in array of size 3
        
        // Test case 4: Single element
        int[] nums4 = {5};
        int k4 = 1;
        // Expected: 1
        
        // Test case 5: Empty array
        int[] nums5 = {};
        int k5 = 0;
        // Expected: 0
        
        // Test case 6: Complex case with duplicates
        int[] nums6 = {1, 2, 1, 3, 2};
        int k6 = 3;
        // Expected: 3
        // Valid subarrays: [1,2,1,3], [2,1,3,2], [1,2,1,3,2]
    }
}

Sample test cases include:

1. Basic case with mixed elements and k=2
2. Array with all identical elements
3. Impossible case where k exceeds array size
4. Single element arrays
5. Empty arrays
6. Complex case with multiple valid subarrays

The key test cases validate both the counting logic and edge case handling for various input configurations.

11. Final Summary

The core insight is to use the sliding window technique with a helper function that counts subarrays with at most K distinct integers, allowing us to compute exactly K distinct subarrays via the difference: countAtMost(K) - countAtMost(K-1). This approach efficiently handles the constraint of exactly K distinct integers by leveraging the monotonic property of the sliding window and avoiding redundant computations through careful boundary management. The solution is optimal with O(n) time complexity and O(k) space complexity, making it well-suited for large input sizes typical in FAANG systems.