Solution to the Fruit Into Baskets interview problem [+ ВИДЕО]
Formulation of the problem
You visit a farm where trees are arranged in a single row from left to right. The trees are represented by an integer array fruits
Where fruits[i]
— is the type of fruit on the i-th tree.
You want to collect as much fruit as possible, but the farm owner has set the following rules:
You have two baskets, each of which can contain only one type of fruit.
Each basket can contain an unlimited amount of fruit.
Starting from any tree, you must collect fruits from each tree (including the starting one), moving to the right.
If you come across a tree whose fruit cannot fit into your baskets, you should stop.
The challenge is to find the maximum number of fruits that can be collected while following these rules.
Approach to the solution
To solve the problem, we will use a sliding window technique and a hash table to keep track of the number of each type of fruit in the current window.
Algorithm
Initialization of variables:
res
to store the result (maximum amount of fruits).type_counter
to track the amount of each type of fruit in the current window.left
to mark the left border of the window.
Traversing an array
fruits
:We use a variable
right
to mark the right border of the window.Increase the counter for the current fruit type
right_fruit
.
Checking the window validity condition:
If the number of fruit types in the window becomes more than two (
len(type_counter) == 3
), move the left border of the windowleft
to the right, decreasing the counters for fruits and removing fruit types with a zero counter.
Updating the result:
Solution code
from collections import defaultdict
from typing import List
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
res = 0
type_counter = defaultdict(int)
left = 0
for right in range(len(fruits)):
right_fruit = fruits[right]
type_counter[right_fruit] += 1
while len(type_counter) == 3:
left_fruit = fruits[left]
type_counter[left_fruit] -= 1
if type_counter[left_fruit] == 0:
del type_counter[left_fruit]
left += 1
res = max(res, right - left + 1)
return res
Code Explanation
Initialization:
res
– variable for storing the maximum number of fruits.type_counter
– a hash table to track the number of each type of fruit in the current window.left
– index of the left border of the window.
Main loop:
Reduce window size:
If the number of fruit types in the window exceeds two (
len(type_counter) == 3
), we move the left border of the window to the right until the number of fruit types becomes acceptable (two or less).
Updating the result:
Visualization of the solution
Let's consider an array fruits = [1, 2, 1, 2, 3, 3, 2, 1]
and visualize the steps of solving the problem, showing the current state of the sliding window.
Execution steps:
Iteration 0:
Current fruit: 1
Window: [1]2, 1, 2, 3, 3, 4, 1, 2
type_counter: {1: 1}
Window length: 1
Iteration 1:
Current fruit: 2
Window: [1, 2]1, 2, 3, 3, 4, 1, 2
type_counter: {1: 1, 2: 1}
Window length: 2
Iteration 2:
Current fruit: 1
Window: [1, 2, 1]2, 3, 3, 4, 1, 2
type_counter: {1:2, 2:1}
Window length: 3
Iteration 3:
Current fruit: 2
Window: [1, 2, 1, 2]3, 3, 4, 1, 2
type_counter: {1:2, 2:2}
Window length: 4
Iteration 4:
Current fruit: 3
Window: [1, 2, 1, 2, 3]3, 4, 1, 2
type_counter: {1:2, 2:2, 3:1}
Window length: 5
Window reduction:
left: 1
Window after reduction: 1, [2, 1, 2, 3]3, 4, 1, 2
type_counter: {1: 1, 2: 2, 3: 1}
Window length: 4
left: 2
Window after reduction: 1, 2, [1, 2, 3]3, 4, 1, 2
type_counter: {1: 1, 2: 1, 3: 1}
Window length: 3
left: 3
Window after reduction: 1, 2, 1, [2, 3]3, 4, 1, 2
type_counter: {2: 1, 3: 1}
Window length: 2
Window after updating the result: 1, 2, 1, [2, 3]3, 4, 1, 2
Current maximum: 4
Iteration 5:
Current fruit: 3
Window: 1, 2, 1, [2, 3, 3]4, 1, 2
type_counter: {2: 1, 3: 2}
Window length: 3
Iteration 6:
Current fruit: 4
Window: 1, 2, 1, [2, 3, 3, 4]12
type_counter: {2:1, 3:2, 4:1}
Window length: 4
Window reduction:
left: 4
Window after reduction: 1, 2, 1, 2, [3, 3, 4]12
type_counter: {3:2, 4:1}
Window length: 3
Window after updating the result: 1, 2, 1, 2, [3, 3, 4]12
Current maximum: 4
Iteration 7:
Current fruit: 1
Window: 1, 2, 1, 2, [3, 3, 4, 1]2
type_counter: {3:2, 4:1, 1:1}
Window length: 4
Window reduction:
left: 5
Window after reduction: 1, 2, 1, 2, 3, [3, 4, 1]2
type_counter: {3:1, 4:1, 1:1}
Window length: 3
left: 6
Window after reduction: 1, 2, 1, 2, 3, 3, [4, 1]2
type_counter: {4:1, 1:1}
Window length: 2
Window after updating the result: 1, 2, 1, 2, 3, 3, [4, 1]2
Current maximum: 4
Iteration 8:
Current fruit: 2
Window: 1, 2, 1, 2, 3, 3, [4, 1, 2]
type_counter: {4:1, 1:1, 2:1}
Window length: 3
Window reduction:
left: 7
Window after reduction: 1, 2, 1, 2, 3, 3, 4, [1, 2]
type_counter: {1: 1, 2: 1}
Window length: 2
Window after updating the result: 1, 2, 1, 2, 3, 3, 4, [1, 2]
Current maximum: 4
After all iterations, the maximum number of fruits that can be collected is 4.
Asymptotic complexity
Time complexity: O(n)
We are walking through the array
fruits
once using the right border of the window (right
).In the worst case, the left border of the window (
left
) also goes through each element of the array once.As a result, each element of the array is processed at most twice, which leads to a linear time complexity of O(n), where
n
— length of the arrayfruits
.
Memory complexity: O(1)
We use a hash table
type_counter
to store the quantity of each type of fruit in the current window.The maximum number of different types of fruits in the hash table is limited to two, since we only have two buckets.
Therefore, the amount of memory required to store data in a hash table does not depend on the size of the input array and remains constant.
This results in a constant memory complexity of O(1).