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:
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, then step 2, 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?
Example 1:
Input: [1,2,1] Output: 3 Explanation: We can collect [1,2,1].
Example 2:
Input: [0,1,2,2] Output: 3 Explanation: We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1].
Example 3:
Input: [1,2,3,2,2] Output: 4 Explanation: We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2].
Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4] Output: 5 Explanation: We can collect [1,2,1,1,2]. If we started at the first tree or the eighth tree, we would only collect 4 fruits.
Note:
1 <= tree.length <= 400000 <= tree[i] < tree.length
The description was taken from https://leetcode.com/problems/fruit-into-baskets/.
#O(N) Time, O(1) Spaceclass Solution: def totalFruit(self, tree: List[int]) -> int: if not tree or len(tree) == 0: return 0 left, right = 0, 0 most_fruit = 0 baskets = {} while right < len(tree): if tree[right] in baskets:
baskets[tree[right]] += 1
else:
baskets[tree[right]] = 1
while len(baskets) > 2:
baskets[tree[left]] -= 1
if baskets[tree[left]] == 0:
del baskets[tree[left]]
left += 1 most_fruit = max(most_fruit, right - left + 1) right += 1 return most_fruitThe description is a little bit shaky. Basically, we have two baskets and both baskets can hold one type of fruit. We will need to return the biggest subarray that only contains two types of fruit: two unique numbers.
We can achieve this by utilizing a sliding window. A good indication that this is the right approach is when the input is a string or some type of list, and we are asked to search for a specific substring or sublist that satisfies a given constraint.
Like other sliding window problems, we will have a running count, we will test our window against a condition, if the condition is satisfactory then we will continue to expand our window. If the condition is not, we will shrink our window and begin to try a different window, all while keeping track of the most favorable window we have seen.
First off, if we have no tree to pick fruit from or the tree is empty, we have no fruit that we can pick.
if not tree or len(tree) == 0: return 0
If we do have a tree, will initialize our left and right pointers to the beginning of it. These will be used to measure our window later on.
left, right = 0, 0
We will also create a variable to keep count of the most fruit, the biggest window, that we have seen.
most_fruit = 0
Next, we will initialize a hashmap for the two baskets we have. Here we are only keeping two types of fruit, so we will only require constant space.
The baskets will contain a count of the types of fruits that we have and a count of those types. This way, we can utilize the length of the baskets to know whether or not we have more than two kinds of unique fruits.
baskets = {}
Then, we will create a loop that will run while we still have fruit in the tree that we haven't seen.
while right < len(tree):
We can view it like this, our right pointer will be in charge of picking fruit and throwing it into the basket.
Our left pointer will be in charge of pulling old fruit out from the basket if we have more than two types.
Let's initialize the right fruit's place in the basket if it is not already there, otherwise, we will increment the frequency of the fruit.
if tree[right] in baskets:
baskets[tree[right]] += 1
else:
baskets[tree[right]] = 1
If our basket has more than two unique kinds of fruit, we will need to shrink it.
We will do this by evicting the leftmost, oldest fruit from the baskets. This can be done by decrementing the count of the left type of fruit in the window and moving the left pointer to the right. Before we move the left pointer though, we'll need to make sure we aren't leaving a zero count of fruit in the window once we remove a fruit because it will contribute to the length still.
If this is the case, we will delete the left fruit key from the baskets before continuing.
while len(baskets) > 2:
baskets[tree[left]] -= 1
if baskets[tree[left]] == 0:
del baskets[tree[left]]
left += 1
This is how we will be able to consider each window as we move along.
[1,2,3,2,2]
[3,3,3,1,2,1,1,2]
This is the overall picture of sliding window problems. We will test against a condition, in this case, only having two unique numbers within our window. If the condition is satisfactory, then we will continue to expand our window. If the condition is not, we will decrease our window length to try a different window, all while keeping track of the most favorable window we have seen.
When we have made sure we have the right number of unique fruit within our baskets, we will count the fruit amount by calculating the distance between the left and right pointers.
If it is more than the most fruit we had previously seen, this window contains the most fruit so far.
most_fruit = max(most_fruit, right - left + 1)
We will then expand our window by one fruit and repeat.
right += 1
Once we have stepped through the entire tree, we will return the most fruit we could possibly fit in our baskets.
return most_fruit