Fruits Into Baskets III
MediumUpdated: Aug 6, 2025
Practice on:
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
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.length1 <= n <= 10^51 <= 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
- Block Partitioning: Divide the baskets array into √n blocks, each containing approximately √n baskets
- Block Preprocessing: For each block, store baskets as (capacity, original_index) pairs and sort them by capacity for efficient searching
- 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
- Return the total count of unplaced fruits
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.