We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Fruit Into Baskets

Number: 940

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Meta, Adobe, Walmart Labs

Problem Description

Given an array of integers representing fruit trees where each integer denotes the type of fruit produced, determine the maximum number of fruits that can be picked by starting at any tree and collecting exactly one fruit from each tree to the right, while only being allowed to hold two distinct types of fruits in your baskets.

Key Insights

  • Use a sliding window to maintain a contiguous subarray with at most two distinct fruit types.
  • A hash table (or dictionary) is used to count occurrences of fruit types in the current window.
  • Expand the window to include new fruits and shrink it from the left when more than two types are present.
  • This approach is similar to solving the "longest substring with at most K distinct characters" for K = 2.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the fruits array. Space Complexity: O(1), as the hash table stores at most 3 keys in worst-case scenarios (effectively bounded by 2 unique types).

Solution

We use a sliding window technique. By iterating through the fruits array with a right pointer, we update a hash table that tracks the count of each fruit type in the window. When the window contains more than two unique fruit types, we move the left pointer to reduce the window size until it becomes valid again (only two types remain). The maximum valid window size over all iterations gives the maximum number of fruits that can be picked.

Code Solutions

# Python solution for Fruit Into Baskets

def totalFruit(fruits):
    # Dictionary to track the count of each fruit type in the current window
    fruit_count = {}
    left = 0  # left index of our sliding window
    max_fruits = 0  # maximum number of fruits collected so far
    
    # Iterate over fruits with the index 'right'
    for right, fruit in enumerate(fruits):
        # Add/update the current fruit in the window
        fruit_count[fruit] = fruit_count.get(fruit, 0) + 1
        
        # If the window contains more than 2 distinct fruit types, shrink it from the left
        while len(fruit_count) > 2:
            fruit_count[fruits[left]] -= 1
            # If the count drops to 0, remove that fruit type from the dictionary
            if fruit_count[fruits[left]] == 0:
                del fruit_count[fruits[left]]
            left += 1
        
        # Update the maximum fruits picked
        max_fruits = max(max_fruits, right - left + 1)
    
    return max_fruits

# Example usage:
print(totalFruit([1, 2, 1]))  # Expected Output: 3
← Back to All Questions