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.

    for x in fruits:
        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.

    if len(cnt) > 2:
        y = fruits[j]
        cnt[y] -= 1
        if cnt[y] == 0:
            cnt.pop(y)
        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.

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Trees Index: 0  1  2  3  4  5  6
Fruits 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:

x = 0, fruit = A
Counter = {'A': 1}
Window = [A]

x = 1, fruit = B
Counter = {'A': 1, 'B': 1}
Window = [A, B]

x = 2, fruit = A
Counter = {'A': 2, 'B': 1}
Window = [A, B, A]

x = 3, fruit = A
Counter = {'A': 3, 'B': 1}
Window = [A, B, A, A]

x = 4, fruit = C
Counter = {'A': 3, 'B': 1, 'C': 1}
Current window exceeds the allowed number of fruit types (more than 2).
  1. 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:
Counter after adding 'C' = {'A': 3, 'B': 1, 'C': 1} (more than 2 types, must remove one)
We remove the leftmost fruit type 'A' by one unit.
j = j + 1 (j = 1 now)

Counter = {'A': 2, 'B': 1, 'C': 1}
We still have three types of fruits. We need to remove 'A' completely to satisfy the basket constraint.
So we remove 'A' one more time.
j = j + 1 (j = 2 now)

Counter = {'A': 1, 'B': 1, 'C': 1}
Still more to do. We remove 'A' completely.
j = j + 1 (j = 3 now)

Counter = {'B': 1, 'C': 1}
Now we have exactly 2 types of fruit in the basket.
Window = [A, C, B, B]
  1. Maximum Fruits: We continue this process until the end. In the end, our window will look like this:
Final Window = [C, B, B]
Length 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

1from collections import Counter
2
3class Solution:
4    def totalFruit(self, fruits: List[int]) -> int:
5        # Initialize a counter to keep track of the count of each type of fruit
6        fruit_counter = Counter()
7        # Initialize a variable to keep track of the starting index of the current window
8        start_index = 0
9        # Iterate over the list of fruits
10        for fruit in fruits:
11            # Increment the count for the current fruit
12            fruit_counter[fruit] += 1
13            # If the counter has more than two types of fruits, we shrink the window
14            if len(fruit_counter) > 2:
15                # The fruit at the start index needs to be removed or decremented
16                start_fruit = fruits[start_index]
17                fruit_counter[start_fruit] -= 1
18                # Remove the fruit from counter if its count drops to 0
19                if fruit_counter[start_fruit] == 0:
20                    del fruit_counter[start_fruit]
21                # Move the start index forward
22                start_index += 1
23        # Calculate the maximum length of the subarray with at most two types of fruits
24        max_length = len(fruits) - start_index
25        return max_length
26
1import java.util.HashMap; // Import HashMap class for usage
2
3class Solution {
4    public int totalFruit(int[] tree) {
5        // Create a HashMap to keep track of the count of each type of fruit
6        HashMap<Integer, Integer> fruitCount = new HashMap<>();
7        int start = 0; // Start of the sliding window
8        int maxFruits = 0; // Maximum number of fruits collected
9
10        // Iterate through the array of fruits using the end of the sliding window
11        for (int end = 0; end < tree.length; end++) {
12            // Add the current fruit to the fruitCount map or update its count
13            fruitCount.put(tree[end], fruitCount.getOrDefault(tree[end], 0) + 1);
14
15            // If the map contains more than 2 types of fruit, shrink the window from the start
16            while (fruitCount.size() > 2) {
17                fruitCount.put(tree[start], fruitCount.get(tree[start]) - 1);
18                // If the count of a fruit at the start of the window becomes 0, remove it
19                if (fruitCount.get(tree[start]) == 0) {
20                    fruitCount.remove(tree[start]);
21                }
22                start++; // Move the start of the window forward
23            }
24
25            // Calculate the maximum number of fruits in the current window
26            maxFruits = Math.max(maxFruits, end - start + 1);
27        }
28        // Return the size of the largest contiguous subarray with 2 types of fruits
29        return maxFruits;
30    }
31}
32
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    int totalFruit(vector<int>& fruits) {
8        // Initialize a hash map to count the fruits
9        unordered_map<int, int> fruitCounter;
10      
11        // Initialize the start of the current window
12        int windowStart = 0;
13      
14        // Get the number of fruits
15        int totalFruits = fruits.size();
16      
17        // Iterate over all fruits
18        for (int windowEnd = 0; windowEnd < totalFruits; ++windowEnd) {
19            // Increase the count for the current fruit
20            fruitCounter[fruits[windowEnd]]++;
21          
22            // If there are more than 2 types of fruits in the current window
23            while (fruitCounter.size() > 2) {
24                // Decrease the count of the fruit at the start of the window
25                fruitCounter[fruits[windowStart]]--;
26              
27                // If the count becomes zero, remove the fruit from the map
28                if (fruitCounter[fruits[windowStart]] == 0) {
29                    fruitCounter.erase(fruits[windowStart]);
30                }
31              
32                // Move the window start forward
33                ++windowStart;
34            }
35        }
36      
37        // The maximum number of fruits is the size of the array minus the start of the last valid window
38        return totalFruits - windowStart;
39    }
40};
41
1function totalFruit(fruits: number[]): number {
2    // Initialize the length of the fruits array
3    const fruitCount = fruits.length;
4  
5    // Create a map to keep track of the frequency of each type of fruit within the sliding window
6    const fruitFrequencyMap = new Map<number, number>();
7
8    // `startIndex` represents the beginning index of the sliding window
9    let startIndex = 0;
10
11    // Iterate over each fruit in the fruits array
12    for (const fruit of fruits) {
13      
14        // Add the fruit to the map or update its frequency
15        fruitFrequencyMap.set(fruit, (fruitFrequencyMap.get(fruit) ?? 0) + 1);
16
17        // If we have more than 2 types of fruits, shrink the window from the left
18        if (fruitFrequencyMap.size > 2) {
19            // Fetch the fruit type at the start of the window for updating its frequency
20            const fruitType = fruits[startIndex++];
21            fruitFrequencyMap.set(fruitType, fruitFrequencyMap.get(fruitType) - 1);
22          
23            // If the frequency of the leftmost fruit type becomes 0, remove it from the map
24            if (fruitFrequencyMap.get(fruitType) === 0) {
25                fruitFrequencyMap.delete(fruitType);
26            }
27        }
28    }
29
30    // Calculate the maximum number of fruits collected in a contiguous subarray of size at most 2
31    return fruitCount - startIndex;
32}
33

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More