Fruits Into Baskets III

Problem Statement

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: fruits = [4,2,5], baskets = [3,5,4] → Output: 1
Example 2: fruits = [3,6,1], baskets = [6,4,7] → Output: 0

Approach 1: Brute Force Approach

Explanation: For each fruit, iterate through the baskets to find the leftmost one with sufficient capacity. Mark the basket as used (set to -1) after placing the fruit. Count the number of baskets that remain unused, which corresponds to unplaced fruits.

Time Complexity: O(n²) for iterating through baskets for each fruit.

Space Complexity: O(1) excluding input storage.

for i in range(0, n):
    for j in range(0, n):
        if baskets[j] >= fruits[i]:
            baskets[j] = -1
            break
cnt = 0
for j in range(0, n):
    if baskets[j] != -1:
        cnt += 1
return cnt

Approach 2: Segment Tree

Explanation: Build a segment tree to store the maximum basket capacity in each range. For each fruit, query the segment tree to find the leftmost basket with sufficient capacity. If found, mark the basket as used (set to -1) and update the tree. Count fruits that cannot be placed.

Time Complexity: O(n log n) for building the segment tree and O(n log n) for n queries.

Space Complexity: O(n) for the segment tree.

function build(i, l, r, baskets):
    if l == r:
        segTree[i] = baskets[l]
        return
    mid = l + (r - l) / 2
    build(2*i+1, l, mid, baskets)
    build(2*i+2, mid+1, r, baskets)
    segTree[i] = max(segTree[2*i+1], segTree[2*i+2])

function segQuery(i, l, r, fruit, baskets):
    if segTree[i] < fruit:
        return false
    if l == r:
        segTree[i] = -1
        return true
    mid = l + (r - l) / 2
    placed = false
    if segTree[2*i+1] >= fruit:
        placed = segQuery(2*i+1, l, mid, fruit, baskets)
    else:
        placed = segQuery(2*i+2, mid+1, r, fruit, baskets)
    segTree[i] = max(segTree[2*i+1], segTree[2*i+2])
    return placed

unplaced = 0
segTree = array of size 4*n initialized to -1
build(0, 0, n-1, baskets)
for each fruit in fruits:
    if not segQuery(0, 0, n-1, fruit, baskets):
        unplaced += 1
return unplaced

Solve on LeetCode