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

Given an array of integers, find the longest subarray that contains at most K distinct integers and return its length.

Example

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

Note:

Your algorithm should run in O(n^2) time and use O(n) extra space.

Problem Definition

The problem requires finding the longest subarray within a given array of integers that contains at most K distinct integers. The output should be the length of this subarray.

Input:

nums: An array of integers.
k: An integer representing the maximum number of distinct integers allowed in the subarray.

Output:

An integer representing the length of the longest subarray with at most K distinct integers.

Constraints:

The algorithm should run in O(n^2) time complexity.
The algorithm should use O(n) extra space.

Example:

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 is to find the longest contiguous subarray with at most K distinct integers. This problem is significant in scenarios where we need to analyze data streams or logs to find patterns within a limited set of unique elements.

Potential pitfalls include misunderstanding the requirement for contiguous subarrays and not efficiently managing the count of distinct integers.

Approach

To solve this problem, we can use a sliding window approach combined with a hash map to keep track of the count of distinct integers within the current window.

Naive Solution

A naive solution would involve checking all possible subarrays and counting the distinct integers in each, which would result in a time complexity of O(n^3). This is not optimal.

Optimized Solution

An optimized solution involves using a sliding window approach:

Initialize two pointers, left and right, both starting at the beginning of the array.
Use a hash map to keep track of the count of each integer within the window.
Expand the window by moving the right pointer and update the hash map.
If the number of distinct integers exceeds K, shrink the window by moving the left pointer until the number of distinct integers is at most K.
Keep track of the maximum length of the window that satisfies the condition.

Algorithm

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

Initialize left and right pointers to 0.
Initialize a hash map to keep track of the count of integers within the window.
Initialize a variable to keep track of the maximum length of the subarray.
Iterate with the right pointer over the array.
For each element, update the hash map with the count of the current integer.
If the number of distinct integers exceeds K, move the left pointer to the right until the number of distinct integers is at most K, updating the hash map accordingly.
Update the maximum length of the subarray if the current window length is greater.
Return the maximum length.

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, maxLength = 0;

    for (int right = 0; right < nums.size(); ++right) {
        countMap[nums[right]]++; // Add current element to the hash map

        // If the number of distinct integers exceeds k, shrink the window
        while (countMap.size() > k) {
            countMap[nums[left]]--;
            if (countMap[nums[left]] == 0) {
                countMap.erase(nums[left]);
            }
            left++;
        }

        // Update the maximum length of the subarray
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    vector<int> nums = {1, 2, 1, 2, 3};
    int k = 2;
    cout << "The length of the longest subarray with at most " << k << " distinct integers is " << 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 by the right pointer and once by the left pointer). The space complexity is O(n) due to the hash map used to store the count of elements.

Edge Cases

Potential edge cases include:

Empty array: The output should be 0.
k = 0: The output should be 0 since no subarray can have 0 distinct integers.
All elements are the same: The output should be the length of the array.

Testing

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

Simple cases with small arrays.
Arrays with all identical elements.
Arrays with more than k distinct elements.
Edge cases such as empty arrays and k = 0.

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 counts and frequencies.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find 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: