Longest Subarray with at most K Distinct Integers II in C++ (O(n^2) Time Complexity)

Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 4
Explanation:the subarray nums[0...3] contains 2 distinct values: [1, 2] and is the longest subarray

Understanding the Problem

The core challenge of this problem is to find the longest contiguous subarray that contains at most K distinct integers. This problem is significant in scenarios where we need to analyze data streams or sequences to find patterns or segments that meet specific criteria. A common pitfall is to misinterpret the requirement of "at most K distinct integers" and mistakenly consider subarrays with exactly K distinct integers.

Approach

To solve this problem, we can use a sliding window approach. The idea is to maintain a window that satisfies the condition of having at most K distinct integers and expand or contract this window as we iterate through the array.

Naive Solution

A naive solution would involve checking all possible subarrays and counting the distinct integers in each. This approach is not optimal as it has a time complexity of O(n^3) due to the nested loops and the distinct count operation.

Optimized Solution

An optimized approach uses a sliding window technique with a hash map to keep track of the count of each integer within the window. This allows us to efficiently expand and contract the window while maintaining the count of distinct integers.

Algorithm

Here is a step-by-step breakdown of the sliding window algorithm:

1. Initialize two pointers, `left` and `right`, both set to the start of the array.
2. Use a hash map to keep track of the count of each integer within the window.
3. Expand the window by moving the `right` pointer and updating the hash map.
4. If the number of distinct integers exceeds K, contract the window by moving the `left` pointer until the condition is satisfied.
5. Keep track of the maximum length of the window that satisfies the condition.

Code Implementation

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestSubarrayWithKDistinct(vector<int>& nums, int k) {
    unordered_map<int, int> countMap; // Hash map to store the count of elements
    int left = 0, right = 0;
    int maxLength = 0;
    
    while (right < nums.size()) {
        // Expand the window by including nums[right]
        countMap[nums[right]]++;
        
        // If the window has more than k distinct integers, contract it from the left
        while (countMap.size() > k) {
            countMap[nums[left]]--;
            if (countMap[nums[left]] == 0) {
                countMap.erase(nums[left]);
            }
            left++;
        }
        
        // Update the maximum length of the window
        maxLength = max(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

int main() {
    vector<int> nums = {1, 2, 1, 2, 3};
    int k = 2;
    cout << "Longest subarray length: " << longestSubarrayWithKDistinct(nums, k) << endl;
    return 0;
}

Complexity Analysis

The time complexity of the sliding window approach is O(n) because each element is processed at most twice (once when expanding the window and once when contracting it). The space complexity is O(n) due to the hash map used to store the count of elements.

Edge Cases

Consider the following edge cases:

• Empty array: The output should be 0.
• Array with all identical elements: The output should be the length of the array if k > 0.
• k = 0: The output should be 0 as no subarray can have 0 distinct integers.

Testing

To test the solution comprehensively, consider the following test cases:

vector<int> nums1 = {};
int k1 = 2;
assert(longestSubarrayWithKDistinct(nums1, k1) == 0);

vector<int> nums2 = {1, 1, 1, 1};
int k2 = 1;
assert(longestSubarrayWithKDistinct(nums2, k2) == 4);

vector<int> nums3 = {1, 2, 3, 4, 5};
int k3 = 2;
assert(longestSubarrayWithKDistinct(nums3, k3) == 2);

vector<int> nums4 = {1, 2, 1, 3, 4};
int k4 = 3;
assert(longestSubarrayWithKDistinct(nums4, k4) == 4);

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Think about different approaches and their time and space complexities.
• Use data structures like hash maps to efficiently manage and query data.
• Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the longest subarray with at most K distinct integers using a sliding window approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in competitive programming and technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Longest Substring with At Most K Distinct Characters
• GeeksforGeeks: Longest Subarray with At Most K Distinct Elements
• Coding Ninjas: Longest Subarray with At Most K Distinct Elements