Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

To find the leftmost usable basket quickly, we need to know whether an entire range contains any basket large enough. A segment tree storing each range's maximum remaining capacity answers that question and lets the search prefer the left half.

Approach

Build the segment tree over basket capacities. Process fruit quantities in their given order. During a search, reject a node immediately if its maximum is smaller than the current quantity. At a leaf that can hold the fruit, mark its capacity as unavailable and return its index.

At an internal node, search the left child first and search the right child only if the left fails. After a placement, recompute maxima on the path back up. Count the fruit as unplaced if the root search returns failure.

Left-first descent guarantees the required earliest eligible index, and range maxima let impossible branches be skipped immediately. Marking a used leaf below every positive fruit quantity prevents reuse while preserving the original order of all other baskets.

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        b = len(baskets)
        size = 4 * b
        seg = [0] * size

        def build(node, l, r):
            if l == r:
                seg[node] = baskets[l]
                return
            mid = (l + r) // 2
            build(node * 2, l, mid)
            build(node * 2 + 1, mid + 1, r)
            seg[node] = max(seg[node * 2], seg[node * 2 + 1])

        build(1, 0, b - 1)

        def find(node, l, r, fruit):
            if fruit > seg[node]:
                return -1 # failure base case
            if l == r:
                # success base case
                seg[node] = -1
                return l

            mid = (l + r) // 2
            candidate = find(node * 2, l, mid, fruit) # first we go left
            if candidate == -1:
                candidate = find(node * 2 + 1, mid + 1, r, fruit) # if no candidate, go right
            seg[node] = max(seg[node * 2], seg[node * 2 + 1])
            return candidate

        res = 0
        for fruit in fruits:
            if find(1, 0, b - 1, fruit) == -1:
                res += 1

        return res

Complexity analysis

Let f = fruits.length and b = baskets.length. Time: O(b + f log b). Auxiliary space: O(b).