156. Two-Basket Harvest
A farmer walks along a row of fruit trees, where trees[i] is the kind of fruit that grows on tree i. She carries only two baskets, and each basket can hold a single kind of fruit, without any limit on how many pieces.
She picks a starting tree, then moves right one tree at a time and picks exactly one fruit from every tree she passes. She must stop as soon as she reaches a tree whose fruit does not fit in either basket. Return the largest number of trees she can pick from, over all possible starting trees.
Example 1
- Input:
- trees = [4,4,9,9,4,6,6,6,6]
- Output:
- 5
- Explanation:
The longest stretches with at most two kinds are [4,4,9,9,4] and [4,6,6,6,6], both of length 5.
Example 2
- Input:
- trees = [1,2,3,4]
- Output:
- 2
- Explanation:
Any three trees in a row contain three kinds, so she can only pick two trees in a row. The answer is 2.
Constraints
1 ≤ trees.length ≤ 105
0 ≤ trees[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)