Fruits Into Baskets III | Leetcode 3479

class Solution {
    vector<int> segTree;

    void buildSegTreeRMQ(vector<int>& baskets,int low,int high,int st_idx){
        if(low==high){
            segTree[st_idx] = baskets[low];
            return;
        }

        int mid = low + (high-low)/2;
        buildSegTreeRMQ(baskets,low,mid,2*st_idx);
        buildSegTreeRMQ(baskets,mid+1,high,2*st_idx+1);
        segTree[st_idx] = max(segTree[2*st_idx],segTree[2*st_idx+1]);
    }
    int findLeftmostBasket(const int& fruit,int low,int high,int st_idx){
        if(segTree[st_idx]<fruit)
            return -1;
        if(low==high){
            segTree[st_idx] = -1;
            return 1;//1 shows the basket was found
        }
        
        int val;
        int mid = low + (high-low)/2;
        if(segTree[2*st_idx]>=fruit)    val = findLeftmostBasket(fruit,low,mid,2*st_idx);
        else                            val = findLeftmostBasket(fruit,mid+1,high,2*st_idx+1);
        segTree[st_idx] = max(segTree[2*st_idx],segTree[2*st_idx+1]);
        return val;
    }
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        segTree = vector<int>(4*n+1);

        //Step-1: Build Segment Tree RMQ
        int st_idx = 1;
        buildSegTreeRMQ(baskets,0,n-1,st_idx);

        //Step-2: Query the leftmost basket to be used
        int count = 0;
        for(int i=0;i<n;++i){
            if(findLeftmostBasket(fruits[i],0,n-1,st_idx)==-1)
                count++;
        }
        return count;
    }
};
/*
// Java implementation
import java.util.*;

public class Solution {
    private int[] segTree;
    private int n;

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        n = baskets.length;
        // Segment tree size: 4*n is safe
        segTree = new int[4 * n];
        build(baskets, 0, n - 1, 1);

        int unplaced = 0;
        for (int fruit : fruits) {
            if (findAndUse(fruit, 0, n - 1, 1) == -1) {
                unplaced++;
            }
        }
        return unplaced;
    }

    // Build max‐segment‐tree over baskets[low..high], at node idx
    private void build(int[] baskets, int low, int high, int idx) {
        if (low == high) {
            segTree[idx] = baskets[low];
        } else {
            int mid = low + (high - low) / 2;
            build(baskets, low, mid, 2 * idx);
            build(baskets, mid + 1, high, 2 * idx + 1);
            segTree[idx] = Math.max(segTree[2 * idx], segTree[2 * idx + 1]);
        }
    }

    // Find leftmost position in [low..high] with segTree value ≥ fruit,
    // set it to –1, and update tree; return 1 if found, else –1
    private int findAndUse(int fruit, int low, int high, int idx) {
        if (segTree[idx] < fruit) {
            return -1;
        }
        if (low == high) {
            // Leaf: use this basket
            segTree[idx] = -1;
            return 1;
        }
        int mid = low + (high - low) / 2;
        int res;
        if (segTree[2 * idx] >= fruit) {
            res = findAndUse(fruit, low, mid, 2 * idx);
        } else {
            res = findAndUse(fruit, mid + 1, high, 2 * idx + 1);
        }
        // Update current node after child change
        segTree[idx] = Math.max(segTree[2 * idx], segTree[2 * idx + 1]);
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] fruits = {2, 3, 5, 1};
        int[] baskets = {3, 1, 4, 2};
        int result = sol.numOfUnplacedFruits(fruits, baskets);
        System.out.println("Unplaced fruits: " + result);
    }
}

# Python implementation
from typing import List

class Solution:
    def num_of_unplaced_fruits(self, fruits: List[int], baskets: List[int]) -> int:
        self.n = len(baskets)
        # 1-indexed segment tree array for simplicity
        self.seg = [0] * (4 * self.n)
        self._build(baskets, 0, self.n - 1, 1)

        unplaced = 0
        for f in fruits:
            if self._find_and_use(f, 0, self.n - 1, 1) == -1:
                unplaced += 1
        return unplaced

    def _build(self, baskets: List[int], low: int, high: int, idx: int):
        if low == high:
            self.seg[idx] = baskets[low]
        else:
            mid = (low + high) // 2
            self._build(baskets, low, mid, idx * 2)
            self._build(baskets, mid + 1, high, idx * 2 + 1)
            self.seg[idx] = max(self.seg[idx * 2], self.seg[idx * 2 + 1])

    def _find_and_use(self, fruit: int, low: int, high: int, idx: int) -> int:
        # If this segment cannot fit the fruit
        if self.seg[idx] < fruit:
            return -1
        # If we're at a leaf, use it
        if low == high:
            self.seg[idx] = -1
            return 1
        mid = (low + high) // 2
        if self.seg[idx * 2] >= fruit:
            res = self._find_and_use(fruit, low, mid, idx * 2)
        else:
            res = self._find_and_use(fruit, mid + 1, high, idx * 2 + 1)
        # Update this node after child has changed
        self.seg[idx] = max(self.seg[idx * 2], self.seg[idx * 2 + 1])
        return res

# Example usage
if __name__ == "__main__":
    fruits = [2, 3, 5, 1]
    baskets = [3, 1, 4, 2]
    sol = Solution()
    print("Unplaced fruits:", sol.num_of_unplaced_fruits(fruits, baskets))
*/

Thanks for your code.
It's very helpful to me.