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 fruitsWhere 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:

1. You have two baskets, each of which can contain only one type of fruit.

2. Each basket can contain an unlimited amount of fruit.

3. Starting from any tree, you must collect fruits from each tree (including the starting one), moving to the right.

4. 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

1. 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.

2. 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.

3. 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 window left to the right, decreasing the counters for fruits and removing fruit types with a zero counter.

4. 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

1. 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.

2. Main loop:

3. 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).

4. 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 array fruits.

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).