Longest Subarray With At Most K Distinct Integers in 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:

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 that contains at most K distinct integers. This problem is significant in scenarios where we need to analyze data streams or sequences with constraints on diversity.

Common applications include network packet analysis, substring problems in text processing, and more.

Potential pitfalls include misunderstanding the requirement for contiguous subarrays and not handling edge cases like empty arrays or K being zero.

Approach

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

1. **Naive Solution**: Iterate through all possible subarrays and check if they contain at most K distinct integers. This approach is not optimal as it has a time complexity of O(n^3).

2. **Optimized Solution**: Use a sliding window technique with a hash map to keep track of the count of distinct integers within the window. This approach ensures we only traverse the array once, achieving O(n) time complexity.

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 update the hash map.

4. If the number of distinct integers exceeds K, contract the window by moving the `left` pointer until the number of distinct integers is at most K.

5. Keep track of the maximum length of the window during this process.

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) {
    // Edge case: if k is 0, return 0 as no subarray can have 0 distinct integers
    if (k === 0) return 0;

    let left = 0;
    let right = 0;
    let maxLength = 0;
    const countMap = new Map();

    while (right < nums.length) {
        // Add the current number to the count map
        countMap.set(nums[right], (countMap.get(nums[right]) || 0) + 1);

        // If the number of distinct integers exceeds k, shrink the window from the left
        while (countMap.size > k) {
            countMap.set(nums[left], countMap.get(nums[left]) - 1);
            if (countMap.get(nums[left]) === 0) {
                countMap.delete(nums[left]);
            }
            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 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(k) due to the hash map storing at most K distinct integers.

Edge Cases

1. **Empty Array**: If the input array is empty, the output should be 0.

2. **K is Zero**: If K is zero, no subarray can have 0 distinct integers, so the output should be 0.

3. **All Elements Same**: If all elements in the array are the same, the output should be the length of the array if K is at least 1.

4. **K Greater than Array Length**: If K is greater than the length of the array, the output should be the length of the array.

Testing

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

Empty array: longestSubarrayWithKDistinct([], 2) should return 0.
K is zero: longestSubarrayWithKDistinct([1, 2, 3], 0) should return 0.
All elements same: longestSubarrayWithKDistinct([1, 1, 1, 1], 2) should return 4.
K greater than array length: longestSubarrayWithKDistinct([1, 2, 3], 5) should return 3.

Use testing frameworks like Jest or Mocha for automated testing.

Thinking and Problem-Solving Tips

1. **Understand the Problem**: Break down the problem into smaller parts and understand the requirements.

2. **Use Sliding Window Technique**: This technique is useful for problems involving subarrays or substrings with constraints.

3. **Practice**: Solve similar problems to get a better grasp of the sliding window technique and hash maps.

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 improving problem-solving skills and preparing for coding interviews.

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