Longest Subarray with at most K Distinct Integers in O(n) Time Complexity using JavaScript

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

An array of integers, nums.
An integer, k, 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) 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 sequences with constraints on diversity, such as network packet analysis or substring problems in text processing.

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

Approach

To solve this problem, we can use the sliding window technique 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 O(n^2) time complexity. This is not optimal for large arrays.

Optimized Solution

The optimized solution uses 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 algorithm:

Initialize left and right pointers to 0.
Initialize an empty hash map to store the count of integers.
Initialize a variable to keep track of the maximum length of the subarray.
Iterate through the array using the right pointer.
For each element, update the hash map with the count of the integer.
If the number of distinct integers in the hash map exceeds k, move the left pointer to the right until the number of distinct integers is at most k.
Update the maximum length of the subarray.
Return the maximum length.

Code Implementation

/**
 * Function to find the length of the longest subarray with at most K distinct integers.
 * @param {number[]} nums - The input array of integers.
 * @param {number} k - The maximum number of distinct integers allowed in the subarray.
 * @return {number} - The length of the longest subarray.
 */
function longestSubarrayWithKDistinct(nums, k) {
    // Initialize pointers and variables
    let left = 0;
    let right = 0;
    let maxLength = 0;
    let countMap = new Map();

    // Iterate through the array with the right pointer
    while (right < nums.length) {
        // Add the current element to the count map
        let rightNum = nums[right];
        countMap.set(rightNum, (countMap.get(rightNum) || 0) + 1);

        // If the number of distinct integers exceeds k, move the left pointer
        while (countMap.size > k) {
            let leftNum = nums[left];
            countMap.set(leftNum, countMap.get(leftNum) - 1);
            if (countMap.get(leftNum) === 0) {
                countMap.delete(leftNum);
            }
            left++;
        }

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

    return maxLength;
}

// Example usage
const nums = [1, 2, 1, 2, 3];
const k = 2;
console.log(longestSubarrayWithKDistinct(nums, k)); // Output: 4

Complexity Analysis

The time complexity of this solution 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(k) due to the hash map storing at most k distinct integers.

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 is at least 1.
k greater than the number of distinct integers in the array: The output should be the length of the array.

Testing

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

console.log(longestSubarrayWithKDistinct([], 2)); // Output: 0
console.log(longestSubarrayWithKDistinct([1, 1, 1, 1], 1)); // Output: 4
console.log(longestSubarrayWithKDistinct([1, 2, 3, 4, 5], 3)); // Output: 3
console.log(longestSubarrayWithKDistinct([1, 2, 1, 3, 4], 2)); // Output: 3

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 track elements.
Practice similar problems to improve problem-solving skills and familiarity with common algorithms.

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 improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: