The Question
Coding

Fruits Into Baskets II

You are given two integer arrays, fruits and baskets, both of size n. The array fruits[i] represents the quantity of the $i$-th fruit, and baskets[j] represents the capacity of the $j$-th basket. You must process the fruits in the order they appear in the fruits array. For each fruit, you want to place it into the first available basket (the one with the smallest index) that has a capacity greater than or equal to the fruit's quantity. Once a fruit is placed in a basket, that basket becomes unavailable for any other fruits. If a fruit cannot fit into any available basket, it remains unplaced. Return the total number of fruits that could not be placed in any basket. Constraints: - n == fruits.length == baskets.length - 1 <= n <= 10^5 - 1 <= fruits[i], baskets[i] <= 10^9
Java
Segment Tree
Questions & Insights

Clarifying Questions

What are the constraints on the input size $N$ and the values in the arrays?
Assumption: N can be up to 10^5. A brute-force O(N^2) solution would be too slow (10^{10} operations), so an O(N \log N) or O(N) approach is required.
Can a basket be reused?
Assumption: No. Each basket can hold exactly one type of fruit (the first one that fits), and once used, it is no longer available for subsequent fruits.
Does the order of fruits matter?
Assumption: Yes. We must process the fruits array in the order it is given (from index 0 to n-1).
What happens if multiple baskets can fit a fruit?
Assumption*: We must pick the first** available basket (the one with the smallest index) that meets the capacity requirement.

Thinking Process

Problem Characterization: This is a classic "find first element greater than or equal to X" problem with point updates (removing a basket).
Initial Intuition: A linear scan for each fruit results in O(N^2). To optimize, we need a data structure that can quickly tell us if any basket in a range has a value \ge X and locate the leftmost one.
Advanced Data Structure: A Segment Tree is ideal here. Each node in the tree will store the maximum value in its corresponding range of the baskets array.
Search Logic: To find the first index j such that baskets[j] >= fruit[i]:
Check if the root's maximum is less than the fruit's value. If so, no basket fits.
If the left child's maximum is \ge fruit value, recurse into the left child.
Otherwise, if the right child's maximum is \ge fruit value, recurse into the right child.
Update Logic: Once a basket at index j is used, update its value in the Segment Tree to -\infty (or 0, if all fruit values are positive) so it's never selected again.
Implementation Breakdown

Problem Set

Functional Requirements:
Process each fruit in the given order.
Find the first available basket with capacity \ge fruit amount.
Mark the basket as used.
Return the total count of fruits that could not be placed in any basket.
Constraints:
N \approx 10^5
fruits[i], baskets[i] \ge 1

Approach

Algorithm: Segment Tree Walk (Finding the first element satisfying a condition).
Data Structure: Max-Segment Tree.
Complexity:
Time: O(N \log N) to build the tree and process N queries/updates.
Space: O(N) to store the segment tree nodes.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: While a Segment Tree is O(N \log N), for very small N (e.g., N < 1000), a simple O(N^2) array scan might be faster due to cache locality and lower constant factors. However, the Segment Tree is the only robust solution for large N.
Binary Indexed Tree (BIT): A BIT is usually more space-efficient than a Segment Tree but is traditionally used for prefix sums. Finding the first element \ge X is more natural in a Segment Tree. Using BIT would require a binary search over the BIT, leading to O(N \log^2 N), which is slightly less efficient.
Parallelization: Building the Segment Tree can be parallelized easily (Divide and Conquer). However, the fruit processing must be sequential because the state of the baskets depends on the choices made for previous fruits.