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

Fruits Into Baskets II

Number: 3790

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

You are given two arrays of integers, fruits and baskets, both of length n. The value fruits[i] represents the quantity of the iᵗʰ type of fruit while baskets[j] represents the capacity of the jᵗʰ basket. Process the fruits in order from left to right by placing each fruit type in the leftmost available basket whose capacity is greater than or equal to that fruit’s quantity. Each basket can hold only one fruit type. If a fruit type cannot be placed in any basket, it remains unplaced. The task is to return the number of fruit types that remain unplaced after attempting to place all fruits.

Key Insights

  • Process fruits from left to right and for each fruit, scan the baskets in order (from the smallest index) to find the first basket that is:
    • Not already used, and
    • Has a capacity greater than or equal to the quantity of that fruit.
  • Mark a basket as used once a fruit is placed.
  • If no available basket meets the requirement for a fruit, count that fruit as unplaced.
  • Due to the problem constraints (n <= 100), a simulated O(n²) solution is acceptable.

Space and Time Complexity

Time Complexity: O(n²) in the worst-case scenario, as for each fruit (n iterations) we may scan through up to n baskets.
Space Complexity: O(n) due to the additional array used to track basket usage.

Solution

We use a simple simulation with a boolean array to track which baskets are available (i.e., not used yet). For each fruit in the fruits array, we iterate over the baskets array from left to right. The moment we find a basket that is both available and has a capacity greater than or equal to the fruit’s quantity, we mark it as used. If no such basket is found for a fruit, we increment the count of unplaced fruits. This simulation directly follows the problem requirements of using the leftmost available basket.

Code Solutions

# Python Solution

def fruitsIntoBaskets(fruits, baskets):
    n = len(baskets)
    # Track usage of baskets, False means basket is available
    used = [False] * n
    unplaced = 0  # Count of unplaced fruits
    
    # Iterate over each fruit in order
    for fruit in fruits:
        placed = False
        # Check each basket from left to right
        for j in range(n):
            # If basket is available and has sufficient capacity
            if not used[j] and baskets[j] >= fruit:
                used[j] = True  # Mark basket as used
                placed = True
                break  # Stop at the leftmost available valid basket
        if not placed:
            unplaced += 1  # Fruit could not be placed in any basket
    return unplaced

# Example usage:
print(fruitsIntoBaskets([4, 2, 5], [3, 5, 4]))  # Expected output: 1
print(fruitsIntoBaskets([3, 6, 1], [6, 4, 7]))  # Expected output: 0
← Back to All Questions