904.md

Fruits into Baskets

Description

link

---

Solution

Translation: Find out the longest length of subarrays with at most 2 different numbers?

• a: first show and we pick into baskets
• b: second show one
• c: the third one

OR: Sliding Windows

---

Code

O(n) O(1)

class Solution:
    def totalFruit(self, tree):
        """
        :type tree: List[int]
        :rtype: int
        """
        res = cur = count_b = a = b = 0
        for c in tree:
            cur = cur + 1 if c in (a, b) else count_b + 1
            count_b = count_b + 1 if c == b else 1
            if b != c: a, b = b, c
            res = max(res, cur)
        return res

    def totalFruit2(self, tree):
        count = {}
        i = res = 0
        for j, v in enumerate(tree):
            count[v] = count.get(v, 0) + 1
            while len(count) > 2:
                count[tree[i]] -= 1
                if count[tree[i]] == 0: del count[tree[i]]
                i += 1
            res = max(res, j - i + 1)
        return res