904. Fruit Into Baskets

Problem Description

You are tasked to collect fruits from a series of fruit trees lined up in a row, with each tree bearing a certain type of fruit. You have two baskets to collect the fruits, and each basket can only hold one type of fruit, but as much of it as you'd like. Starting from any tree, you pick one fruit from each tree and move to the right, filling up your baskets with the fruits. The moment you encounter a tree with a fruit type that doesn't fit in either basket (since you can only carry two types), you must stop collecting. The goal is to maximize the amount of fruit you can collect under these constraints. The problem provides you with an array fruits, where fruits[i] denotes the type of fruit the ith tree produces. Your task is to determine the maximum number of fruits you can collect.

Intuition

This problem is a variation of the sliding window algorithm, which is useful for keeping track of a subset of data in a larger set. In this case, the subset is the range of trees from which we can collect fruits to fill our two baskets.

The intuition behind the solution is to maintain a window that slides over the array of fruit trees. The window should encompass the longest sequence of trees that only includes up to two types of fruits, satisfying the basket constraint. As we move through the array, we count the number of each type of fruit within the window using a counter. If adding a new fruit type to our window pushes us over the two-type limit, we shrink the window from the left until we are back within the limit, ensuring we always consider the maximum range of trees at each point.

The process is as follows:

• Start with an empty counter and a pointer at the beginning of the array.
• Iterate through the array one tree at a time, adding the fruit type to the counter.
• When the counter contains more than two types of fruits (i.e., we have more than two fruit types in our current window), we remove the leftmost fruit type from the window by decrementing its count in the counter. If its count reaches zero, we remove it from the counter.
• The window's size is adjusted accordingly throughout the process, and the maximum size of the window at any point during the iteration will be our answer.

Since we only ever add each element once and potentially remove each element once, this solution approach is efficient and works within O(n) time complexity, where n is the number of trees.

Learn more about Sliding Window patterns.

Solution Approach

The solution employs a few key concepts: sliding window, hash map (through Python's Counter class), and two pointers to optimize the process.

Here's a step-by-step walkthrough of how the totalFruit function operates:

1. Initialize Counter: The Counter from Python’s collections module is used to keep track of the number of each type of fruit within our current window. It's essentially a hash map tying fruit types to their counts.

2. Initialize Pointers: Two pointers are initialized. The j pointer indicates the start of our sliding window, and the for loop index (x in the loop) acts as the end of the sliding window, moving from the first to the last tree.

3. Iterate Over Fruit Trees: The for loop begins iterating over the fruit trees. For each fruit type encountered, add it to our counter and increment its count.

   1for x in fruits:
   2    cnt[x] += 1

4. Exceeding Basket Limit: After adding the new fruit type, we check if we have more than two types of fruits in our counter (len(cnt) > 2). If we do, it means our current window of trees has exceeded the basket constraint, and we must shrink the window from the left.

   1if len(cnt) > 2:
   2    y = fruits[j]
   3    cnt[y] -= 1
   4    if cnt[y] == 0:
   5        cnt.pop(y)
   6    j += 1

   In this block, we reduce the count of the leftmost fruit type by one (by getting the fruit at index j) and then increment the j pointer to effectively remove the tree from the window. If the leftmost fruit count drops to zero, it means there are no more trees of that fruit type in our current window, so we remove it from the counter.

5. Maximum Fruits: In each iteration, our window potentially encapsulates a valid sequence of at most two types of fruits. Since we're passing through all trees only once, and the j pointer never steps backward, the length of the maximum window will be found naturally. By subtracting j from the total number of fruits (len(fruits)), we get the length of this maximum window, which also represents the maximum number of fruits we can collect.

   1return len(fruits) - j

This algorithm effectively finds the longest subarray with at most two distinct elements, which corresponds to the largest quantity of fruit we can collect in our two baskets. The use of the sliding window technique allows for an efficient O(n) time complexity because each tree is evaluated only once, and each time the start of the window moves to the right, it never moves back.

Example Walkthrough

Let's illustrate the solution approach using a simple example. Consider the following series of fruit trees and their corresponding fruits:

1Trees Index: 0  1  2  3  4  5  6
2Fruits Type: A  B  A  A  C  B  B

We will walk through the algorithm step by step:

1. Initialize Counter: We will use a Counter to keep track of the types of fruits we currently have in our baskets.

2. Initialize Pointers: We will initialize two pointers, j and x. j will start at 0 and indicates the beginning of our window.

3. Iterate Over Fruit Trees: As we iterate over the trees with our x pointer, we'll perform the following steps:

1x = 0, fruit = A
2Counter = {'A': 1}
3Window = [A]
4
5x = 1, fruit = B
6Counter = {'A': 1, 'B': 1}
7Window = [A, B]
8
9x = 2, fruit = A
10Counter = {'A': 2, 'B': 1}
11Window = [A, B, A]
12
13x = 3, fruit = A
14Counter = {'A': 3, 'B': 1}
15Window = [A, B, A, A]
16
17x = 4, fruit = C
18Counter = {'A': 3, 'B': 1, 'C': 1}
19Current window exceeds the allowed number of fruit types (more than 2).

4. Exceeding Basket Limit: Once we hit the third type of fruit, in this case, 'C', we need to shrink our window from the left side:

1Counter after adding 'C' = {'A': 3, 'B': 1, 'C': 1} (more than 2 types, must remove one)
2We remove the leftmost fruit type 'A' by one unit.
3j = j + 1 (j = 1 now)
4
5Counter = {'A': 2, 'B': 1, 'C': 1}
6We still have three types of fruits. We need to remove 'A' completely to satisfy the basket constraint.
7So we remove 'A' one more time.
8j = j + 1 (j = 2 now)
9
10Counter = {'A': 1, 'B': 1, 'C': 1}
11Still more to do. We remove 'A' completely.
12j = j + 1 (j = 3 now)
13
14Counter = {'B': 1, 'C': 1}
15Now we have exactly 2 types of fruit in the basket.
16Window = [A, C, B, B]

5. Maximum Fruits: We continue this process until the end. In the end, our window will look like this:

1Final Window = [C, B, B]
2Length of Final Window = 3

The length of the final window indicates the maximum number of fruits we can collect, which is 3 in this example.

Thus, using our algorithm, we determine that the longest sequence of trees where we can collect fruits without breaking the rules (up to 2 types of fruits) is [C, B, B], and the total amount of fruit collected is 3.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of fruits in the input list, fruits. This is because the code uses a single loop to iterate through all the fruits exactly once.

The space complexity of the code is also O(n), primarily due to the Counter data structure cnt which in the worst-case scenario could store a frequency count for each unique fruit in the input list if all fruits are different. However, in practical terms, since the problem is constrained to finding the longest subarray with at most two distinct integers, the space complexity can effectively be seen as O(2) or constant O(1), as there will never be more than two unique fruits in the counter at any time.

Learn more about how to find time and space complexity quickly using problem constraints.