Solution
Approach 1: Scan Through Blocks
Intuition
Equivalently, we want the longest subarray with at most two "types" (values of tree[i]
).
Instead of considering each element individually, we can consider blocks of adjacent elements of the same type.
For example, instead of tree = [1, 1, 1, 1, 2, 2, 3, 3, 3]
, we can say this is blocks = [(1, weight = 4), (2, weight = 2), (3, weight = 3)]
.
Now say we brute forced, scanning from left to right. We'll have something like blocks = [1, _2_, 1, 2, 1, 2, _1_, 3, ...]
(with various weights).
The key insight is that when we encounter a 3
, we do not need to start from the second element 2
(marked _2_
for convenience); we can start from the first element (_1_
) before the 3
. This is because if we started two or more elements before, the sequence must have types 1
and 2
, and that sequence is going to end at the 3
, and thus be shorter than anything we've already considered.
Since every starting point (that is the leftmost index of a block) was considered, this solution is correct.
Algorithm
As the notation and strategy around implementing this differs between Python and Java, please see the inline comments for more details.
Complexity Analysis

Time Complexity: , where is the length of
tree
. 
Space Complexity: .
Approach 2: Sliding Window
Intuition
As in Approach 1, we want the longest subarray with at most two different "types" (values of tree[i]
). Call these subarrays valid.
Say we consider all valid subarrays that end at index j
. There must be one with the smallest possible starting index i
: lets say opt(j) = i
.
Now the key idea is that opt(j)
is a monotone increasing function. This is because any subarray of a valid subarray is valid.
Algorithm
Let's perform a sliding window, keeping the loop invariant that i
will be the smallest index for which [i, j]
is a valid subarray.
We'll maintain count
, the count of all the elements in the subarray. This allows us to quickly query whether there are 3 types in the subarray or not.
Complexity Analysis

Time Complexity: , where is the length of
tree
. 
Space Complexity: .
Analysis written by: @awice.