Problem Breakdown
We are given an array tree where each element represents a fruit type produced by a tree in a row. We need to collect fruits into two baskets. Each basket can hold unlimited quantity but only one specific fruit type per basket (maximum 2 distinct types total). Once we start at any tree, we move strictly rightwards and must stop if the current window contains more than 2 unique fruit types or reaches the end of the row.
Goal: Find the maximum number of fruits collected in a valid contiguous subarray containing at most two unique values.
- Inputs: A list
treeof integers representing fruit types. - Outputs: An integer representing the maximum count of fruits.
- Constraints: Array length up to 40,000; Fruit types are non-negative integers within range
[0, tree.length).
Edge Cases / Tricky Scenarios:
- Single Element: If
tree = [5], the answer is 1 (one basket holds type 5). - All Same Elements: e.g.,
[3, 3, 3]-> Answer is length of array since only one unique type exists. - Third Type Appears Immediately: If we have a valid window but the next element introduces a third distinct value, the left pointer must advance to drop elements until the count drops back to <= 2 types.
Intuition
Brute Force Approach:
We could iterate through every possible starting index i, and for each start, expand rightwards counting unique fruits until we hit a limit or end of array. We track the maximum length found.
- Complexity: because in the worst case (e.g.,
[1, 2, 3...]), checking every subarray takes linear time relative to N for each start position. WithN = 40,000, this is roughly operations, which will Time Out on most platforms (usually limit ~10^8 ops/sec).
Key Insight:
This problem maps directly to the “Longest Substring with At Most K Distinct Characters” pattern where K = 2. Since we only care about contiguous segments and expanding/shrinking a window based on unique counts, this suggests a Sliding Window (Two Pointers) approach. We maintain a valid window [left, right] that satisfies the constraint of having at most two distinct fruit types.
Optimal Approach:
- Expand
rightpointer to include new fruits. - Track frequency of each fruit type in current window using a hash map (dictionary).
- If adding
tree[right]causes more than 2 unique keys, shrink the window fromleft. Remove elements until valid again. - Update global maximum with current window size at every step.
Approach
- Initialize two pointers:
left = 0, and iteraterightfrom0to end of array. - Use a dictionary
basket(orfruit_count) to store the frequency of each fruit type in the current valid window[left, right]. - In every iteration (for each new tree at
right):- Add
tree[right]to our map and increment its count.
- Add
- Check if the number of unique keys (
len(basket)) exceeds 2:- If yes, we must shrink from the left until valid again.
- Decrement count for
tree[left]. - Remove key from map if count becomes zero (to maintain accurate distinct count).
- Increment
leftpointer.
- After ensuring validity, calculate current window size (
right - left + 1) and update max result.
Complexity Analysis
- Time Complexity: . We traverse the array once with the
rightpointer. Theleftpointer also moves at most from start to end. Each element is added and removed from the map at most once. Dictionary operations are amortized , so total time is linear relative to input size. - Space Complexity: where K is the number of unique elements allowed in window (constant 2). In Python dictionaries store overhead proportional to distinct keys encountered during processing before shrinking. Since we prune when count exceeds 3 momentarily and keep <= 2 validly, effectively constant space relative to N ( auxiliary), though strictly speaking the map size is bounded by input values but practically capped at small constants due to window constraint.
Solution
from collections import defaultdict
def totalFruit(tree):
# Dictionary to store count of each fruit type in current window
basket = defaultdict(int)
left = 0
max_fruits = 0
for right, fruit_type in enumerate(tree):
# Add the new tree's fruit to our baskets
basket[fruit_type] += 1
# If we have more than 2 types of fruits, shrink window from left
while len(basket) > 2:
basket[tree[left]] -= 1
if basket[tree[left]] == 0:
del basket[tree[left]]
left += 1
# Update maximum fruits collected (current valid window size)
max_fruits = max(max_fruits, right - left + 1)
return max_fruits
# Example usage matching problem description
print(totalFruit([3,3,3,1,2,1,1,2,3,3,4])) # Output: 5