Fruit Into Baskets
Problem
Given an integer array fruits where fruits[i] represents the type of fruit on the ith tree, return the maximum number of fruits you can collect in two baskets such that each basket can only hold one type of fruit and you must pick fruits from consecutive trees.
- 1 ≤ fruits.length ≤ 10⁵
- 0 ≤ fruits[i] < fruits.length
Example
fruits = [1,2,3,2,2]4We want the longest contiguous subarray that contains at most two distinct fruit types. We initialize the sliding window with `l = 0`, an empty frequency map `freq = {}`, and `res = 0`. When `r = 0`, we add fruit `1`, so `freq = {1: 1}`. The window is valid because it contains at most two types, so we update `res = 1`. When `r = 1`, we add fruit `2`, so `freq = {1: 1, 2: 1}`. The window is still valid, so we update `res = 2`. When `r = 2`, we add fruit `3`, so `freq = {1: 1, 2: 1, 3: 1}`. The window is now invalid because it contains three distinct types, so we must shrink from the left. We remove `fruits[l] = 1` by decrementing its count to zero and deleting it, which makes `freq = {2: 1, 3: 1}` and advances `l` to `1`. The window is valid again because it contains only types `2` and `3`. When `r = 3`, we add fruit `2`, so `freq = {2: 2, 3: 1}`. The window remains valid, its length is `r - l + 1 = 3`, and we update `res = 3`. When `r = 4`, we add fruit `2`, so `freq = {2: 3, 3: 1}`. The window remains valid, its length is `r - l + 1 = 4`, and we update `res = 4`. The key idea is that we only move `l` when a third type appears. We shrink until one fruit type fully exits the window (its count becomes zero and is removed from `freq`), and then we continue expanding to maximize the window length.
Approach
Straightforward Solution
A brute-force approach would check all subarrays and count distinct elements, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The problem reduces to finding the longest contiguous subarray with at most two distinct elements. This is a classic sliding window problem where the window expands to include new elements and contracts when the constraint is violated.
Path to Optimal
Recognizing the problem as a sliding window with a constraint on distinct elements allows a linear time solution. By maintaining a frequency map of fruit types in the current window, the algorithm expands the right pointer and contracts the left pointer whenever more than two distinct types are present. This ensures the window always satisfies the constraint and tracks the maximum length.
Optimal Approach
Use two pointers to represent a window. For each right index, add `fruits[r]` to `freq`. If the number of distinct keys becomes greater than two, advance `l` while decrementing counts and deleting any key whose count becomes zero. After shrinking, the window is valid again, so update the maximum length. After adding `fruits[r]`, the distinct count can increase by at most one, so it can reach 3 momentarily before shrinking restores it to 2.
Time
O(n)
Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.
Space
O(1)
The frequency map stores counts of fruit types in the current window. Since the problem restricts to at most two types, the map size is bounded by a small constant, resulting in constant auxiliary space.
Pattern Spotlight
Sliding Window (Variable Size with Frequency Map)
Maintain a window that satisfies the problem's constraints by expanding the right pointer and contracting the left pointer only when the constraint is violated, using a frequency map to track distinct elements efficiently.
Solution
| 1 | class Solution: |
| 2 | def totalFruit(self, fruits): |
| 3 | l = 0 |
| 4 | res = 0 |
| 5 | freq = {} |
| 6 | |
| 7 | for r in range(len(fruits)): |
| 8 | rf = fruits[r] |
| 9 | freq[rf] = freq.get(rf, 0) + 1 |
| 10 | |
| 11 | while len(freq) > 2: |
| 12 | lf = fruits[l] |
| 13 | freq[lf] -= 1 |
| 14 | if freq[lf] == 0: |
| 15 | del freq[lf] |
| 16 | l += 1 |
| 17 | |
| 18 | res = max(res, r - l + 1) |
| 19 | |
| 20 | return res |
Step-by-Step Solution
Initialize Sliding Window State
| 3 | l = 0 |
| 4 | res = 0 |
| 5 | freq = {} |
Objective
To initialize the variables that define the sliding window and store the current window state.
Key Insight
The algorithm maintains a window `[l..r]` and a frequency map `freq` that counts how many of each fruit type are currently inside the window. The variable `res` stores the best valid window length seen so far.
Interview Quick-Check
Core Logic
Set `l = 0`, `res = 0`, and `freq = {}` to define the initial window boundary and prepare the frequency map used to enforce the two-type constraint.
State & Boundaries
Initialize `l` at the start of the array so the window can expand correctly as `r` advances.
Common Pitfalls & Bugs
If `freq` is not reset correctly, the window state becomes inconsistent and the distinct-type check will be incorrect.
Expand Window and Track Fruit Frequencies
| 7 | for r in range(len(fruits)): |
| 8 | rf = fruits[r] |
| 9 | freq[rf] = freq.get(rf, 0) + 1 |
Objective
To iterate through the fruits array, expanding the window by moving the right pointer and updating the frequency map of fruit types.
Key Insight
Expanding the window by including the fruit at the right pointer and updating its count in the frequency map allows the algorithm to track how many of each fruit type are currently in the window. This is essential to detect when the window violates the two-type constraint and needs contraction.
Interview Quick-Check
Core Logic
Increment the count of the fruit at the right pointer in the frequency map to maintain an accurate count of fruit types in the current window.
State & Boundaries
The right pointer moves forward in each iteration, expanding the window to include new fruits.
Common Pitfalls & Bugs
Forgetting to update the frequency map when expanding the window can lead to incorrect detection of constraint violations.
Contract Window to Maintain Two-Type Constraint
| 11 | while len(freq) > 2: |
| 12 | lf = fruits[l] |
| 13 | freq[lf] -= 1 |
| 14 | if freq[lf] == 0: |
| 15 | del freq[lf] |
| 16 | l += 1 |
Objective
To shrink the window from the left when more than two distinct fruit types are present, restoring the constraint.
Key Insight
When the frequency map size exceeds two, the window contains too many fruit types. Contracting the window by moving the left pointer forward and decrementing counts removes fruit types until only two remain. This dynamic adjustment ensures the window always satisfies the problem's constraints.
Interview Quick-Check
Core Logic
While the frequency map contains more than two keys, decrement the count of the fruit at the left pointer and remove it from the map if its count reaches zero, then move the left pointer forward.
State & Boundaries
The loop continues contracting until the window contains at most two distinct fruit types.
Common Pitfalls & Bugs
Failing to remove fruit types with zero count from the frequency map can cause incorrect window size calculations.
Update Maximum Window Size
| 18 | res = max(res, r - l + 1) |
Objective
To track and update the maximum length of a valid window throughout the iteration.
Key Insight
After adjusting the window to satisfy the two-type constraint, the current window size (right - left + 1) represents a valid subarray length. Updating the maximum result ensures the algorithm returns the longest such subarray found.
Interview Quick-Check
Core Logic
Calculate the current window size and update the maximum result if the current window is larger.
State & Boundaries
This update occurs after the window is guaranteed to be valid (at most two distinct fruit types).
Common Pitfalls & Bugs
Updating the maximum before contracting the window can lead to invalid window sizes being considered.
Return the Maximum Number of Fruits Collected
| 20 | return res |
Objective
To return the maximum length of a valid window found, representing the maximum fruits collected.
Key Insight
After processing all fruits, the stored maximum window size corresponds to the longest contiguous subarray with at most two distinct fruit types, which solves the problem.
Interview Quick-Check
Core Logic
Return the maximum window size tracked during the iteration as the final answer.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
freq[rf] = freq.get(rf, 0) + 1Increment the count of the current fruit in the frequency map.
This line is critical because it updates the frequency map to reflect the current window's contents, enabling the algorithm to detect when the window violates the two-type constraint.
freq[lf] -= 1Decrement the count of the fruit at the left pointer in the frequency map.
This decrement is essential to accurately track the window's fruit composition during contraction, ensuring the frequency map correctly represents the current window.
if freq[lf] == 0:Check whether the left fruit’s frequency has reached zero so the type can be removed from the map.
This check detects when the left fruit type has fully left the window, which is the condition needed to remove its key and keep `len(freq)` accurate.
del freq[lf]Remove the fruit from the frequency map if its count reaches zero.
Removing fruit types with zero count is critical to maintain the correct size of the frequency map, which directly controls the window's validity.
res = max(res, r - l + 1)Update the maximum window size with the current valid window length.
Updating the maximum after ensuring the window is valid guarantees the result reflects the longest subarray with at most two distinct fruit types.
freq = {}Initialize a frequency map to count fruit types in the current window.
The frequency map tracks how many of each fruit type are present, enabling constraint checks and window adjustments.
while len(freq) > 2:Check if the window contains more than two distinct fruit types.
This condition detects when the window violates the problem's constraint, triggering contraction to restore validity.
return resReturn the maximum number of fruits collected.
Returning the tracked maximum window size provides the final solution to the problem.
lf = fruits[l]Retrieve the fruit type at the left pointer for contraction.
Identifying the fruit to remove from the window is necessary to update the frequency map correctly during contraction.
l += 1Move the left pointer forward to contract the window.
Advancing the left pointer shrinks the window, removing fruits until the constraint is satisfied again.
res = 0Initialize the variable to store the maximum number of fruits collected.
This variable accumulates the length of the longest valid window found, which is the problem's output.
for r in range(len(fruits)):Iterate over the fruits array with the right pointer.
The right pointer expands the window by moving forward through the array, exploring all possible subarrays.
l = 0Initialize the left pointer of the sliding window to 0.
Starting the left pointer at 0 sets the initial window boundary, enabling the window to expand from the beginning of the array.
rf = fruits[r]Retrieve the fruit type at the right pointer.
Accessing the current fruit is necessary to update its count in the frequency map and maintain window state.
Test Your Understanding
Why does the algorithm contract the window from the left only when the number of distinct fruit types exceeds two?
Because the problem requires at most two distinct fruit types in the baskets, contracting the window restores this constraint by removing fruit types until only two remain, ensuring the window is valid and the maximum length can be tracked.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Fruit Into Baskets from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Start drilling Fruit Into Baskets for free