Scale Engineer

Fruits Into Baskets III

Med
#3093Time: O(n^2) - For each of the `n` fruits, we may have to scan through all `n` baskets in the worst case. This leads to a nested loop structure.Space: O(n) - We use a boolean array `basketUsed` of size `n` to keep track of the availability of baskets.
Algorithms
Binary Search
Data structures
ArraySegment TreeOrdered Set

Prompt

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.

 

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

  • fruits[0] = 4 is placed in baskets[1] = 5.
  • fruits[1] = 2 is placed in baskets[0] = 3.
  • fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

  • fruits[0] = 3 is placed in baskets[0] = 6.
  • fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
  • fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

 

Constraints:

  • n == fruits.length == baskets.length
  • 1 <= n <= 105
  • 1 <= fruits[i], baskets[i] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through each fruit one by one. For each fruit, we perform a linear scan through the baskets from left to right to find the first one that is not yet used and has enough capacity. We use a boolean array to keep track of which baskets have been taken.

Algorithm

  1. Initialize a counter for unplaced fruits, unplacedCount, to 0.
  2. Create a boolean array, basketUsed, of the same size as baskets, and initialize all its elements to false. This array will track which baskets have been used.
  3. Iterate through each fruit in the fruits array from left to right.
  4. For each fruit, start a search for a suitable basket. Initialize a flag, placed, to false.
  5. Iterate through the baskets array from left to right (index j from 0 to n-1).
  6. In the inner loop, check if the current basket j is available (!basketUsed[j]) and if its capacity is sufficient (baskets[j] >= fruit).
  7. If both conditions are met, you have found the leftmost available basket. Mark it as used by setting basketUsed[j] = true, set placed = true, and break the inner loop to proceed to the next fruit.
  8. After the inner loop finishes, if the placed flag is still false, it means no suitable basket was found for the current fruit. Increment unplacedCount.
  9. After iterating through all the fruits, return unplacedCount.

Walkthrough

The brute-force method follows the problem's rules exactly as stated without any complex data structures. We loop through every fruit, and for each fruit, we loop through every basket to find a match. This results in a nested loop structure.

class Solution {    public int unplacedFruits(int[] fruits, int[] baskets) {        int n = fruits.length;        boolean[] basketUsed = new boolean[n];        int unplacedCount = 0;         // Iterate through each fruit from left to right        for (int fruit : fruits) {            boolean placed = false;            // Find the leftmost available basket with sufficient capacity            for (int j = 0; j < n; j++) {                if (!basketUsed[j] && baskets[j] >= fruit) {                    basketUsed[j] = true;                    placed = true;                    break; // Move to the next fruit                }            }            // If no suitable basket was found            if (!placed) {                unplacedCount++;            }        }        return unplacedCount;    }}

Complexity

Time

O(n^2) - For each of the `n` fruits, we may have to scan through all `n` baskets in the worst case. This leads to a nested loop structure.

Space

O(n) - We use a boolean array `basketUsed` of size `n` to keep track of the availability of baskets.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space (only a boolean array).

Cons

  • The time complexity of O(n^2) is inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs (n up to 10^5).

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem