Fruit Into Baskets | Leetcode 904 | Optimal Solution using Sliding Window

The problem “Fruit Into Baskets” asks for the length of the longest contiguous subarray that contains at most two distinct fruit types. Think of it as carrying fruits in two baskets, each basket can hold only a single type, and you want to collect the maximum number of fruits from a continuous row of trees.

Here’s the [Problem Link] to begin with.

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Constraints:

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

Brute Force (Check All Subarrays)

Intuition and Approach

• For each start index i, expand j to the right and keep track of distinct fruit types in a set.
• If the set size exceeds 2, stop expanding and move to the next start.
• Track the maximum window length while valid.

Code

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        n = len(fruits)
        max_length = 0
        for i in range(n):
            my_set = set()
            for j in range(i, n):
                my_set.add(fruits[j])
                if len(my_set) > 2:
                    break
                max_length = max(max_length, j - i + 1)
        return max_length

Time and Space Complexity

• Time: O(n^2)
• Space: O(1) to O(2) for the set (bounded by 2 distinct types)

When to Use

• Good for understanding, but not efficient for large inputs.

Better (Sliding Window with Shrink Loop)

Intuition and Approach

• Use two pointers (left, right) and a frequency dictionary to count fruit types in the window.
• Expand right and include fruits[right].
• While there are more than 2 types, shrink from left, decrementing counts and removing types with zero count.
• After restoring the constraint (≤2 types), update the maximum window length.

Code

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        my_set = {}
        left = 0
        right = 0
        n = len(fruits)
        max_length = 0
        while right < n:
            my_set[fruits[right]] = my_set.get(fruits[right], 0) + 1
            while len(my_set) > 2:
                my_set[fruits[left]] -= 1
                if my_set[fruits[left]] == 0:
                    del my_set[fruits[left]]
                left += 1
            max_length = max(max_length, right - left + 1)
            right = right + 1
        return max_length

Time and Space Complexity

• Time: O(n)
• Space: O(2) → effectively O(1), since at most two distinct types are kept

Why It Works

• The window always maintains at most two types by shrinking when necessary, ensuring linear traversal.

Optimal (Tight Sliding Window)

Intuition and Approach

• Same core idea as “Better,” with slightly tighter checks:
  • Add fruits[right] and, if distinct types exceed 2, shrink once from left.
  • After ensuring ≤2 types, update max_length.

Code

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        my_set = {}
        left = 0
        right = 0
        n = len(fruits)
        max_length = 0
        while right < n:
            my_set[fruits[right]] = my_set.get(fruits[right], 0) + 1
            if len(my_set) > 2:
                my_set[fruits[left]] -= 1
                if my_set[fruits[left]] == 0:
                    del my_set[fruits[left]]
                left += 1
            if len(my_set) <= 2:
                max_length = max(max_length, right - left + 1)
            right = right + 1
        return max_length

Time and Space Complexity

• Time: O(n)
• Space: O(1) (bounded by 2 types)

Why This Is Optimal

• Each index is visited at most twice (by right and possibly by left), giving linear time and constant extra space.

Common Pitfalls and Tips

• Always adjust left until the window has ≤2 distinct types.
• Use a frequency map to know when to delete a type (count reaches zero).
• Works for any non-negative integers as fruit types; order matters since we need a contiguous segment.

Final Takeaway

• Use Brute Force for learning.
• Prefer the Sliding Window solutions (Better/Optimal) for O(n) performance and O(1) space.
• This pattern generalizes to “longest subarray with at most K distinct elements” – here K = 2, a very common and powerful template in array/string problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.