Fruit Into Baskets

Problem Summary

Given a list of fruit types, and you can only have two types of fruits
If you can only pick 1 fruit from each row, how many max can you have with you

What is Being Asked?

Copy of Longest Substring with At Most K Distinct Characters

Key Observations

(Patterns, constraints, or hints in the problem statement.)

Solve it in $O (n)$ time

Approach Taken

Same as the other problem

Approach Taken

because we want a count + unique chars we need hashmap with char to count
while removing from left, if count is 0 remove the key val altogether
do a max(cur, end-start + 1) after each addition

Main Concepts Used

Sliding Window

Time & Space Complexity

Time: $O (n)$ → Reason: Doing one pass
Space: $O (1)$ → We are storing character to count in our map. If input is of same fruit types then it would be $O (1)$ otherwise at max it could be 2 distinct types

Code

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        MAX_FRUIT_TYPES = 2

        start, max_fruits = 0, float("-inf")
        map = {}
        for end, end_fruit in enumerate(fruits):
            map[end_fruit] = 1 + map.get(end_fruit, 0)
            while len(map) > MAX_FRUIT_TYPES:
                left_fruit_type = fruits[start]
                map[left_fruit_type] -= 1
                if map[left_fruit_type] == 0:
                    map.pop(left_fruit_type)
                start += 1
            max_fruits = max(max_fruits, end - start + 1)
        return max_fruits