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

Array Segment Tree Ordered Set

Prompt

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i^th type of fruit, and baskets[j] represents the capacity of the j^th 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 <= 10⁵
1 <= fruits[i], baskets[i] <= 10⁹

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

Initialize a counter for unplaced fruits, unplacedCount, to 0.
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.
Iterate through each fruit in the fruits array from left to right.
For each fruit, start a search for a suitable basket. Initialize a flag, placed, to false.
Iterate through the baskets array from left to right (index j from 0 to n-1).
In the inner loop, check if the current basket j is available (!basketUsed[j]) and if its capacity is sufficient (baskets[j] >= fruit).
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.
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.
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.

1class Solution {2    public int unplacedFruits(int[] fruits, int[] baskets) {3        int n = fruits.length;4        boolean[] basketUsed = new boolean[n];5        int unplacedCount = 0;6 7        // Iterate through each fruit from left to right8        for (int fruit : fruits) {9            boolean placed = false;10            // Find the leftmost available basket with sufficient capacity11            for (int j = 0; j < n; j++) {12                if (!basketUsed[j] && baskets[j] >= fruit) {13                    basketUsed[j] = true;14                    placed = true;15                    break; // Move to the next fruit16                }17            }18            // If no suitable basket was found19            if (!placed) {20                unplacedCount++;21            }22        }23        return unplacedCount;24    }25}

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).

The bottleneck in the brute-force approach is the O(n) search for a suitable basket for each fruit. We can optimize this search to O(log n) using a segment tree. A segment tree is built over the baskets array, with each node storing the maximum capacity in its corresponding index range. For each fruit, we can query this tree to efficiently find the leftmost available basket with sufficient capacity. Once a basket is used, we update the tree by setting its capacity to 0, effectively removing it from future consideration.

Algorithm

Segment Tree Structure: Design a segment tree where each node represents a range of basket indices and stores the maximum capacity within that range.
Build: Construct the segment tree from the baskets array. This takes O(n) time.
Query for Leftmost Basket: Implement a query function findLeftmost(requiredCapacity) that finds the smallest index j such that baskets[j] >= requiredCapacity. This function works by recursively traversing the tree:
- If the maximum capacity in a node's range is less than requiredCapacity, there's no answer in this branch.
- It always prioritizes searching the left child's subtree to find the smallest possible index.
- If the left subtree yields no result, it searches the right subtree.
- This query operation takes O(log n) time.
Update: Implement an update(index, value) function that changes the value at a specific index in the base array and propagates the change up the tree. This is used to "remove" a basket once it's used by setting its capacity to 0. This takes O(log n) time.
Main Logic:
- Initialize unplacedCount = 0.
- Build the segment tree on the baskets array.
- Iterate through each fruit in the fruits array.
- For each fruit, call findLeftmost(fruit) to get the index of the best basket.
- If the query returns a valid index, call update(index, 0) to mark the basket as used.
- If the query returns -1 (no suitable basket), increment unplacedCount.
Return unplacedCount.

Walkthrough

This approach uses a segment tree to accelerate the search for the leftmost suitable basket. The tree is built on the indices of the baskets array. Each node in the tree stores the maximum capacity available in the range of indices it covers. This allows us to quickly discard ranges where no basket can hold the current fruit and to efficiently find the leftmost valid option.

1class Solution {2    private int[] tree;3    private int n;4 5    public int unplacedFruits(int[] fruits, int[] baskets) {6        this.n = baskets.length;7        this.tree = new int[4 * n];8        build(baskets, 0, 0, n - 1);9 10        int unplacedCount = 0;11        for (int fruit : fruits) {12            int basketIndex = query(0, 0, n - 1, fruit);13 14            if (basketIndex == -1) {15                unplacedCount++;16            } else {17                // Mark the basket as used by setting its capacity to 018                // (since original capacities are >= 1)19                update(0, 0, n - 1, basketIndex, 0);20            }21        }22        return unplacedCount;23    }24 25    private void build(int[] arr, int node, int start, int end) {26        if (start == end) {27            tree[node] = arr[start];28        } else {29            int mid = start + (end - start) / 2;30            build(arr, 2 * node + 1, start, mid);31            build(arr, 2 * node + 2, mid + 1, end);32            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);33        }34    }35 36    private void update(int node, int start, int end, int idx, int val) {37        if (start == end) {38            tree[node] = val;39        } else {40            int mid = start + (end - start) / 2;41            if (start <= idx && idx <= mid) {42                update(2 * node + 1, start, mid, idx, val);43            } else {44                update(2 * node + 2, mid + 1, end, idx, val);45            }46            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);47        }48    }49 50    private int query(int node, int start, int end, int requiredCapacity) {51        if (tree[node] < requiredCapacity) {52            return -1;53        }54        if (start == end) {55            return start;56        }57 58        int mid = start + (end - start) / 2;59        60        // Prioritize left child for the "leftmost" index61        int result = query(2 * node + 1, start, mid, requiredCapacity);62        63        if (result != -1) {64            return result;65        }66        67        // If left subtree has no answer, check right subtree68        return query(2 * node + 2, mid + 1, end, requiredCapacity);69    }70}

Complexity

Time

O(n log n) - Building the segment tree takes O(n). For each of the `n` fruits, we perform one query and one update, both of which take O(log n) time.

Space

O(n) - The segment tree requires an array of size approximately 4n to store its nodes.

Trade-offs

Pros

Highly efficient with a time complexity of O(n log n).
Scales well for large inputs as specified in the constraints.

Cons

The implementation is significantly more complex than the brute-force approach.
Requires a good understanding of segment trees.

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 problem