Leetcode 904: Fruit Into Baskets

Intuition

Question = Find the longest sub-string consists of only two numbers.

Approach

Keep track of the last seen number before the current index, while Having a pointer to the start of such a valid sub-string that ends up in the current index (inclusively); Or if the number of the current index cannot be included in the current sub-string (The first third number, which terminates the construction), update the maximum, set start to the starting index of the last seen number (which refers to the longest valid sub-string, should the current number be included). And then update the basket, which is used to keep track of the two numbers (fruits) of the current sub-string.

If start cannot make the sub-string ending up at i (inclusively) valid, then any starting index before start cannot. If start can make the sub-string ending up at i (inclusively) valid, then any starting index between start and i can.

Complexity:

Time complexity: O(n)
Space complexity: O(1)

Code

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        start = 0
        max_fruits = 0
        last_candidate = (0, fruits[0])
        basket = []

        for i in range(len(fruits)):
            if fruits[i] not in basket:
                if len(basket) < 2:
                    basket.append(fruits[i])
                else:
                    max_fruits = max(max_fruits, i - start)
                    start = last_candidate[0]
                    basket = [fruits[i], last_candidate[1]]
            
            if fruits[i] != last_candidate[1]:
                last_candidate = (i, fruits[i])

        return max(max_fruits, len(fruits) - start)