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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Fruits Into Baskets II

Difficulty: Easy

Problem Description

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket. From left to right, place the fruits according to these rules: Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type. Each basket can hold only one type of fruit. If a fruit type cannot be placed in any basket, it remains unplaced. Return the number of fruit types that remain unplaced after all possible allocations are made.

Key Insights

  • Each fruit type can only be placed in one basket.
  • Baskets must be filled from left to right based on their capacity.
  • If a basket's capacity is insufficient for a fruit type, the algorithm must move to the next basket.
  • The goal is to maximize the placement of fruit types to minimize the number of unplaced types.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of fruit types and m is the number of baskets.
Space Complexity: O(1) as we are using a constant amount of additional space.

Solution

The algorithm iterates through each fruit type and tries to place it in the leftmost available basket with sufficient capacity. If a basket can hold the fruit, it is placed, and the algorithm moves to the next fruit. If no baskets can accommodate a fruit type, it is counted as unplaced. This approach uses a simple linear scan through the baskets for each fruit type.

Code Solutions

def fruits_into_baskets(fruits, baskets):
    unplaced_fruits = 0
    basket_used = [False] * len(baskets)  # Track which baskets are used

    for fruit in fruits:
        placed = False
        for j in range(len(baskets)):
            if not basket_used[j] and baskets[j] >= fruit:
                basket_used[j] = True  # Mark this basket as used
                placed = True
                break  # Move to the next fruit type
        if not placed:
            unplaced_fruits += 1  # Increment count of unplaced fruits

    return unplaced_fruits
← Back to All Questions