LeetMotion
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:
Given the integer array fruits, return the maximum number of fruits you can pick.
basket dictionary mapping fruit type to its count in the current window. When you add a fruit on the right, increment its count. When you must shrink from the left, decrement the leftmost fruit's count and delete its key if it reaches zero (freeing a basket slot). len(basket) > 2means you've exceeded your limit.while loop inside the for loop, each element enters the window exactly once (when r advances) and leaves the window at most once (when l advances past it). So the total number of basket operations across the entire algorithm is at most 2n, giving O(n) time overall. The hash map operations are O(1) on average.Imagine a produce truck driver harvesting fruit along a highway lined with orchards. The truck has exactly two compartments, each dedicated to a single fruit variety. The driver starts at any orchard and drives continuously rightward, loading fruit from every tree. The moment they reach an orchard with a third fruit variety, they can't load it — so they offload from the back of the truck (left pointer advance) until one compartment empties, then continue. The goal: find the longest stretch of highway the driver can harvest without emptying a compartment midway.
We use a variable-size sliding window with a basket hash map that tracks the count of each fruit type within the current window. We greedily expand rightward and only shrink when the basket exceeds 2 distinct types.
l = 0, res = 0, basket = {}.r: add fruits[r] to basket (increment count).len(basket) > 2: decrement basket[fruits[l]], delete if zero, increment l.res = max(res, r - l + 1).res.*Space is O(1) because the basket holds at most 3 keys at any moment (we immediately shrink when it would hold a 4th), so the hash map is bounded by a constant.
Discussion
…