You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the i<sup>th</sup> tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

1. You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
2. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
3. Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

For example:

• fruits = [1,2,1] should return 3 because we can pick from all 3 trees.
• fruits = [0,1,2,2] should return 3 because we can pick from trees [1,2,2]. If we had started at the first tree, we would only pick from trees [0,1].
• fruits = [1,2,3,2,2] should return 4 because we can pick from trees [2,3,2,2]. If we had started at the first tree, we would only pick from trees [1,2].

Can you provide an efficient solution to this problem, considering the constraints that 1 <= fruits.length <= 10^5 and 0 <= fruits[i] < fruits.length?

Naive Approach

The brute-force solution would be to iterate through all possible subarrays of the fruits array and check if each subarray satisfies the condition of having at most two types of fruits. We keep track of the maximum length of such a subarray. This involves nested loops, leading to a time complexity of O(n^2).

def max_fruits_naive(fruits):
    max_len = 0
    for i in range(len(fruits)):
        for j in range(i, len(fruits)):
            subarray = fruits[i:j+1]
            unique_fruits = set(subarray)
            if len(unique_fruits) <= 2:
                max_len = max(max_len, len(subarray))
    return max_len

# Example usage:
fruits = [1, 2, 3, 2, 2]
print(max_fruits_naive(fruits))  # Output: 4

Optimal Approach: Sliding Window

The optimal approach uses the sliding window technique to achieve a time complexity of O(n). We maintain a window with at most two types of fruits. We expand the window to the right until we have more than two types. Then, we shrink the window from the left until we have at most two types again. We keep track of the maximum window size.

def max_fruits(fruits):
    max_len = 0
    fruit_count = {}
    left = 0

    for right in range(len(fruits)):
        # Expand the window
        if fruits[right] not in fruit_count:
            fruit_count[fruits[right]] = 0
        fruit_count[fruits[right]] += 1

        # Shrink the window if more than two types of fruits
        while len(fruit_count) > 2:
            fruit_count[fruits[left]] -= 1
            if fruit_count[fruits[left]] == 0:
                del fruit_count[fruits[left]]
            left += 1

        # Update the maximum length
        max_len = max(max_len, right - left + 1)

    return max_len

# Example usage:
fruits = [1, 2, 3, 2, 2]
print(max_fruits(fruits))  # Output: 4

Data Structures

• fruits: An array of integers representing the type of fruit each tree produces.
• fruit_count: A dictionary to store the count of each type of fruit within the current window.
• left: An integer representing the left boundary of the sliding window.
• right: An integer representing the right boundary of the sliding window.

Big O Runtime Analysis

The optimal solution with the sliding window technique has a time complexity of O(n), where n is the number of trees (length of the fruits array).

• The for loop iterates through each element of the fruits array once, which takes O(n) time.
• Inside the loop, the operations of adding to and removing from the fruit_count dictionary take O(1) on average.
• The while loop also iterates, but in total, the left pointer can only move up to n times, so the while loop also contributes O(n) in the worst case.
• Therefore, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Big O Space Usage Analysis

The space complexity of the optimal solution is O(1) because the fruit_count dictionary can hold at most three key-value pairs (since the while loop ensures that no more than two types of fruits are in the window at any time). Therefore, the space used by the dictionary is constant and does not depend on the input size.

Edge Cases

1. Empty Array:

   • If the input fruits array is empty, the algorithm should return 0 because no fruits can be picked.

2. Single Type of Fruit:

   • If all trees have the same type of fruit, the algorithm should return the length of the fruits array because all fruits can be picked.

3. Two Types of Fruits:

   • If there are only two types of fruits, the algorithm should return the length of the fruits array because all fruits can be picked.

4. Fruits at the Beginning:

   • If the longest sequence of pickable fruits starts at the beginning of the array, the algorithm should correctly identify the maximum length.

5. Fruits at the End:

   • If the longest sequence of pickable fruits ends at the end of the array, the algorithm should correctly identify the maximum length.

6. All unique fruits:

   • If there are all unique fruits, we need to make sure the window slides as expected.