Find length of the longest subarray containing at most two distinct integers

Summary

Given an array, find the length of the longest contiguous subarray that contains at most two distinct elements. This problem is a variation of the classic "Fruit into Baskets" problem, which involves finding the maximum number of fruits that can be put in each basket without exceeding its capacity.

The key concepts involved are arrays, data structures, and algorithms. The problem requires us to find a contiguous subarray with at most two distinct elements, which is a classic problem in algorithm design.

Detailed Explanation

To solve this problem, we can use the two-pointer algorithm. We maintain two pointers, left and right, both initialized to 0. The left pointer points to the start of the current subarray, and the right pointer points to the end of the current subarray.

We initialize a dictionary distinct_counts to keep track of the number of distinct elements in the current subarray. We also maintain two variables: max_length to store the maximum length of the subarray found so far, and current_count to store the number of distinct elements in the current subarray.

Here's the step-by-step breakdown:

1. Initialize left, right, distinct_counts, max_length, and current_count.
2. Iterate through the array with the right pointer.
3. For each element, update distinct_counts by incrementing the count of that element if it's already present in the dictionary, or adding it to the dictionary with a count of 1.
4. If the number of distinct elements exceeds 2, move the left pointer to the right until the number of distinct elements is at most 2.
5. Update max_length with the maximum length found so far.
6. Repeat steps 2-5 until the end of the array.

Here's an ASCII art diagram illustrating the algorithm:

          +---------------+
          |         left    |
          +---------------+
                  |
                  v
+---------------+       +---------------+
|  Array        |       |  Subarray     |
|  [1, 2, 3, 4]  |       |  [1, 2, 3]   |
|  ...           |       |  ...          |
+---------------+       +---------------+
                  |
                  v
          +---------------+
          |         right    |
          +---------------+

Time complexity: O(n), where n is the length of the array. Space complexity: O(1), as we only use a constant amount of space to store the dictionary and variables.

Optimized Solutions

Java