# Fruits Into Baskets III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fruits-into-baskets-iii)
Canonical: https://scaleengineer.com/dsa/problems/fruits-into-baskets-iii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree, Ordered Set
---
## Problem
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:**

**Input:** fruits = \[4,2,5\], baskets = \[3,5,4\]

**Output:** 1

**Explanation:**

* `fruits[0] = 4` is placed in `baskets[1] = 5`.
* `fruits[1] = 2` is placed in `baskets[0] = 3`.
* `fruits[2] = 5` cannot be placed in `baskets[2] = 4`.

Since one fruit type remains unplaced, we return 1.

**Example 2:**

**Input:** fruits = \[3,6,1\], baskets = \[6,4,7\]

**Output:** 0

**Explanation:**

* `fruits[0] = 3` is placed in `baskets[0] = 6`.
* `fruits[1] = 6` cannot be placed in `baskets[1] = 4` (insufficient capacity) but can be placed in the next available basket, `baskets[2] = 7`.
* `fruits[2] = 1` is placed in `baskets[1] = 4`.

Since all fruits are successfully placed, we return 0.

**Constraints:**

* `n == fruits.length == baskets.length`
* `1 <= n <= 105`
* `1 <= fruits[i], baskets[i] <= 109`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We iterate through each fruit one by one. For each fruit, we perform a linear scan through the baskets from left to right to find the first one that is not yet used and has enough capacity. We use a boolean array to keep track of which baskets have been taken.
**Time:** O(n^2) - For each of the `n` fruits, we may have to scan through all `n` baskets in the worst case. This leads to a nested loop structure. · **Space:** O(n) - We use a boolean array `basketUsed` of size `n` to keep track of the availability of baskets.
**Pros:** Simple to understand and implement.; Requires minimal extra space (only a boolean array).
**Cons:** The time complexity of O(n^2) is inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs (n up to 10^5).
### Explanation
The brute-force method follows the problem's rules exactly as stated without any complex data structures. We loop through every fruit, and for each fruit, we loop through every basket to find a match. This results in a nested loop structure.

```java
class Solution {
    public int unplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        boolean[] basketUsed = new boolean[n];
        int unplacedCount = 0;

        // Iterate through each fruit from left to right
        for (int fruit : fruits) {
            boolean placed = false;
            // Find the leftmost available basket with sufficient capacity
            for (int j = 0; j < n; j++) {
                if (!basketUsed[j] && baskets[j] >= fruit) {
                    basketUsed[j] = true;
                    placed = true;
                    break; // Move to the next fruit
                }
            }
            // If no suitable basket was found
            if (!placed) {
                unplacedCount++;
            }
        }
        return unplacedCount;
    }
}
```
### Algorithm
1. Initialize a counter for unplaced fruits, `unplacedCount`, to 0.
2. Create a boolean array, `basketUsed`, of the same size as `baskets`, and initialize all its elements to `false`. This array will track which baskets have been used.
3. Iterate through each `fruit` in the `fruits` array from left to right.
4. For each `fruit`, start a search for a suitable basket. Initialize a flag, `placed`, to `false`.
5. Iterate through the `baskets` array from left to right (index `j` from 0 to `n-1`).
6. In the inner loop, check if the current basket `j` is available (`!basketUsed[j]`) and if its capacity is sufficient (`baskets[j] >= fruit`).
7. If both conditions are met, you have found the leftmost available basket. Mark it as used by setting `basketUsed[j] = true`, set `placed = true`, and break the inner loop to proceed to the next fruit.
8. After the inner loop finishes, if the `placed` flag is still `false`, it means no suitable basket was found for the current fruit. Increment `unplacedCount`.
9. After iterating through all the fruits, return `unplacedCount`.

## Optimized Search with a Segment Tree
The bottleneck in the brute-force approach is the O(n) search for a suitable basket for each fruit. We can optimize this search to O(log n) using a segment tree. A segment tree is built over the `baskets` array, with each node storing the maximum capacity in its corresponding index range. For each fruit, we can query this tree to efficiently find the leftmost available basket with sufficient capacity. Once a basket is used, we update the tree by setting its capacity to 0, effectively removing it from future consideration.
**Time:** O(n log n) - Building the segment tree takes O(n). For each of the `n` fruits, we perform one query and one update, both of which take O(log n) time. · **Space:** O(n) - The segment tree requires an array of size approximately 4n to store its nodes.
**Pros:** Highly efficient with a time complexity of O(n log n).; Scales well for large inputs as specified in the constraints.
**Cons:** The implementation is significantly more complex than the brute-force approach.; Requires a good understanding of segment trees.
### Explanation
This approach uses a segment tree to accelerate the search for the leftmost suitable basket. The tree is built on the indices of the `baskets` array. Each node in the tree stores the maximum capacity available in the range of indices it covers. This allows us to quickly discard ranges where no basket can hold the current fruit and to efficiently find the leftmost valid option.

```java
class Solution {
    private int[] tree;
    private int n;

    public int unplacedFruits(int[] fruits, int[] baskets) {
        this.n = baskets.length;
        this.tree = new int[4 * n];
        build(baskets, 0, 0, n - 1);

        int unplacedCount = 0;
        for (int fruit : fruits) {
            int basketIndex = query(0, 0, n - 1, fruit);

            if (basketIndex == -1) {
                unplacedCount++;
            } else {
                // Mark the basket as used by setting its capacity to 0
                // (since original capacities are >= 1)
                update(0, 0, n - 1, basketIndex, 0);
            }
        }
        return unplacedCount;
    }

    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = start + (end - start) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = start + (end - start) / 2;
            if (start <= idx && idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    private int query(int node, int start, int end, int requiredCapacity) {
        if (tree[node] < requiredCapacity) {
            return -1;
        }
        if (start == end) {
            return start;
        }

        int mid = start + (end - start) / 2;
        
        // Prioritize left child for the "leftmost" index
        int result = query(2 * node + 1, start, mid, requiredCapacity);
        
        if (result != -1) {
            return result;
        }
        
        // If left subtree has no answer, check right subtree
        return query(2 * node + 2, mid + 1, end, requiredCapacity);
    }
}
```
### Algorithm
1. **Segment Tree Structure**: Design a segment tree where each node represents a range of basket indices and stores the maximum capacity within that range.
2. **Build**: Construct the segment tree from the `baskets` array. This takes O(n) time.
3. **Query for Leftmost Basket**: Implement a query function `findLeftmost(requiredCapacity)` that finds the smallest index `j` such that `baskets[j] >= requiredCapacity`. This function works by recursively traversing the tree:
    - If the maximum capacity in a node's range is less than `requiredCapacity`, there's no answer in this branch.
    - It always prioritizes searching the left child's subtree to find the smallest possible index.
    - If the left subtree yields no result, it searches the right subtree.
    - This query operation takes O(log n) time.
4. **Update**: Implement an `update(index, value)` function that changes the value at a specific index in the base array and propagates the change up the tree. This is used to "remove" a basket once it's used by setting its capacity to 0. This takes O(log n) time.
5. **Main Logic**:
    - Initialize `unplacedCount = 0`.
    - Build the segment tree on the `baskets` array.
    - Iterate through each `fruit` in the `fruits` array.
    - For each `fruit`, call `findLeftmost(fruit)` to get the index of the best basket.
    - If the query returns a valid index, call `update(index, 0)` to mark the basket as used.
    - If the query returns -1 (no suitable basket), increment `unplacedCount`.
6. Return `unplacedCount`.