547. Fruit Into Baskets
You are walking down a row of fruit trees. fruits[i] is the type of fruit the tree at position i grows. You carry exactly two baskets, and each basket can hold an unlimited amount of fruit — but only of a single type.
You may start at any tree. From there you move right, picking one fruit from every tree you pass, and you must stop the first time you reach a tree whose type fits in neither basket. Trees may not be skipped.
Given the integer array fruits, return the maximum number of fruits you can collect — equivalently, the length of the longest contiguous stretch of fruits that contains at most two distinct values.
Example 1:
Input: fruits = [1, 2, 1]
Output: 3
Explanation: Only two types appear, so every tree can be picked: one basket holds type 1, the other type 2.
Example 2:
Input: fruits = [0, 1, 2, 2]
Output: 3
Explanation: Starting at the second tree picks types [1, 2, 2] — three fruits. Starting at the first tree would force a stop after [0, 1], since 2 fits in neither basket.
Example 3:
Input: fruits = [1, 2, 3, 2, 2]
Output: 4
Explanation: The stretch [2, 3, 2, 2] uses only types 2 and 3 and collects four fruits.
Constraints:
- 1 ≤ fruits.length ≤ 10⁵
- 0 ≤ fruits[i] ≤ 10⁹
Hints:
Rephrase away the story: you want the longest contiguous subarray containing at most 2 distinct values.
Grow a window rightward, keeping a count per type inside it. When a third type appears, shrink from the left until one type's count hits zero.
The left edge never moves backwards, so both edges advance at most n times — the whole scan is O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: fruits = [1, 2, 1]
Expected output: 3