Skip to main content
Talentd

Fruits Into Baskets III - Solution & Explanation

MediumArrayBinary SearchSegment TreeOrdered Set13 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

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.

Code

PythonJavaC++GoTypeScriptRustC#Swift

Python

Java

C++

Go

TypeScript

Rust

C#

Swift

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n * m)O(1)Small input sizes or when demonstrating the basic placement rule
Segment Tree Binary SearchO((n + m) log m)O(m)General case with large constraints and frequent range queries
Ordered Set / Balanced BSTO((n + m) log m)O(m)Languages with strong ordered-set support and efficient lower_bound operations

Video Solution

Fruits Into Baskets II & III | Segment Tree Concepts & Qns | Video 13 | Leetcode 3477 | 3479 | MIK • codestorywithMIK • 19,674 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Fruits Into Baskets III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Block Placement Queries