Longest Subarray with At Most Two Distinct Integers

Given an array of integers, the task is to find the length of the longest contiguous subarray that contains at most two distinct integers. In other words, you need to determine the maximum length of a subarray (a contiguous segment) in which there are no more than two different numbers.

If the array is empty, the answer should be 0. Otherwise, employing a sliding window approach can achieve an efficient solution.

For a formal mathematical expression, let \(A = [a_1, a_2, \dots, a_n]\) be the array and let a subarray \(A[i\dots j]\) be valid if it contains at most two distinct integers. We need to find the maximum \(L = j - i + 1\) over all valid subarrays.

Example:

• For the input [1, 2, 1], the whole array is valid (contains only 1 and 2) so the answer is 3.
• For the input [1, 2, 2, 3, 3, 4, 4, 4], one of the longest valid subarrays is [2, 2, 3, 3, 4] having a length of 5.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout), which is the length of the longest contiguous subarray that contains at most two distinct integers.

3
1 2 1

3