Fruit Into Baskets

Medium

Fruit Into Baskets

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for each fruit type (e.g., are they positive integers, and if so, what's the maximum value)?
If the input array is empty or null, what should I return?
If the input array contains only one type of fruit, what should I return?
If the input array has multiple valid subarrays of maximum length, can I return any one of them?
Are the fruits represented as integers, characters, or some other data type?

Brute Force Solution

Approach

The brute force method to solve the fruit basket problem involves checking every possible continuous sequence of fruit. We're essentially figuring out, for every starting point, how far we can go while only picking at most two types of fruit. We then pick the longest such sequence.

Here's how the algorithm would work step-by-step:

Start with the very first fruit in the row.
See how many fruits you can pick, moving one fruit at a time, as long as you only have one or two types of fruit in your basket.
Record how many fruits you picked in this step. This becomes a potential answer.
Now, start with the second fruit in the row. Again, see how many fruits you can pick while only having one or two types.
Again, record how many fruits you picked. Compare that number to the previous potential answer and keep the bigger number.
Continue this process, starting with the third fruit, then the fourth, and so on until you've started with every fruit in the row.
After you've gone through all the starting positions, the largest number you recorded is the maximum number of fruits you can pick.

Code Implementation

def fruits_into_baskets_brute_force(fruits):
    maximum_fruits = 0
    for start_index in range(len(fruits)):
        # Iterate through possible starting positions

        for end_index in range(start_index, len(fruits)):
            # Check every possible subarray from the start_index

            subarray = fruits[start_index:end_index + 1]
            unique_fruits = set(subarray)

            if len(unique_fruits) <= 2:
                # Only proceed if the subarray contains at most 2 fruits

                maximum_fruits = max(maximum_fruits, len(subarray))

    return maximum_fruits

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n fruits in the input array, representing the starting position of a potential basket. For each starting position, the inner loop iterates through the remaining fruits to determine the maximum number of fruits that can be picked while adhering to the two-type constraint. In the worst-case scenario, the inner loop may iterate through almost all n fruits for each of the n starting positions. Therefore, the time complexity is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The described brute force algorithm checks all possible subarrays and keeps track of the maximum length found so far. It only requires a few variables to store the start and end indices of the current subarray and the maximum length seen so far. These variables consume a constant amount of space regardless of the number of fruits (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to pick the most fruit while only picking at most two types of fruit. We can solve this by strategically expanding and shrinking a 'window' of fruit types to maximize the fruit we pick. By keeping track of which fruit types are in the window, we can efficiently determine the longest valid selection.

Here's how the algorithm would work step-by-step:

Imagine a 'basket' that can only hold two types of fruit.
Start at the beginning of the fruit row and keep adding fruits to the basket as long as you are only adding one of the types already in the basket, or a new type if the basket has space.
If you encounter a third type of fruit and the basket is already full, you need to shrink the basket from the beginning until only two types of fruit remain.
Keep track of the longest sequence of fruit you have collected while following the two-type rule.
Repeat the expansion and shrinking process as you move along the row of fruit.
The longest sequence you recorded is the maximum amount of fruit you can collect following the rules.

Code Implementation

def max_fruit_count(fruits):
    window_start = 0
    max_length = 0
    fruit_frequency = {}

    for window_end in range(len(fruits)):
        right_fruit = fruits[window_end]
        if right_fruit not in fruit_frequency:
            fruit_frequency[right_fruit] = 0
        fruit_frequency[right_fruit] += 1

        # Shrink the sliding window, until we have at most 2 distinct fruit types in the fruit frequency dictionary.
        while len(fruit_frequency) > 2:
            left_fruit = fruits[window_start]
            fruit_frequency[left_fruit] -= 1

            # Clean up the fruit frequency map to ensure accuracy.
            if fruit_frequency[left_fruit] == 0:
                del fruit_frequency[left_fruit]

            window_start += 1

        # Remember the maximum length so far.
        max_length = max(max_length, window_end - window_start + 1)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of fruits using a sliding window approach. The outer loop expands the window, and the inner loop shrinks it only when more than two fruit types are encountered. Each element in the array is visited at most twice, once during the expansion and potentially once during the shrinking of the window. Therefore, the time complexity is proportional to the number of fruits, n, making it O(n).

Space Complexity

O(1) – The algorithm utilizes a sliding window approach, primarily relying on a constant number of variables to track the types of fruit within the basket. Specifically, it uses a hash map (or dictionary) to store at most two fruit types and their counts. Since the basket can hold a maximum of two fruit types, the size of this data structure is limited to a constant value, independent of the input size N (the number of fruits). Thus, the auxiliary space used by the algorithm remains constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as no fruit can be collected if the input is invalid.
Array with only one type of fruit	Return the length of the array as all fruits can be picked.
Array with only two types of fruit	Return the length of the array as all fruits can be picked.
Array with many distinct types of fruit	The sliding window approach will ensure the maximum length of fruits of two types are collected.
Array with repeating sequences of two fruit types	Sliding window should correctly identify the largest sequence of two fruit types when they repeat.
Very large array exceeding memory constraints	Sliding window uses constant extra space, making it suitable even for large arrays.
Integer overflow when calculating the length of the sub array	Use appropriate data types (e.g., long in Java) to store the length.
Input array contains non-integer values	Throw IllegalArgumentException since the question assumes array of integer representing the fruits.