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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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 <= 10^5
  • 1 <= fruits[i], baskets[i] <= 10^9

Solution

Method 1 – Square Root Decomposition with Block Optimization

Intuition

This problem extends the concept from Fruits Into Baskets II, but with significantly larger input constraints that make direct simulation inefficient. The key insight is to use square root decomposition to optimize the search process while maintaining the leftmost placement requirement.

We partition the baskets array into √n blocks of approximately equal size. Within each block, we maintain sorted order and track the maximum capacity. This allows us to quickly skip entire blocks that cannot accommodate a fruit, while still preserving the leftmost placement property within viable blocks.

Approach

  1. Block Partitioning: Divide the baskets array into √n blocks, each containing approximately √n baskets
  2. Block Preprocessing: For each block, store baskets as (capacity, original_index) pairs and sort them by capacity for efficient searching
  3. Fruit Placement Process: For each fruit in sequence:
    • Iterate through blocks from left to right
    • Block Filtering: If the maximum capacity in a block is less than the fruit’s requirement, skip the entire block
    • Intra-block Search: Within a viable block, find the basket with smallest original index that can accommodate the fruit
    • Basket Removal: Remove the selected basket from its block and continue to the next fruit
    • Unplaced Counting: If no suitable basket is found across all blocks, increment the unplaced counter
  4. Return the total count of unplaced fruits

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        int block_size = (int)ceil(sqrt(n));
        
        vector<vector<pair<int, int>>> blocks(block_size);
        
        // Distribute baskets into blocks
        for (int i = 0; i < n; i++) {
            int block_idx = i / block_size;
            blocks[block_idx].push_back({baskets[i], i});
        }
        
        // Sort each block by capacity
        for (auto& block : blocks) {
            sort(block.begin(), block.end());
        }
        
        int unplaced_count = 0;
        
        for (int fruit_quantity : fruits) {
            bool placed = false;
            
            for (auto& block : blocks) {
                if (block.empty()) continue;
                
                // Skip if max capacity in block is insufficient
                if (block.back().first < fruit_quantity) continue;
                
                // Find leftmost viable basket
                int best_idx = -1;
                int min_original_idx = INT_MAX;
                
                for (int i = 0; i < block.size(); i++) {
                    if (block[i].first >= fruit_quantity && block[i].second < min_original_idx) {
                        min_original_idx = block[i].second;
                        best_idx = i;
                    }
                }
                
                if (best_idx != -1) {
                    block.erase(block.begin() + best_idx);
                    placed = true;
                    break;
                }
            }
            
            if (!placed) unplaced_count++;
        }
        
        return unplaced_count;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import (
    "math"
)

