Fruits Into Baskets III - Video Solutions
Fruits Into Baskets II & III | Segment Tree Concepts & Qns | Video 13 | Leetcode 3477 | 3479 | MIK
Fruits Into Baskets III - Video Solution
Watch 10 video solutions for Fruits Into Baskets III, a medium level problem involving Array, Binary Search, Segment Tree. This walkthrough by codestorywithMIK has 19,674 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] = 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.
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 |