aboutsummaryrefslogtreecommitdiff
path: root/fruit_into_baskets.py
blob: 9197d0321612ad2f7ac849523517d81c62acb40d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 904. Fruit Into Baskets

"""
you are visiting a farm that has a single row of fruit trees arranged from
left t oright. the trees are represented by an integer array 'fruits' where
'fruits[i]' is the type of fruit the i'th tree produces. you want to collect
as much fruit as possible. however, the owner has some strict rules that you
must follow: you can only have two baskets and each can only hoold a single
type of fruit (unlimited quantity). starting from any tree, you must pick
exacty one fruit from every tree while moving to the right. once you reach a
tree with fruit that cannot fit in your baskets, you must stop. given the int
array 'fruits', return the maximum number of fruits you can pick
"""


class Solution(object):
    def totalFruit(self, fruits):
        """
        :type fruits: List[int]
        :rtype: int
        """
        cnt, i = {}, 0
        for j, v in enumerate(fruits):
            cnt[v] = cnt.get(v, 0) + 1
            if len(cnt) > 2:
                cnt[fruits[i]] -= 1
                if cnt[fruits[i]] == 0:
                    del cnt[fruits[i]]
                i += 1
        return j - i + 1


if __name__ == "__main__":
    obj = Solution()
    print(obj.totalFruit(fruits=[1, 2, 1]))
    print(obj.totalFruit(fruits=[0, 1, 2, 2]))
    print(obj.totalFruit(fruits=[1, 2, 3, 2, 2]))