Fruits Into Baskets II

Difficulty: Easy | Acceptance: 70.20% | Paid: No Topics: Array, Binary Search, Segment Tree, Simulation, Ordered Set

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:

You 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 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.

Examples
Constraints
Brute Force Simulation
Sliding Window
Binary Search on Answer

Examples

Example 1

Input:

fruits = [4,2,5], baskets = [3,5,4]

Output:

Explanation: fruits[0] = 4 is placed in baskets[1] = 5.

fruits[1] = 2 is placed in baskets[0] = 3.

fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2

Input:

fruits = [3,6,1], baskets = [6,4,7]

Output:

Explanation: fruits[0] = 3 is placed in baskets[0] = 6.

fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.

fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

Constraints

- n == fruits.length == baskets.length
- 1 <= n <= 100
- 1 <= fruits[i], baskets[i] <= 1000

Brute Force Simulation

Intuition We can try every possible starting tree and expand to the right as far as possible while maintaining at most two types of fruits.

Steps

Iterate through each index i as the starting point.
Initialize a set to track fruit types in the current window.
Expand the window to the right j from i to the end of the array.
Add fruits[j] to the set.
If the set size exceeds 2, break the loop.
Update the maximum length found.

python

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

Complexity

Time: O(n²)
Space: O(1)
Notes: Simple but too slow for large inputs.

Sliding Window

Intuition We maintain a window [left, right] that contains at most 2 types of fruits. As we expand the right pointer, if we encounter a third type, we shrink the left pointer until the window becomes valid again.

Steps

Use a hash map to count the frequency of fruits in the current window.
Iterate right from 0 to n-1.
Increment the count of fruits[right].
While the map size is greater than 2:
- Decrement the count of fruits[left].
- If count reaches 0, remove it from the map.
- Increment left.
Update the maximum window size.

python

class Solution:\n    def totalFruit(self, fruits: list[int]) -> int:\n        count = {}\n        l = 0\n        max_fruits = 0\n        for r, f in enumerate(fruits):\n            count[f] = count.get(f, 0) + 1\n            while len(count) > 2:\n                count[fruits[l]] -= 1\n                if count[fruits[l]] == 0:\n                    del count[fruits[l]]\n                l += 1\n            max_fruits = max(max_fruits, r - l + 1)\n        return max_fruits\n

Complexity

Time: O(n)
Space: O(1)
Notes: Optimal solution. Each element is added and removed from the map at most once.

Binary Search on Answer

Intuition The answer (maximum window length) is monotonic. If a window of size k is possible, then any size < k is also possible. We can binary search for the maximum k and check if a valid window of that size exists.

Steps

Binary search for the answer low to high.
For a mid value k, check if any subarray of length k has at most 2 distinct fruits.
The check function uses a sliding window of fixed size k with a frequency map.

python

class Solution:\n    def totalFruit(self, fruits: list[int]) -> int:\n        def canPick(k):\n            count = {}\n            for i in range(len(fruits)):\n                count[fruits[i]] = count.get(fruits[i], 0) + 1\n                if i >= k:\n                    count[fruits[i - k]] -= 1\n                    if count[fruits[i - k]] == 0:\n                        del count[fruits[i - k]]\n                if i >= k - 1 and len(count) <= 2:\n                    return True\n            return False\n\n        l, r = 0, len(fruits)\n        while l < r:\n            mid = (l + r + 1) // 2\n            if canPick(mid):\n                l = mid\n            else:\n                r = mid - 1\n        return l\n

Complexity

Time: O(n log n)
Space: O(1)
Notes: Useful when the problem asks for the maximum length satisfying a monotonic condition.