Fruits Into Baskets II - Solution & Explanation

Problem Overview: You are given two arrays: fruits and baskets. Each fruit must be placed in the leftmost basket that has capacity greater than or equal to the fruit size. Every basket can hold only one fruit. If no valid basket exists, the fruit remains unplaced. The task is to count how many fruits cannot be placed.

Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)

The most direct strategy is to simulate the placement process exactly as described. Iterate through each fruit and scan the baskets from left to right. The first unused basket whose capacity is >= fruit gets assigned to that fruit, and the basket is marked as used. If the scan reaches the end without finding a valid basket, increment the unplaced fruit count. This approach works well for small input sizes and mirrors the problem statement closely. Since you simply iterate over arrays and track used baskets, the extra space stays constant.

Approach 2: Ordered Set / Balanced Structure (O(n log m) time, O(m) space)

Instead of scanning all baskets every time, maintain a structure that tracks available baskets. One option is an ordered structure that stores basket indices along with their capacities. For each fruit, you search for the earliest basket whose capacity satisfies the requirement and remove it from the set once used. This avoids repeatedly checking baskets that are already filled. The main benefit appears when the basket count grows large, because each lookup becomes logarithmic instead of linear. Problems involving placement with constraints like this often benefit from ordered containers.

Approach 3: Segment Tree for First Valid Basket (O(n log m) time, O(m) space)

A more algorithmic solution uses a segment tree built over the baskets array. Each node stores the maximum capacity in its range. For every fruit, query the tree to find the leftmost index where the stored maximum is at least the fruit size. Once found, update that position to zero (or negative infinity) to mark the basket as used. The segment tree allows you to skip entire ranges that cannot fit the fruit, making the search efficient. This technique is common in allocation problems where you must find the first position satisfying a constraint.

Conceptually, this problem combines simple array traversal with efficient searching techniques such as binary search structures or trees. The key insight is that the basket must be both unused and the leftmost valid position.

Recommended for interviews: Start with the simulation approach because it demonstrates clear understanding of the rules and edge cases. If the interviewer pushes for scalability, transition to the segment tree or ordered-set approach that reduces repeated scanning. Showing both the straightforward simulation and the optimized search structure signals strong problem‑solving depth.