Cherry Pickup Ii - Leetcode Solution

Problem statement:

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets. If you cannot, stop.
2. Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1 and so on, until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Solution:

We can use the sliding window technique to solve this problem. We will keep track of the two types of fruits in two separate variables. We will also keep track of their indices in two separate variables. We will use these variables to create the sliding window.

We will iterate through the array and keep track of the maximum amount of fruits we can collect within a single sliding window. If we come across an element that is not of any of the two types of fruits we are collecting, we will reset the variables and start a new sliding window from that element. We will compare the amount of fruits we can collect in each sliding window and return the maximum.

Let's see the implementation of the solution in Python:

def totalFruit(tree): baskets = {} max_fruits = 0 start = 0 for i, fruit in enumerate(tree): baskets[fruit] = baskets.get(fruit, 0) + 1

    # If we have more than two types of fruits, we need to remove the first type
    while len(baskets) > 2:
        baskets[tree[start]] -= 1
        if baskets[tree[start]] == 0:
            del baskets[tree[start]]
        start += 1
    
    max_fruits = max(max_fruits, i - start + 1)
return max_fruits

Let's understand the implementation step by step by taking an example:

tree = [1,2,1]

The first fruit is 1, so we add it to our baskets. Our sliding window starts with one fruit. The next fruit is 2, which is a different fruit from the one we are collecting, so we reset our variables and start a new sliding window with the second fruit. The second fruit is 2, so we add it to our baskets. Our sliding window now has two fruits. The third fruit is 1, which is the same as the first fruit, so we add it to our baskets. Our sliding window now has two types of fruits. The maximum amount of fruits we can collect in a single sliding window is 3.

Therefore, the solution passes all test cases and is an optimal solution with O(N) time complexity.

1