func numOfUnplacedFruits(fruits []int, baskets []int) int {
    n := len(fruits)
    blockSize := int(math.Ceil(math.Sqrt(float64(n))))
    
    blocks := make([][][2]int, blockSize)
    
    // Distribute baskets into blocks
    for i, capacity := range baskets {
        blockIdx := i / blockSize
        blocks[blockIdx] = append(blocks[blockIdx], [2]int{capacity, i})
    }
    
    // Sort each block by capacity
    for i := range blocks {
        sort.Slice(blocks[i], func(a, b int) bool {
            return blocks[i][a][0] < blocks[i][b][0]
        })
    }
    
    unplacedCount := 0
    
    for _, fruitQuantity := range fruits {
        placed := false
        
        for i := range blocks {
            if len(blocks[i]) == 0 {
                continue
            }
            
            // Skip if max capacity insufficient
            lastIdx := len(blocks[i]) - 1
            if blocks[i][lastIdx][0] < fruitQuantity {
                continue
            }
            
            // Find leftmost viable basket
            bestIdx := -1
            minOriginalIdx := math.MaxInt32
            
            for j, basket := range blocks[i] {
                if basket[0] >= fruitQuantity && basket[1] < minOriginalIdx {
                    minOriginalIdx = basket[1]
                    bestIdx = j
                }
            }
            
            if bestIdx != -1 {
                // Remove the selected basket
                blocks[i] = append(blocks[i][:bestIdx], blocks[i][bestIdx+1:]...)
                placed = true
                break
            }
        }
        
        if !placed {
            unplacedCount++
        }
    }
    
    return unplacedCount
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        int blockSize = (int) Math.ceil(Math.sqrt(n));
        
        List<List<int[]>> blocks = new ArrayList<>();
        for (int i = 0; i < blockSize; i++) {
            blocks.add(new ArrayList<>());
        }
        
        // Distribute baskets into blocks
        for (int i = 0; i < n; i++) {
            int blockIdx = i / blockSize;
            blocks.get(blockIdx).add(new int[]{baskets[i], i});
        }
        
        // Sort each block by capacity
        for (List<int[]> block : blocks) {
            block.sort((a, b) -> Integer.compare(a[0], b[0]));
        }
        
        int unplacedCount = 0;
        
        for (int fruitQuantity : fruits) {
            boolean placed = false;
            
            for (List<int[]> block : blocks) {
                if (block.isEmpty()) continue;
                
                // Skip if max capacity insufficient
                if (block.get(block.size() - 1)[0] < fruitQuantity) continue;
                
                // Find leftmost viable basket
                int bestIdx = -1;
                int minOriginalIdx = Integer.MAX_VALUE;
                
                for (int i = 0; i < block.size(); i++) {
                    int[] basket = block.get(i);
                    if (basket[0] >= fruitQuantity && basket[1] < minOriginalIdx) {
                        minOriginalIdx = basket[1];
                        bestIdx = i;
                    }
                }
                
                if (bestIdx != -1) {
                    block.remove(bestIdx);
                    placed = true;
                    break;
                }
            }
            
            if (!placed) unplacedCount++;
        }
        
        return unplacedCount;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import kotlin.math.*

class Solution {
    fun numOfUnplacedFruits(fruits: IntArray, baskets: IntArray): Int {
        val n = fruits.size
        val blockSize = ceil(sqrt(n.toDouble())).toInt()
        
        val blocks = Array(blockSize) { mutableListOf<Pair<Int, Int>>() }
        
        // Distribute baskets into blocks
        for (i in baskets.indices) {
            val blockIdx = i / blockSize
            blocks[blockIdx].add(Pair(baskets[i], i))
        }
        
        // Sort each block by capacity
        for (block in blocks) {
            block.sortBy { it.first }
        }
        
        var unplacedCount = 0
        
        for (fruitQuantity in fruits) {
            var placed = false
            
            for (block in blocks) {
                if (block.isEmpty()) continue
                
                // Skip if max capacity insufficient
                if (block.last().first < fruitQuantity) continue
                
                // Find leftmost viable basket
                var bestIdx = -1
                var minOriginalIdx = Int.MAX_VALUE
                
                for (i in block.indices) {
                    val (capacity, originalIdx) = block[i]
                    if (capacity >= fruitQuantity && originalIdx < minOriginalIdx) {
                        minOriginalIdx = originalIdx
                        bestIdx = i
                    }
                }
                
                if (bestIdx != -1) {
                    block.removeAt(bestIdx)
                    placed = true
                    break
                }
            }
            
            if (!placed) unplacedCount++
        }
        
        return unplacedCount
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

from math import ceil, sqrt

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        
        # Square root decomposition: create √n blocks
        block_size = int(ceil(sqrt(n)))
        blocks = [[] for _ in range(block_size)]
        
        # Distribute baskets into blocks based on their original indices
        for original_idx, basket_capacity in enumerate(baskets):
            block_idx = original_idx // block_size
            blocks[block_idx].append((basket_capacity, original_idx))
        
        # Sort each block by capacity to enable efficient searching
        # Last element in each block will have maximum capacity
        for block in blocks:
            block.sort()
        
        # Process fruits and attempt placement
        unplaced_count = 0
        
        for fruit_quantity in fruits:
            placed = False
            
            # Check blocks from left to right to maintain leftmost preference
            for block in blocks:
                # Skip empty blocks
                if not block:
                    continue
                
                # Quick check: if max capacity in block < fruit quantity, skip entire block
                max_capacity_in_block = block[-1][0]
                if max_capacity_in_block < fruit_quantity:
                    continue
                
                # Find the leftmost (smallest original index) basket that can fit the fruit
                viable_baskets = [(original_idx, capacity) 
                                for capacity, original_idx in block 
                                if capacity >= fruit_quantity]
                
                if viable_baskets:
                    # Select basket with minimum original index (leftmost)
                    chosen_original_idx, chosen_capacity = min(viable_baskets)
                    
                    # Remove the selected basket from the block
                    block.remove((chosen_capacity, chosen_original_idx))
                    placed = True
                    break
            
            # If no suitable basket found in any block
            if not placed:
                unplaced_count += 1
        
        return unplaced_count
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

impl Solution {
    pub fn num_of_unplaced_fruits(fruits: Vec<i32>, baskets: Vec<i32>) -> i32 {
        let n = fruits.len();
        let block_size = ((n as f64).sqrt().ceil()) as usize;
        
        let mut blocks: Vec<Vec<(i32, usize)>> = vec![Vec::new(); block_size];
        
        // Distribute baskets into blocks
        for (i, &capacity) in baskets.iter().enumerate() {
            let block_idx = i / block_size;
            blocks[block_idx].push((capacity, i));
        }
        
        // Sort each block by capacity
        for block in &mut blocks {
            block.sort_by_key(|&(capacity, _)| capacity);
        }
        
        let mut unplaced_count = 0;
        
        for &fruit_quantity in &fruits {
            let mut placed = false;
            
            for block in &mut blocks {
                if block.is_empty() {
                    continue;
                }
                
                // Skip if max capacity insufficient
                if block.last().unwrap().0 < fruit_quantity {
                    continue;
                }
                
                // Find leftmost viable basket
                let mut best_idx = None;
                let mut min_original_idx = usize::MAX;
                
                for (i, &(capacity, original_idx)) in block.iter().enumerate() {
                    if capacity >= fruit_quantity && original_idx < min_original_idx {
                        min_original_idx = original_idx;
                        best_idx = Some(i);
                    }
                }
                
                if let Some(idx) = best_idx {
                    block.remove(idx);
                    placed = true;
                    break;
                }
            }
            
            if !placed {
                unplaced_count += 1;
            }
        }
        
        unplaced_count
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
    const n = fruits.length;
    const blockSize = Math.ceil(Math.sqrt(n));
    
    const blocks: Array<Array<[number, number]>> = Array(blockSize).fill(null).map(() => []);
    
    // Distribute baskets into blocks
    for (let i = 0; i < n; i++) {
        const blockIdx = Math.floor(i / blockSize);
        blocks[blockIdx].push([baskets[i], i]);
    }
    
    // Sort each block by capacity
    for (const block of blocks) {
        block.sort((a, b) => a[0] - b[0]);
    }
    
    let unplacedCount = 0;
    
    for (const fruitQuantity of fruits) {
        let placed = false;
        
        for (const block of blocks) {
            if (block.length === 0) continue;
            
            // Skip if max capacity insufficient
            if (block[block.length - 1][0] < fruitQuantity) continue;
            
            // Find leftmost viable basket
            let bestIdx = -1;
            let minOriginalIdx = Number.MAX_SAFE_INTEGER;
            
            for (let i = 0; i < block.length; i++) {
                const [capacity, originalIdx] = block[i];
                if (capacity >= fruitQuantity && originalIdx < minOriginalIdx) {
                    minOriginalIdx = originalIdx;
                    bestIdx = i;
                }
            }
            
            if (bestIdx !== -1) {
                block.splice(bestIdx, 1);
                placed = true;
                break;
            }
        }
        
        if (!placed) unplacedCount++;
    }
    
    return unplacedCount;
}

Complexity

  • ⏰ Time complexity: O(n × √n) = O(n^(3/2)), where n is the length of the arrays. Processing each fruit requires traversing at most √n blocks, and within each viable block, we perform a linear search that takes O(√n) time in the worst case.
  • 🧺 Space complexity: O(√n), required to maintain the block structure. Each block stores at most √n baskets, and we have at most √n blocks.