Find the Longest Subarray with at Most Two Distinct Values
Company: Moodys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Find the Longest Subarray with at Most Two Distinct Values
Given an array of integers, return the length of the longest contiguous subarray containing at most two distinct values.
Design a linear-time sliding-window solution. At every step, the current window must remain valid or be shrunk until it contains no more than two distinct values.
### Constraints & Assumptions
- The array length is between 0 and 200,000.
- Values fit in a signed 32-bit integer and may be negative.
- The answer for an empty array is 0.
- Only contiguous subarrays count.
### Clarifying Questions to Ask
- Does “at most two” allow a window containing only one distinct value?
- Is the required output only the length, or also the window boundaries?
- Are negative values or repeated runs handled differently? They should not be.
```hint Maintain counts, not just a set
When the right edge introduces a third value, counts tell you when advancing the left edge has completely removed one value from the window.
```
### Required Behavior
- Return 0 for an empty array.
- Count repeated occurrences without increasing the distinct-value count.
- Shrink the left boundary until the active window is valid whenever a third distinct value enters.
- Consider valid windows that begin at index 0 or end at the final element.
### Examples
```text
Input: [1, 2, 1]
Output: 3
Explanation: The entire array contains two distinct values.
```
```text
Input: [0, 1, 2, 2]
Output: 3
Explanation: [1, 2, 2] is the longest valid subarray.
```
```text
Input: [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
Output: 5
Explanation: [1, 2, 1, 1, 2] has at most two distinct values.
```
Quick Answer: Find the length of the longest contiguous subarray containing no more than two distinct integer values. A correct solution maintains sliding-window invariants across repeated runs, negative values, empty input, and every boundary movement while meeting the linear-time goal.
Given an array of integers `nums`, return the **length of the longest contiguous
subarray that contains at most two distinct values**.
A subarray is a contiguous run of elements — you may not skip positions. A window
holding only one distinct value still satisfies "at most two". Repeated occurrences
of the same value never raise the distinct-value count, and negative values are
treated exactly like any other value. Aim for a single linear pass: a sliding window
that shrinks from the left whenever a third distinct value enters at the right.
### Output semantics
Return one integer — the maximum length over all valid subarrays, never the window
boundaries and never the subarray itself. The returned length is unique for any
input (several different windows may tie at that length; only the length is
reported), so there is exactly one correct output per test. For an empty array the
answer is `0`.
### Input / output
- Input: one argument, `nums`, a list of integers.
- Output: one integer in the range `[0, len(nums)]`.
### Examples
**Example 1**
```text
Input: nums = [1, 2, 1]
Output: 3
```
The whole array holds two distinct values (`1` and `2`), so the longest valid
subarray is the array itself.
**Example 2**
```text
Input: nums = [0, 1, 2, 2]
Output: 3
```
`[1, 2, 2]` (indices 1..3) is the longest valid window. Extending it left to index 0
would add a third distinct value (`0`), so the window has to stop there.
**Example 3**
```text
Input: nums = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
Output: 5
```
`[1, 2, 1, 1, 2]` (indices 3..7) wins. The leading run of three `3`s cannot join it
because that window would hold `3`, `1` and `2` at once. Note that `[3, 3, 3, 1]` is
valid but only length 4.
### Constraints
- `0 <= len(nums) <= 200000`
- `-2147483648 <= nums[i] <= 2147483647` (every value fits in a signed 32-bit
integer and may be negative)
- The answer for an empty array is `0`.
- Only contiguous subarrays count.
- The answer never exceeds `len(nums)`, so every value, count and intermediate
result fits in a signed 32-bit integer — `int` is sufficient in Java and C++.
Constraints
- 0 <= len(nums) <= 200000 (the array length is between 0 and 200,000)
- -2147483648 <= nums[i] <= 2147483647 (values fit in a signed 32-bit integer and may be negative)
- The answer for an empty array is 0.
- Only contiguous subarrays count; the return value is a length, not a pair of indices.
- The answer is at most len(nums) = 200000, so every value, count and intermediate result fits in a signed 32-bit integer — int in Java and C++ is sufficient, and no value approaches 2^53.
Examples
Input: ([],)
Expected Output: 0
Explanation: Empty array: the prompt pins the answer to 0.
Input: ([5],)
Expected Output: 1
Explanation: One element is always a valid window of one distinct value.
Hints
- A window is valid while it holds at most two distinct values. Ask yourself what must change about the window the moment a third value arrives at its right edge.
- Knowing only WHICH values are in the window is not enough — you also need to know when advancing the left edge has removed the last occurrence of one of them. Store how many times each value currently appears.
- Both edges only ever move forward, so each element enters the window once and leaves it at most once. That is what keeps the whole scan linear even though there is a loop inside a loop.