# Fruits Into Baskets II
**Difficulty:** EASY
[External](https://leetcode.com/problems/fruits-into-baskets-ii)
Canonical: https://scaleengineer.com/dsa/problems/fruits-into-baskets-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree
---
## 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 <= 100`
* `1 <= fruits[i], baskets[i] <= 1000`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. We iterate through each fruit type and, for each one, we perform a linear scan through the baskets from left to right to find the first available basket with sufficient capacity.
**Time:** O(n^2), where `n` is the number of fruits. The nested loops lead to a quadratic time complexity, as for each of the `n` fruits, we might scan up to `n` baskets in the worst case. · **Space:** O(n), where `n` is the number of baskets. This is for the `usedBaskets` boolean array.
**Pros:** Simple to understand and implement.; Directly models the logic from the problem statement.; Efficient enough for the given constraints where `n <= 100`.
**Cons:** The O(n^2) time complexity can be slow if the input size `n` is very large.
### Explanation
We use a boolean array, `usedBaskets`, to keep track of which baskets have already been assigned a fruit type.

For each fruit `f` from the `fruits` array:
1. We search for a suitable basket by iterating through the `baskets` array from index 0 to `n-1`.
2. The first basket `j` we encounter that is not yet used (`usedBaskets[j]` is false) and has enough capacity (`baskets[j] >= f`) is chosen.
3. We mark this basket as used by setting `usedBaskets[j] = true` and move on to the next fruit.
4. If we iterate through all the baskets and don't find a suitable one for the current fruit, we count it as unplaced.

This process is repeated for all fruit types. The total count of unplaced fruits is the final answer.

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

        for (int fruit : fruits) {
            for (int j = 0; j < n; j++) {
                if (!usedBaskets[j] && baskets[j] >= fruit) {
                    usedBaskets[j] = true;
                    placedCount++;
                    break; // Found the leftmost basket, move to the next fruit
                }
            }
        }

        return n - placedCount;
    }
}
```
### Algorithm
- Initialize a boolean array `usedBaskets` of size `n` to all `false` to track basket availability.
- Initialize `placedCount = 0`.
- Iterate through each `fruit` in the `fruits` array from left to right.
- For each `fruit`, start an inner loop to iterate through the `baskets` array from index `j = 0` to `n-1`.
- Inside the inner loop, check if the current basket `j` is not used (`!usedBaskets[j]`) and has sufficient capacity (`baskets[j] >= fruit`).
- If both conditions are met, it means we've found the leftmost available basket. Mark it as used (`usedBaskets[j] = true`), increment `placedCount`, and `break` the inner loop to proceed to the next fruit.
- After iterating through all fruits, the number of unplaced fruits is `n - placedCount`.

## Optimized Search with Segment Tree
To improve upon the O(n^2) complexity, we can optimize the search for a suitable basket. The bottleneck in the brute-force approach is the linear scan for each fruit. We can use a segment tree data structure to find the leftmost available basket with sufficient capacity in logarithmic time.
**Time:** O(n log n). Building the 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), where `n` is the number of baskets. The segment tree requires an auxiliary array of size approximately `4n`.
**Pros:** Highly efficient with a time complexity of O(n log n).; Scales well for larger input sizes beyond the problem's constraints.; Demonstrates the use of advanced data structures to optimize search problems.
**Cons:** Significantly more complex to implement and debug compared to the brute-force approach.; The overhead of the segment tree might make it slightly slower than the simple O(n^2) solution for the small constraints of this problem (`n <= 100`).
### Explanation
A segment tree is built over the `baskets` array. Each node in the tree stores the maximum capacity within its corresponding index range.

When we need to place a fruit `f`, we query the segment tree:
1. **Query:** We search for the leftmost index `j` such that `baskets[j] >= f`. The query traverses the tree from the root, always prioritizing the left child (which corresponds to smaller indices) to satisfy the "leftmost" requirement. This search operation takes O(log n) time.
2. **Update:** If a suitable basket at index `j` is found, we "remove" it to prevent it from being used again. This is done by updating its value in the segment tree to a value that will never satisfy the condition (e.g., 0, since capacities are positive). This update also takes O(log n) time.

If the query returns no suitable basket, the fruit is marked as unplaced. By replacing the O(n) linear scan with an O(log n) segment tree query and update, we reduce the overall time complexity.

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

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

    // Update the tree after using a basket
    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, start, mid, idx, val);
            } else {
                update(2 * node + 1, mid + 1, end, idx, val);
            }
            tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
        }
    }

    // Query for the leftmost basket with capacity >= fruit
    private int query(int node, int start, int end, int fruit) {
        if (tree[node] < fruit) {
            return -1; // No basket in this range has enough capacity
        }
        if (start == end) {
            return start; // Leaf node, found a suitable basket
        }

        int mid = start + (end - start) / 2;
        
        // Prioritize left child for "leftmost"
        if (tree[2 * node] >= fruit) {
            int res = query(2 * node, start, mid, fruit);
            if (res != -1) return res;
        }
        
        // If left child has no suitable basket, check right child
        return query(2 * node + 1, mid + 1, end, fruit);
    }

    public int unplacedFruits(int[] fruits, int[] baskets) {
        this.n = baskets.length;
        this.baskets = baskets;
        this.tree = new int[4 * n];
        
        build(1, 0, n - 1);
        
        int unplacedCount = 0;
        for (int fruit : fruits) {
            int basketIndex = query(1, 0, n - 1, fruit);
            if (basketIndex == -1) {
                unplacedCount++;
            } else {
                // Mark basket as used by setting its capacity to 0
                update(1, 0, n - 1, basketIndex, 0);
            }
        }
        
        return unplacedCount;
    }
}
```
### Algorithm
- Define a segment tree data structure where each node stores the maximum value in its corresponding index range.
- **Build:** Construct the segment tree from the `baskets` array. This takes `O(n)` time.
- Initialize `unplacedCount = 0`.
- Iterate through each `fruit` in the `fruits` array.
- **Query:** For each `fruit`, query the segment tree to find the leftmost index `j` where the capacity is sufficient (`>= fruit`). This query must be designed to explore the left side of the tree first to respect the 'leftmost' rule. This operation takes `O(log n)`.
- **Update:** If a basket at index `j` is found, update the tree by setting the capacity at `j` to 0 (or another value that won't be chosen again). This prevents the basket from being used for subsequent fruits and takes `O(log n)`.
- If the query finds no suitable basket, increment `unplacedCount`.
- Return the final `unplacedCount`.

# Solutions
### Java

```java
class Solution {
public
  int numOfUnplacedFruits(int[] fruits, int[] baskets) {
    int n = fruits.length;
    boolean[] vis = new boolean[n];
    int ans = n;
    for (int x : fruits) {
      for (int i = 0; i < n; ++i) {
        if (baskets[i] >= x && !vis[i]) {
          vis[i] = true;
          --ans;
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numOfUnplacedFruits(vector<int> &fruits, vector<int> &baskets) {
    int n = fruits.size();
    vector<bool> vis(n);
    int ans = n;
    for (int x : fruits) {
      for (int i = 0; i < n; ++i) {
        if (baskets[i] >= x && !vis[i]) {
          vis[i] = true;
          --ans;
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int: n = len(fruits) vis = [False] * n ans = n for x in fruits: for i, y in enumerate(baskets): if y >= x and not vis[i]: vis[i] = True ans -= 1 break return ans

```