A row of trees is given as fruits, where fruits[i] is the type of fruit on tree i. You have two baskets, and each basket holds only one type of fruit (but any amount of it). Starting from any tree, you pick one fruit from every tree moving right, and you must stop at the first tree whose fruit fits in neither basket. Return the maximum number of fruits you can collect.
[2,3,2,2].- 1 <= fruits.length <= 10^5
- 0 <= fruits[i] < fruits.length
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every starting tree and walking right is O(n^2). The rules simply describe the longest contiguous block containing at most two distinct values. Keep a window with a count of each type inside. Extend right; if a third type appears, move left forward, decreasing counts, until some type disappears. The window is then valid again, and each index is added and removed once.
Algorithm
- Keep a map
count,left = 0,best = 0. - For each
right, increasecount[fruits[right]]. - While the map has more than 2 keys: decrease
count[fruits[left]], delete it at zero, moveleftright. - Update
best = max(best, right - left + 1). - Return
best.
O(n)Space: O(1), at most three keys in the map2 replaced by K. Interviewers often follow up with exactly K distinct, which is atMost(K) - atMost(K - 1) for counting subarrays.class Solution: def totalFruit(self, fruits: List[int]) -> int: count = defaultdict(int) # type -> count in window left = best = 0 for right, f in enumerate(fruits): count[f] += 1 while len(count) > 2: # a third type: shrink from the left g = fruits[left] count[g] -= 1 if count[g] == 0: del count[g] left += 1 best = max(best, right - left + 1) return best