DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Fruit Into Baskets

mediumSliding window

Problem statement

A row of trees is described by fruits, where fruits[i] is the type of fruit on tree i. You have two baskets, and each basket can hold only one type of fruit (but any amount of it).

You choose a starting tree, then move right one tree at a time, picking exactly one fruit from each tree into a basket. You must stop as soon as you reach a tree whose fruit fits in neither basket. Return the most fruit you can collect.

Stripped of the story: find the longest contiguous block of fruits that contains at most two distinct values.

Examples

Example 1

Input: fruits = [1, 2, 1, 3, 3, 2, 2]

Output: 4

Explanation: Start at index 3: [3, 3, 2, 2] uses only types 3 and 2.

Example 2

Input: fruits = [4, 4, 4]

Output: 3

Explanation: One type fits in one basket, so you pick every tree.

Hints

Approach

Keep a window [left, right] with a map from fruit type to its count inside the window. The window is valid while the map has at most two keys.

  1. For each right, add fruits[right] to the map.
  2. While the map has more than two keys, decrement the count of fruits[left], delete it when it reaches zero, and move left forward.
  3. Update the best length with right - left + 1.

Deleting a key when its count reaches zero is what keeps "number of keys" equal to "number of distinct types".

ComplexityTime O(n)Space O(1)
Python
class Solution:
def totalFruit(self, fruits: list[int]) -> int:
count = {} # fruit type -> how many in the window
left = 0
best = 0
for right, kind in enumerate(fruits):
count[kind] = count.get(kind, 0) + 1
while len(count) > 2: # a third type: shrink from the left
old = fruits[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
best = max(best, right - left + 1)
return best

Follow-up questions

  • Generalise to at most k distinct types.
  • Return the start index of the best window.

Frequently asked questions

The map never holds more than three keys, and only for a moment before the shrink loop removes one.

Replace 2 with k. The algorithm is the general "longest subarray with at most k distinct values" window, and space becomes O(k).

Once the story is removed, it is "the longest run of events that touches at most two services" or "the longest stretch of requests served by at most two backends". Recognising the underlying window problem is the real test.