Fruits Into Baskets III solution and explanation
Google
9 more videos on this problem
Fruits Into Baskets II & III | Segment Tree Concepts & Qns | Video 13 | Leetcode 3477 | 3479 | MIKcodestorywithMIK · 37:12 · 19K views
Fruits Into Baskets III | Leetcode 3479 | Segment Tree RMQTechdose · 22:42 · 8K views
3477 & 3479. Fruits Into Baskets III & II | Segment TreeAryan Mittal · 28:00 · 7K views
3479. Fruits Into Baskets III | Leetcode Daily - PythonLeetcode Daily · 7:29 · 1K views
Daily Leetcode #1954: Aug 06, 2025 - 3479. Fruits Into Baskets IIIProgramming Live with Larry · 51:42 · 870 views
Segment Tree Basics | Must DO | 3479. Fruits Into Baskets III | Leetcode Daily Challenge | 3 methodsEye on AI and DSA · 30:00 · 661 views
3479. Fruits Into Baskets III (Leetcode Medium)Programming Live with Larry · 42:52 · 608 views
Fruits Into Baskets III | LeetCode 3479 - Python (2 Solutions)impoldev · 23:22 · 500 views
Leetcode 3479. Fruits Into Baskets III | Segment Tree Explained with PythonStatLearn Tech · 19:04 · 499 views
Fruits Into Baskets III - LeetCode 3479 | Segment Tree Java SolutioncodingX krishna · 31:41 · 339 views
The 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] = 4is placed inbaskets[1] = 5.fruits[1] = 2is placed inbaskets[0] = 3.fruits[2] = 5cannot be placed inbaskets[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] = 3is placed inbaskets[0] = 6.fruits[1] = 6cannot be placed inbaskets[1] = 4(insufficient capacity) but can be placed in the next available basket,baskets[2] = 7.fruits[2] = 1is placed inbaskets[1] = 4.
Since all fruits are successfully placed, we return 0.
Constraints:
n == fruits.length == baskets.length1 <= n <= 1051 <= fruits[i], baskets[i] <= 109
Approach overview
Problem Overview: You are given an array of fruits where each value represents the size of a fruit, and an array of baskets where each value represents the basket capacity. Each fruit must go into the leftmost basket with capacity greater than or equal to the fruit size. A basket can only hold one fruit. If no such basket exists, the fruit cannot be placed. Return the number of fruits successfully placed.
Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)
Process fruits from left to right. For each fruit, iterate through the baskets array and pick the first unused basket whose capacity is greater than or equal to the fruit size. Mark the basket as used and continue. This approach directly simulates the rule but performs a linear scan for every fruit, resulting in O(n * m) time in the worst case. It works for small inputs but quickly becomes too slow when both arrays grow large.
Approach 2: Segment Tree + Binary Search (O((n + m) log m) time, O(m) space)
Build a segment tree over the baskets array where each node stores the maximum capacity in that range. For each fruit, query the tree to find the leftmost index whose capacity is at least the fruit size. This is done with a tree-guided binary search: if the left child’s maximum is large enough, recurse left; otherwise move to the right child. Once a basket is used, update that index in the tree to -inf (or 0) so it cannot be selected again. Each query and update costs O(log m), making the full algorithm O((n + m) log m). This handles large constraints efficiently.
Approach 3: Ordered Set / Balanced BST (O((n + m) log m) time, O(m) space)
Another option uses an ordered set or balanced BST storing basket indices grouped by capacity. As fruits arrive, you search for the first basket with capacity ≥ fruit size and remove it after assignment. This approach achieves similar complexity to the segment tree solution but depends on language support for ordered structures and efficient lower-bound queries.
Recommended for interviews: The segment tree approach is typically expected. The brute force simulation shows you understand the placement rule, but the optimized solution demonstrates knowledge of range queries and tree-guided searches. It cleanly finds the leftmost valid basket while supporting fast updates after each assignment.
Solution
We can use a segment tree to maintain the maximum basket capacity in an interval, which allows us to quickly find the first basket with capacity greater than or equal to the fruit quantity through binary search. If no such basket is found, we increment the answer by one; if found, we set that basket's capacity to zero, indicating that the basket has been used.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of baskets.
class SegmentTree:
__slots__ = ["nums", "tr"]
def __init__(self, nums):
self.nums = nums
n = len(nums)
self.tr = [0] * (n << 2)
self.build(1, 1, n)
def build(self, u, l, r):
if l == r:
self.tr[u] = self.nums[l - 1]
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)
def modify(self, u, l, r, i, v):
if l == r:
self.tr[u] = v
return
mid = (l + r) >> 1
if i <= mid:
self.modify(u << 1, l, mid, i, v)
else:
self.modify(u << 1 | 1, mid + 1, r, i, v)
self.pushup(u)
def query(self, u, l, r, v):
if self.tr[u] < v:
return -1
if l == r:
return l
mid = (l + r) >> 1
if self.tr[u << 1] >= v:
return self.query(u << 1, l, mid, v)
return self.query(u << 1 | 1, mid + 1, r, v)
def pushup(self, u):
self.tr[u] = max(self.tr[u << 1], self.tr[u << 1 | 1])
class Solution:
def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
tree = SegmentTree(baskets)
n = len(baskets)
ans = 0
for x in fruits:
i = tree.query(1, 1, n, x)
if i < 0:
ans += 1
else:
tree.modify(1, 1, n, i, 0)
return ansclass SegmentTree {
int[] nums;
int[] tr;
public SegmentTree(int[] nums) {
this.nums = nums;
int n = nums.length;
this.tr = new int[n << 2];
build(1, 1, n);
}
public void build(int u, int l, int r) {
if (l == r) {
tr[u] = nums[l - 1];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
public void modify(int u, int l, int r, int i, int v) {
if (l == r) {
tr[u] = v;
return;
}
int mid = (l + r) >> 1;
if (i <= mid) {
modify(u << 1, l, mid, i, v);
} else {
modify(u << 1 | 1, mid + 1, r, i, v);
}
pushup(u);
}
public int query(int u, int l, int r, int v) {
if (tr[u] < v) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (tr[u << 1] >= v) {
return query(u << 1, l, mid, v);
}
return query(u << 1 | 1, mid + 1, r, v);
}
public void pushup(int u) {
tr[u] = Math.max(tr[u << 1], tr[u << 1 | 1]);
}
}
class Solution {
public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
SegmentTree tree = new SegmentTree(baskets);
int n = baskets.length;
int ans = 0;
for (int x : fruits) {
int i = tree.query(1, 1, n, x);
if (i < 0) {
ans++;
} else {
tree.modify(1, 1, n, i, 0);
}
}
return ans;
}
}class SegmentTree {
public:
vector<int> nums, tr;
SegmentTree(vector<int>& nums) {
this->nums = nums;
int n = nums.size();
tr.resize(n * 4);
build(1, 1, n);
}
void build(int u, int l, int r) {
if (l == r) {
tr[u] = nums[l - 1];
return;
}
int mid = (l + r) >> 1;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int i, int v) {
if (l == r) {
tr[u] = v;
return;
}
int mid = (l + r) >> 1;
if (i <= mid) {
modify(u * 2, l, mid, i, v);
} else {
modify(u * 2 + 1, mid + 1, r, i, v);
}
pushup(u);
}
int query(int u, int l, int r, int v) {
if (tr[u] < v) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (tr[u * 2] >= v) {
return query(u * 2, l, mid, v);
}
return query(u * 2 + 1, mid + 1, r, v);
}
void pushup(int u) {
tr[u] = max(tr[u * 2], tr[u * 2 + 1]);
}
};
class Solution {
public:
int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
SegmentTree tree(baskets);
int n = baskets.size();
int ans = 0;
for (int x : fruits) {
int i = tree.query(1, 1, n, x);
if (i < 0) {
ans++;
} else {
tree.modify(1, 1, n, i, 0);
}
}
return ans;
}
};class SegmentTree {
nums: number[];
tr: number[];
constructor(nums: number[]) {
this.nums = nums;
const n = nums.length;
this.tr = Array(n * 4).fill(0);
this.build(1, 1, n);
}
build(u: number, l: number, r: number): void {
if (l === r) {
this.tr[u] = this.nums[l - 1];
return;
}
const mid = (l + r) >> 1;
this.build(u * 2, l, mid);
this.build(u * 2 + 1, mid + 1, r);
this.pushup(u);
}
modify(u: number, l: number, r: number, i: number, v: number): void {
if (l === r) {
this.tr[u] = v;
return;
}
const mid = (l + r) >> 1;
if (i <= mid) {
this.modify(u * 2, l, mid, i, v);
} else {
this.modify(u * 2 + 1, mid + 1, r, i, v);
}
this.pushup(u);
}
query(u: number, l: number, r: number, v: number): number {
if (this.tr[u] < v) {
return -1;
}
if (l === r) {
return l;
}
const mid = (l + r) >> 1;
if (this.tr[u * 2] >= v) {
return this.query(u * 2, l, mid, v);
}
return this.query(u * 2 + 1, mid + 1, r, v);
}
pushup(u: number): void {
this.tr[u] = Math.max(this.tr[u * 2], this.tr[u * 2 + 1]);
}
}
function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
const tree = new SegmentTree(baskets);
const n = baskets.length;
let ans = 0;
for (const x of fruits) {
const i = tree.query(1, 1, n, x);
if (i < 0) {
ans++;
} else {
tree.modify(1, 1, n, i, 0);
}
}
return ans;
}public class SegmentTree {
int[] nums;
int[] tr;
public SegmentTree(int[] nums) {
this.nums = nums;
int n = nums.Length;
this.tr = new int[n << 2];
Build(1, 1, n);
}
public void Build(int u, int l, int r) {
if (l == r) {
tr[u] = nums[l - 1];
return;
}
int mid = (l + r) >> 1;
Build(u << 1, l, mid);
Build(u << 1 | 1, mid + 1, r);
Pushup(u);
}
public void Modify(int u, int l, int r, int i, int v) {
if (l == r) {
tr[u] = v;
return;
}
int mid = (l + r) >> 1;
if (i <= mid) {
Modify(u << 1, l, mid, i, v);
} else {
Modify(u << 1 | 1, mid + 1, r, i, v);
}
Pushup(u);
}
public int Query(int u, int l, int r, int v) {
if (tr[u] < v) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (tr[u << 1] >= v) {
return Query(u << 1, l, mid, v);
}
return Query(u << 1 | 1, mid + 1, r, v);
}
public void Pushup(int u) {
tr[u] = Math.Max(tr[u << 1], tr[u << 1 | 1]);
}
}
public class Solution {
public int NumOfUnplacedFruits(int[] fruits, int[] baskets) {
SegmentTree tree = new SegmentTree(baskets);
int n = baskets.Length;
int ans = 0;
foreach (var x in fruits) {
int i = tree.Query(1, 1, n, x);
if (i < 0) {
ans++;
} else {
tree.Modify(1, 1, n, i, 0);
}
}
return ans;
}
}type SegmentTree struct {
nums, tr []int
}
func NewSegmentTree(nums []int) *SegmentTree {
n := len(nums)
tree := &SegmentTree{
nums: nums,
tr: make([]int, n*4),
}
tree.build(1, 1, n)
return tree
}
func (st *SegmentTree) build(u, l, r int) {
if l == r {
st.tr[u] = st.nums[l-1]
return
}
mid := (l + r) >> 1
st.build(u*2, l, mid)
st.build(u*2+1, mid+1, r)
st.pushup(u)
}
func (st *SegmentTree) modify(u, l, r, i, v int) {
if l == r {
st.tr[u] = v
return
}
mid := (l + r) >> 1
if i <= mid {
st.modify(u*2, l, mid, i, v)
} else {
st.modify(u*2+1, mid+1, r, i, v)
}
st.pushup(u)
}
func (st *SegmentTree) query(u, l, r, v int) int {
if st.tr[u] < v {
return -1
}
if l == r {
return l
}
mid := (l + r) >> 1
if st.tr[u*2] >= v {
return st.query(u*2, l, mid, v)
}
return st.query(u*2+1, mid+1, r, v)
}
func (st *SegmentTree) pushup(u int) {
st.tr[u] = max(st.tr[u*2], st.tr[u*2+1])
}
func numOfUnplacedFruits(fruits []int, baskets []int) (ans int) {
tree := NewSegmentTree(baskets)
n := len(baskets)
for _, x := range fruits {
i := tree.query(1, 1, n, x)
if i < 0 {
ans++
} else {
tree.modify(1, 1, n, i, 0)
}
}
return
}class SegmentTree {
var nums: [Int]
var tr: [Int]
init(_ nums: [Int]) {
self.nums = nums
let n = nums.count
self.tr = [Int](repeating: 0, count: n << 2)
build(1, 1, n)
}
func build(_ u: Int, _ l: Int, _ r: Int) {
if l == r {
tr[u] = nums[l - 1]
return
}
let mid = (l + r) >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
pushup(u)
}
func modify(_ u: Int, _ l: Int, _ r: Int, _ i: Int, _ v: Int) {
if l == r {
tr[u] = v
return
}
let mid = (l + r) >> 1
if i <= mid {
modify(u << 1, l, mid, i, v)
} else {
modify(u << 1 | 1, mid + 1, r, i, v)
}
pushup(u)
}
func query(_ u: Int, _ l: Int, _ r: Int, _ v: Int) -> Int {
if tr[u] < v {
return -1
}
if l == r {
return l
}
let mid = (l + r) >> 1
if tr[u << 1] >= v {
return query(u << 1, l, mid, v)
}
return query(u << 1 | 1, mid + 1, r, v)
}
func pushup(_ u: Int) {
tr[u] = max(tr[u << 1], tr[u << 1 | 1])
}
}
class Solution {
func numOfUnplacedFruits(_ fruits: [Int], _ baskets: [Int]) -> Int {
let tree = SegmentTree(baskets)
let n = baskets.count
var ans = 0
for x in fruits {
let i = tree.query(1, 1, n, x)
if i < 0 {
ans += 1
} else {
tree.modify(1, 1, n, i, 0)
}
}
return ans
}
}struct SegmentTree<'a> {
nums: &'a [i32],
tr: Vec<i32>,
}
impl<'a> SegmentTree<'a> {
fn new(nums: &'a [i32]) -> Self {
let n = nums.len();
let mut tree = SegmentTree {
nums,
tr: vec![0; n * 4],
};
tree.build(1, 1, n);
tree
}
fn build(&mut self, u: usize, l: usize, r: usize) {
if l == r {
self.tr[u] = self.nums[l - 1];
return;
}
let mid = (l + r) >> 1;
self.build(u * 2, l, mid);
self.build(u * 2 + 1, mid + 1, r);
self.pushup(u);
}
fn modify(&mut self, u: usize, l: usize, r: usize, i: usize, v: i32) {
if l == r {
self.tr[u] = v;
return;
}
let mid = (l + r) >> 1;
if i <= mid {
self.modify(u * 2, l, mid, i, v);
} else {
self.modify(u * 2 + 1, mid + 1, r, i, v);
}
self.pushup(u);
}
fn query(&self, u: usize, l: usize, r: usize, v: i32) -> i32 {
if self.tr[u] < v {
return -1;
}
if l == r {
return l as i32;
}
let mid = (l + r) >> 1;
if self.tr[u * 2] >= v {
return self.query(u * 2, l, mid, v);
}
self.query(u * 2 + 1, mid + 1, r, v)
}
fn pushup(&mut self, u: usize) {
self.tr[u] = self.tr[u * 2].max(self.tr[u * 2 + 1]);
}
}
impl Solution {
pub fn num_of_unplaced_fruits(fruits: Vec<i32>, baskets: Vec<i32>) -> i32 {
let mut tree = SegmentTree::new(&baskets);
let n = baskets.len();
let mut ans = 0;
for &x in fruits.iter() {
let i = tree.query(1, 1, n, x);
if i < 0 {
ans += 1;
} else {
tree.modify(1, 1, n, i as usize, 0);
}
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * m) | O(1) | Small input sizes or when demonstrating the basic placement rule |
| Segment Tree Binary Search | O((n + m) log m) | O(m) | General case with large constraints and frequent range queries |
| Ordered Set / Balanced BST | O((n + m) log m) | O(m) | Languages with strong ordered-set support and efficient lower_bound operations |
Frequently asked questions
Is Fruits Into Baskets III easy or hard?
Fruits Into Baskets III is rated Medium but leans toward the harder side because it requires combining range queries with efficient updates. Recognizing that a segment tree can locate the leftmost valid basket is the key insight.
Fruits Into Baskets III Python/Java solution
Most implementations build a segment tree over the basket capacities and perform recursive queries to locate the first basket that can hold each fruit. The same algorithm works in Python, Java, C++, Go, TypeScript, Rust, C#, and Swift with O((n + m) log m) complexity.
What is the best approach for Fruits Into Baskets III?
Segment Tree with binary search is the most efficient approach. Build a segment tree over basket capacities storing the maximum value in each range. For every fruit, traverse the tree to find the leftmost basket with capacity >= fruit size, then update that basket as used. This runs in O((n + m) log m) time and O(m) space.
How to solve Fruits Into Baskets III in O((n+m) log m)?
Build a segment tree over the baskets array storing the maximum capacity in each node. For every fruit, perform a tree-guided search: if the left child has a max value >= fruit size, move left; otherwise go right. Once the basket is found, update that index to remove it from future queries. Each operation takes O(log m).
Is Fruits Into Baskets III asked at Google/Amazon/Meta?
Problems involving segment trees, ordered sets, and range maximum queries appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of finding the first valid position using a segment tree is a common interview topic.
What data structure is used in Fruits Into Baskets III?
The optimal solution uses a Segment Tree to store range maximum values and support fast updates. Some implementations also use ordered sets or balanced binary search trees with lower_bound queries to locate the next valid basket efficiently.
What is the time complexity of Fruits Into Baskets III?
The optimal solution runs in O((n + m) log m) time using a segment tree. Each fruit requires a logarithmic search to locate the leftmost valid basket and another logarithmic update to mark the basket as used. Space complexity is O(m) for the tree structure.