How do you solve Fruit Into Baskets on LeetCode?

Fruit Into Baskets (LeetCode #904) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: We can only have two types of fruits at any time.

What is the brute force solution for Fruit Into Baskets?

The brute force approach for Fruit Into Baskets is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible starting point and counting how many fruits can be collected until we reach a type that cannot fit in our baskets. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Fruit Into Baskets?

Fruit Into Baskets uses the following concepts: Array, Hash Table, Sliding Window. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Fruit Into Baskets?

Explain your thought process clearly while coding. Discuss edge cases and how your solution handles them. Practice similar sliding window problems to build intuition.

What are common mistakes when solving Fruit Into Baskets?

Not handling edge cases where all fruits are the same. Failing to update the left pointer correctly when the fruit count exceeds two.

#904

Fruit Into Baskets

Medium

ArrayHash TableSliding WindowHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a sliding window approach to maintain a dynamic range of fruits collected. This allows us to efficiently expand and contract our window to ensure we only have two types of fruits at any time.

⚙️

Algorithm

4 steps

1Step 1: Initialize two pointers (left and right) and a hashmap to count the fruits.
2Step 2: Expand the right pointer to include new fruits until we have more than two types.
3Step 3: When we exceed two types, move the left pointer to reduce the count until we are back to two types.
4Step 4: Keep track of the maximum size of the window during this process.

solution.py13 lines

1def total_fruits(fruits):
2    left = 0
3    fruit_count = {}
4    max_fruits = 0
5    for right in range(len(fruits)):
6        fruit_count[fruits[right]] = fruit_count.get(fruits[right], 0) + 1
7        while len(fruit_count) > 2:
8            fruit_count[fruits[left]] -= 1
9            if fruit_count[fruits[left]] == 0:
10                del fruit_count[fruits[left]]
11            left += 1
12        max_fruits = max(max_fruits, right - left + 1)
13    return max_fruits

ℹ

Complexity note: The time complexity is linear because each fruit is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is linear due to the hashmap storing fruit counts.

1We can only have two types of fruits at any time.
2Using a sliding window allows us to efficiently manage the types of fruits collected.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.