algoadvance

904. Fruit Into Baskets

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

You want to collect as much fruit as possible. However, the owner has a rule that you can only collect fruit from at most two different types of trees at any point. Given the array fruits, your task is to return the maximum number of fruits you can collect under the given rule.

Clarifying Questions

  1. Q: Can the array fruits be empty?
    • A: No, the array will contain at least one element.
  2. Q: Can we assume that all integers in the fruits array are non-negative?
    • A: Yes, all integers in the fruits array are non-negative.
  3. Q: Should the solution handle very large arrays efficiently?
    • A: Yes, the solution should be optimized for performance, particularly for large input arrays.
  4. Q: Are there any constraints on the values of the integers in the fruits array?
    • A: The integers simply represent different types of fruits and their actual values don’t matter beyond this representation.

Strategy

To solve this problem, we can utilize the sliding window technique. Here’s a step-by-step plan:

  1. Sliding Window Technique: This approach will help us efficiently keep track of the types of fruits and their counts within a dynamic window that moves across the array.

  2. Window Management:
    • Use two pointers start and end to represent the current window.
    • Use a dictionary to keep track of the count of each type of fruit within the window.
    • Expand the window by moving the end pointer and add the fruit at fruits[end] to the dictionary.
    • If the dictionary contains more than two types of fruits, shrink the window from the start side until we are back to having at most two types of fruits.
  3. Update the Maximum Count: Keep track of the maximum number of fruits collected as we expand and shrink the window.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the fruits array. Each fruit is added and removed from the dictionary at most once.

Code

def totalFruit(fruits):
    from collections import defaultdict
    
    start, max_fruits = 0, 0
    fruit_count = defaultdict(int)
    
    # Iterate over the end pointer
    for end in range(len(fruits)):
        fruit_count[fruits[end]] += 1
        
        # If we have more than 2 types of fruits, shrink the window from the start
        while len(fruit_count) > 2:
            fruit_count[fruits[start]] -= 1
            if fruit_count[fruits[start]] == 0:
                del fruit_count[fruits[start]]
            start += 1
        
        # Update the maximum number of fruits we have seen so far
        max_fruits = max(max_fruits, end - start + 1)
    
    return max_fruits

# Example Usage:
fruits = [1, 2, 1]
print(totalFruit(fruits))  # Output: 3

In this implementation:

Try our interview co-pilot at AlgoAdvance.com