Leetcode 904 Fruit Into Baskets

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:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets. Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick.

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

• General idea The input is a row of trees, and each tree bears fruit. This number represents the type of fruit (note, not the number). Let you pick the fruit from a certain position to the right continuously. There are only two baskets, and each basket can only put the same type of fruit. If there is no fruit to pick during the traversal to the right, or the fruit of the current tree cannot be placed in the fruit basket, then stop and ask how many fruits can be picked in total.

Problem solving method Now LeetCode likes to produce a situational question, it takes people a long time to understand the meaning of the question and abstract it out. If this problem is abstracted into a model, it is to find the longest continuous sub-array of an array, requiring that there are at most two different elements in this sub-array.

If the above abstraction is done, then we can easily think of using double pointers to calculate the number of all elements in the double pointer interval. This number is the number of fruits that we can pick. At the same time, in the process of moving, it is necessary to ensure that the type of elements in the double pointer interval is at most 2. When doing the question before, the Counter was used to directly count all the numbers in an interval, which would time out. Therefore, a dictionary is used for storage, and only the number of the rightmost and leftmost elements is updated each time.

The time complexity is O(N), and the space complexity is O(N).

class Solution(object):
    def totalFruit(self, tree):
        """
        :type tree: List[int]
        :rtype: int
        """
        left, right = 0, 0
        res = 0
        cnt = collections.defaultdict(int)
        while right < len(tree):
            cnt[tree[right]] += 1
            while len(cnt) > 2:
                cnt[tree[left]] -= 1
                if cnt[tree[left]] == 0:
                    del cnt[tree[left]]
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res