Problem Statement in English

You’re given a line of trees. Each tree produces a certain type of fruit; fruits[i] is the type of fruit produced by the i-th tree.

You want to collect as much fruit as possible in two baskets. As soon as you encounter a third type of fruit, you must stop collecting.

You can start with any tree, and you can move to the next tree only if it produces a type of fruit that is already in one of your two baskets.

Your goal is to find the maximum number of fruits you can collect.

Approach

We can use the sliding window technique to solve this problem. We’ll maintain a window that contains at most two types of fruits.

As we expand the window by moving the right pointer, we’ll keep track of the count of each fruit type in the current window. If we encounter a third type of fruit, we’ll shrink the window from the left until we have at most two types of fruits again.

Solution in Python


class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        hm = {}

        l = res = t = 0

        for r in range(len(fruits)):
            hm[fruits[r]] = hm.get(fruits[r], 0) + 1
            t += 1

            while len(hm.keys()) > 2:
                hm[fruits[l]] -= 1
                t -= 1

                if not hm[fruits[l]]:
                    del hm[fruits[l]]
                
                l += 1

            res = max(res, t)

        return res

Complexity

  • Time: O(n)O(n)
    Since we traverse the array once with two pointers, the time complexity is linear in terms of the number of trees.

  • Space: O(n)O(n)
    Since we’re using a hashmap to store the count of each fruit type, the space complexity is linear in terms of the number of unique fruit types.

And we are done.