Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The picking rules describe a contiguous subarray containing at most two distinct fruit types. Extending its right edge can introduce a third type; removing elements from the left restores validity. A sliding window finds the longest such segment without reconsidering earlier starting positions.

Approach

Keep a left pointer and counts of fruit types inside the current window.
Add each new rightmost fruit. While more than two types are present, remove the leftmost fruit and advance the left pointer, deleting zero-count entries.
Once valid, compare the window length with the best length. This is the longest valid window ending at that right endpoint.
Return the maximum. Windows containing just one fruit type are valid too.

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        n = len(fruits)
        b = defaultdict(int)
        res = 0
        l = 0

        for r in range(n):
            b[fruits[r]] += 1
            while len(b) > 2:
                b[fruits[l]] -= 1
                if b[fruits[l]] == 0:
                    del b[fruits[l]]
                l += 1
            res = max(res, r - l + 1)

        return res

Complexity analysis

Each of the n fruits enters and leaves the window at most once, so time is O(n). The frequency map holds at most three types during an update, so auxiliary space is O(1).