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 III

Number: 3791

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two arrays, fruits and baskets, each of length n, where fruits[i] is the quantity of the ith type of fruit and baskets[j] is the capacity of the jth basket, assign each fruit to the leftmost available basket (in order) that has a capacity greater than or equal to the fruit’s quantity. Each basket can only hold one fruit type. If no such basket exists for a fruit type, the fruit remains unplaced. Return the total count of unplaced fruit types.

Key Insights

  • Use a greedy two-pointer approach to simulate the assignment from left to right.
  • A pointer for baskets is used to track the next available basket.
  • For each fruit, move the basket pointer until you find a basket with capacity >= fruit’s quantity.
  • If a basket is found, assign the fruit and move the pointer; if not, count the fruit as unplaced.
  • The problem leverages the given order in both arrays, eliminating the need for sorting.

Space and Time Complexity

Time Complexity: O(n) — each fruit and basket is processed at most once. Space Complexity: O(1) — only constant extra space is used aside from the input arrays.

Solution

We use a two-pointer technique to simulate the allocation of fruits into baskets in the given order. One pointer iterates through the fruits and another pointer tracks the available baskets. For each fruit, we advance the basket pointer until we find a basket that can accommodate that fruit (i.e., the basket's capacity is greater than or equal to the fruit's quantity). If a suitable basket is found, we assign the fruit to that basket and move to the next basket. If no basket with sufficient capacity is found, the fruit remains unplaced. Finally, we count and return the number of unplaced fruits.

Code Solutions

def fruitsIntoBaskets(fruits, baskets):
    n = len(fruits)
    basket_index = 0  # pointer to current basket available for assignment
    unplaced = 0  # count of fruits that are unplaced

    # Iterate over each fruit type in order
    for fruit in fruits:
        # Find the leftmost basket with capacity >= fruit quantity
        while basket_index < n and baskets[basket_index] < fruit:
            basket_index += 1
        if basket_index < n:
            # Basket found: assign fruit and move to the next basket
            basket_index += 1
        else:
            # No basket available: fruit remains unplaced
            unplaced += 1
    return unplaced

# Example usage:
if __name__ == "__main__":
    fruits = [4, 2, 5]
    baskets = [3, 5, 4]
    print(fruitsIntoBaskets(fruits, baskets))  # Expected output: 1
← Back to All Questions