Find the length of the longest contiguous subarray containing at most two distinct fruit types.
LeetCode 904: Fruit Into Baskets
gfgProblem
You are given an integer array fruits where fruits[i] represents the type of fruit on the i-th tree in a line.
You want to collect fruits using exactly two baskets. Each basket can hold only one type of fruit, but there is no limit on how many fruits of that type it can hold.
Starting from any tree, you may move to the right and collect one fruit from each tree you pass. You must stop as soon as the collected fruits contain more than two distinct types, since you can no longer place them into the two baskets.
Return the maximum number of fruits you can collect.
Notes
- The collected fruits must come from a contiguous subarray.
- You may choose any starting point.
- Each basket can store only a single fruit type.
Input Format
fruits: an integer array of lengthn- Each value identifies a fruit type on a tree
Goal
Return the length of the longest contiguous subarray containing at most two distinct values.
Output Format
- Return a single integer: the maximum length of a valid contiguous subarray.
Constraints
1 <= fruits.length- Fruit types are integers
- The solution should be efficient for large arrays, typically near linear time.
Example 1
Input
fruits = [1,2,1]
Output
3
Explanation
The whole array contains only two fruit types, so the maximum collectible length is 3.
Example 2
Input
fruits = [0,1,2,2]
Output
3
Explanation
A best choice is [1,2,2], which contains exactly two fruit types and has length 3.
Show 1 more example
Example 3
Input
fruits = [1,2,3,2,2]
Output
4
Explanation
A best choice is [2,3,2,2], which contains only two fruit types and has length 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.