3479. Fruits Into Baskets III
Problem Description
You have two arrays: fruits
and baskets
, both of length n
.
fruits[i]
represents the quantity of thei-th
type of fruitbaskets[j]
represents the capacity of thej-th
basket
You need to place fruits into baskets following these rules:
- Process fruits from left to right (starting from index 0)
- For each fruit type, find the leftmost available basket that has capacity greater than or equal to the fruit quantity
- Each basket can hold only one type of fruit (once a basket is used, it cannot be used again)
- If no suitable basket exists for a fruit type, that fruit remains unplaced
Return the total number of fruit types that remain unplaced after attempting to place all fruits.
Example walkthrough:
If fruits = [4, 2, 5]
and baskets = [3, 6, 2]
:
- Fruit type 0 (quantity 4): Look for leftmost basket with capacity ≥ 4. Basket 1 (capacity 6) works, so place it there.
- Fruit type 1 (quantity 2): Look for leftmost unused basket with capacity ≥ 2. Basket 0 (capacity 3) works, so place it there.
- Fruit type 2 (quantity 5): Look for leftmost unused basket with capacity ≥ 5. Only basket 2 (capacity 2) remains, which is too small. This fruit remains unplaced.
- Result: 1 unplaced fruit type.
The solution uses a segment tree to efficiently find the leftmost basket with sufficient capacity. The segment tree maintains the maximum capacity in each interval, enabling binary search to locate the first suitable basket in O(log n)
time. When a basket is used, its capacity is set to 0 in the tree.
Intuition
The key insight is recognizing this as a matching problem with a specific constraint: we need to find the leftmost suitable basket for each fruit. A naive approach would be to scan through all baskets for each fruit, giving us O(n²)
time complexity.
However, we can optimize this by thinking about what information we need to maintain:
- We need to quickly find if there exists any basket with capacity ≥ fruit quantity
- Among all such baskets, we need the leftmost one
- Once a basket is used, it should no longer be considered for future fruits
This naturally leads us to think about range queries - we want to query "what's the maximum capacity in the range [1, n]?" and more specifically, "where is the first position that has capacity ≥ x?"
A segment tree is perfect for this because:
- It maintains the maximum value in any range in
O(log n)
time - We can perform binary search on the tree structure itself to find the leftmost position with sufficient capacity
- We can update individual positions (set capacity to 0 when used) in
O(log n)
time
The segment tree essentially transforms our problem from "scan all baskets for each fruit" to "binary search for the first suitable basket," reducing our overall complexity from O(n²)
to O(n log n)
.
The beauty of this approach is that the segment tree naturally preserves the "leftmost" property we need - when we query from the root and prioritize the left subtree over the right subtree, we automatically get the leftmost basket that meets our criteria.
Learn more about Segment Tree and Binary Search patterns.
Solution Approach
The solution uses a Segment Tree data structure to efficiently handle the basket allocation problem. Let's walk through the implementation step by step:
Segment Tree Construction
The SegmentTree
class maintains:
nums
: The original basket capacitiestr
: The tree array storing maximum values for each segment (size4n
to accommodate the tree structure)
The tree is built using the build
method:
- Each leaf node (when
l == r
) stores the actual basket capacity - Internal nodes store the maximum capacity of their children using
pushup(u)
, which setstr[u] = max(tr[u << 1], tr[u << 1 | 1])
Key Operations
1. Query Operation (query
method):
- Finds the leftmost basket with capacity ≥
v
- Returns the 1-indexed position of the basket, or -1 if none exists
- The search strategy:
- If current segment's maximum <
v
, no suitable basket exists (return -1) - If we're at a leaf node, return its position
- Otherwise, check left subtree first (ensuring leftmost selection)
- Only check right subtree if left doesn't have a suitable basket
- If current segment's maximum <
2. Modify Operation (modify
method):
- Updates a specific basket's capacity to
v
- Navigates to the target leaf and updates it
- Calls
pushup
to propagate the change up the tree
Main Algorithm
The numOfUnplacedFruits
method:
- Initialize the segment tree with basket capacities
- For each fruit quantity
x
:- Query the tree for the leftmost basket with capacity ≥
x
- If
i < 0
(no suitable basket found), increment the unplaced count - Otherwise, mark basket
i
as used by setting its capacity to 0 usingmodify
- Query the tree for the leftmost basket with capacity ≥
- Return the total count of unplaced fruits
Time Complexity
- Building the tree:
O(n)
- Each query and modify operation:
O(log n)
- Total for
n
fruits:O(n log n)
Space Complexity
O(n)
for the segment tree array
The segment tree approach elegantly handles the "leftmost available basket" requirement while maintaining efficient updates as baskets are used.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through a small example with fruits = [3, 5, 2]
and baskets = [4, 2, 6]
.
Initial Setup:
- Build segment tree with basket capacities [4, 2, 6]
- Tree structure stores maximum values: root node has max(4, 2, 6) = 6
Processing Fruit 0 (quantity = 3):
- Query: Find leftmost basket with capacity ≥ 3
- Start at root (max = 6, sufficient)
- Check left subtree first (contains baskets 0-1, max = 4)
- Left subtree has capacity ≥ 3, so recurse left
- Reach basket 0 (capacity = 4 ≥ 3) ✓
- Place fruit 0 in basket 0
- Update: Set basket 0 capacity to 0
- Tree updates: propagate changes upward
Processing Fruit 1 (quantity = 5):
- Query: Find leftmost basket with capacity ≥ 5
- Start at root (max = 6, sufficient)
- Check left subtree (contains baskets 0-1, max = 2 now)
- Left subtree max = 2 < 5, insufficient
- Check right subtree (contains basket 2, max = 6)
- Basket 2 (capacity = 6 ≥ 5) ✓
- Place fruit 1 in basket 2
- Update: Set basket 2 capacity to 0
Processing Fruit 2 (quantity = 2):
- Query: Find leftmost basket with capacity ≥ 2
- Start at root (max = 2, sufficient)
- Check left subtree (max = 2)
- Reach basket 1 (capacity = 2 ≥ 2) ✓
- Place fruit 2 in basket 1
- Update: Set basket 1 capacity to 0
Result: All fruits placed, 0 unplaced fruits.
The segment tree efficiently finds the leftmost suitable basket in O(log n) time by prioritizing the left subtree during queries, eliminating the need to scan all baskets linearly.
Solution Implementation
1from typing import List
2
3
4class SegmentTree:
5 """
6 Segment Tree data structure for efficient range maximum queries
7 and point updates.
8 """
9 __slots__ = ["nums", "tr"]
10
11 def __init__(self, nums: List[int]) -> None:
12 """
13 Initialize the segment tree with given array.
14
15 Args:
16 nums: Input array to build segment tree from
17 """
18 self.nums = nums
19 n = len(nums)
20 # Allocate space for segment tree (4 times the array size)
21 self.tr = [0] * (n << 2)
22 self.build(1, 1, n)
23
24 def build(self, node_idx: int, left: int, right: int) -> None:
25 """
26 Build the segment tree recursively.
27
28 Args:
29 node_idx: Current node index in the tree
30 left: Left boundary of current segment
31 right: Right boundary of current segment
32 """
33 if left == right:
34 # Leaf node: store the actual array value (1-indexed to 0-indexed)
35 self.tr[node_idx] = self.nums[left - 1]
36 return
37
38 mid = (left + right) >> 1
39 # Build left subtree
40 self.build(node_idx << 1, left, mid)
41 # Build right subtree
42 self.build(node_idx << 1 | 1, mid + 1, right)
43 # Update current node with maximum of children
44 self.pushup(node_idx)
45
46 def modify(self, node_idx: int, left: int, right: int,
47 target_pos: int, new_value: int) -> None:
48 """
49 Update a single position in the segment tree.
50
51 Args:
52 node_idx: Current node index in the tree
53 left: Left boundary of current segment
54 right: Right boundary of current segment
55 target_pos: Position to update (1-indexed)
56 new_value: New value to set at target position
57 """
58 if left == right:
59 # Found the target leaf node
60 self.tr[node_idx] = new_value
61 return
62
63 mid = (left + right) >> 1
64 if target_pos <= mid:
65 # Target is in left subtree
66 self.modify(node_idx << 1, left, mid, target_pos, new_value)
67 else:
68 # Target is in right subtree
69 self.modify(node_idx << 1 | 1, mid + 1, right, target_pos, new_value)
70 # Update current node after modification
71 self.pushup(node_idx)
72
73 def query(self, node_idx: int, left: int, right: int,
74 min_value: int) -> int:
75 """
76 Find the leftmost position with value >= min_value.
77
78 Args:
79 node_idx: Current node index in the tree
80 left: Left boundary of current segment
81 right: Right boundary of current segment
82 min_value: Minimum value threshold
83
84 Returns:
85 Position of leftmost element >= min_value (1-indexed),
86 or -1 if no such element exists
87 """
88 # If maximum in current segment is less than min_value, no valid position exists
89 if self.tr[node_idx] < min_value:
90 return -1
91
92 if left == right:
93 # Found a valid leaf node
94 return left
95
96 mid = (left + right) >> 1
97 # Check if left subtree has a valid element
98 if self.tr[node_idx << 1] >= min_value:
99 # Search in left subtree first (to find leftmost)
100 return self.query(node_idx << 1, left, mid, min_value)
101 # Otherwise, search in right subtree
102 return self.query(node_idx << 1 | 1, mid + 1, right, min_value)
103
104 def pushup(self, node_idx: int) -> None:
105 """
106 Update parent node with maximum of its children.
107
108 Args:
109 node_idx: Index of node to update
110 """
111 self.tr[node_idx] = max(self.tr[node_idx << 1],
112 self.tr[node_idx << 1 | 1])
113
114
115class Solution:
116 def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
117 """
118 Count the number of fruits that cannot be placed in any basket.
119
120 Args:
121 fruits: List of fruit sizes
122 baskets: List of basket capacities
123
124 Returns:
125 Number of fruits that cannot be placed in any basket
126 """
127 # Build segment tree from basket capacities
128 tree = SegmentTree(baskets)
129 n = len(baskets)
130 unplaced_count = 0
131
132 for fruit_size in fruits:
133 # Find leftmost basket that can hold this fruit
134 basket_position = tree.query(1, 1, n, fruit_size)
135
136 if basket_position < 0:
137 # No basket can hold this fruit
138 unplaced_count += 1
139 else:
140 # Place fruit in basket and mark basket as used (capacity = 0)
141 tree.modify(1, 1, n, basket_position, 0)
142
143 return unplaced_count
144
1/**
2 * Segment Tree implementation for range maximum queries and point updates.
3 * This data structure efficiently maintains the maximum value in any range.
4 */
5class SegmentTree {
6 private int[] originalArray; // Original input array
7 private int[] segmentTree; // Segment tree array storing max values
8
9 /**
10 * Constructor to initialize the segment tree with given array.
11 * @param nums Input array to build the segment tree from
12 */
13 public SegmentTree(int[] nums) {
14 this.originalArray = nums;
15 int arrayLength = nums.length;
16 // Allocate 4 times the array size for the segment tree
17 this.segmentTree = new int[arrayLength << 2];
18 // Build the tree starting from root node (1), covering range [1, n]
19 build(1, 1, arrayLength);
20 }
21
22 /**
23 * Recursively builds the segment tree.
24 * @param nodeIndex Current node index in the segment tree
25 * @param leftBound Left boundary of current segment (1-indexed)
26 * @param rightBound Right boundary of current segment (1-indexed)
27 */
28 public void build(int nodeIndex, int leftBound, int rightBound) {
29 // Base case: leaf node
30 if (leftBound == rightBound) {
31 // Convert 1-indexed position to 0-indexed array position
32 segmentTree[nodeIndex] = originalArray[leftBound - 1];
33 return;
34 }
35
36 // Calculate middle point
37 int mid = (leftBound + rightBound) >> 1;
38
39 // Recursively build left subtree
40 build(nodeIndex << 1, leftBound, mid);
41 // Recursively build right subtree
42 build((nodeIndex << 1) | 1, mid + 1, rightBound);
43
44 // Update current node with maximum of children
45 pushup(nodeIndex);
46 }
47
48 /**
49 * Updates a single position in the segment tree.
50 * @param nodeIndex Current node index in the segment tree
51 * @param leftBound Left boundary of current segment
52 * @param rightBound Right boundary of current segment
53 * @param targetPosition Position to update (1-indexed)
54 * @param newValue New value to set at the position
55 */
56 public void modify(int nodeIndex, int leftBound, int rightBound,
57 int targetPosition, int newValue) {
58 // Base case: reached the target leaf node
59 if (leftBound == rightBound) {
60 segmentTree[nodeIndex] = newValue;
61 return;
62 }
63
64 // Calculate middle point
65 int mid = (leftBound + rightBound) >> 1;
66
67 // Determine which subtree contains the target position
68 if (targetPosition <= mid) {
69 // Target is in left subtree
70 modify(nodeIndex << 1, leftBound, mid, targetPosition, newValue);
71 } else {
72 // Target is in right subtree
73 modify((nodeIndex << 1) | 1, mid + 1, rightBound, targetPosition, newValue);
74 }
75
76 // Update current node after modification
77 pushup(nodeIndex);
78 }
79
80 /**
81 * Finds the leftmost position where value is >= threshold.
82 * @param nodeIndex Current node index in the segment tree
83 * @param leftBound Left boundary of current segment
84 * @param rightBound Right boundary of current segment
85 * @param threshold Minimum value threshold to search for
86 * @return Position (1-indexed) of leftmost element >= threshold, or -1 if none exists
87 */
88 public int query(int nodeIndex, int leftBound, int rightBound, int threshold) {
89 // If maximum in this range is less than threshold, no valid position exists
90 if (segmentTree[nodeIndex] < threshold) {
91 return -1;
92 }
93
94 // Base case: reached a leaf node that satisfies the condition
95 if (leftBound == rightBound) {
96 return leftBound;
97 }
98
99 // Calculate middle point
100 int mid = (leftBound + rightBound) >> 1;
101
102 // Check if left subtree has a valid position
103 if (segmentTree[nodeIndex << 1] >= threshold) {
104 // Search in left subtree first (to find leftmost position)
105 return query(nodeIndex << 1, leftBound, mid, threshold);
106 }
107
108 // Otherwise, search in right subtree
109 return query((nodeIndex << 1) | 1, mid + 1, rightBound, threshold);
110 }
111
112 /**
113 * Updates parent node with the maximum value of its children.
114 * @param nodeIndex Current node index to update
115 */
116 public void pushup(int nodeIndex) {
117 int leftChild = nodeIndex << 1;
118 int rightChild = (nodeIndex << 1) | 1;
119 segmentTree[nodeIndex] = Math.max(segmentTree[leftChild], segmentTree[rightChild]);
120 }
121}
122
123/**
124 * Solution class for the fruit placement problem.
125 */
126class Solution {
127 /**
128 * Counts the number of fruits that cannot be placed in any basket.
129 * Each fruit requires a basket with capacity >= fruit size.
130 * Once a basket is used, its capacity becomes 0.
131 *
132 * @param fruits Array of fruit sizes to be placed
133 * @param baskets Array of basket capacities
134 * @return Number of fruits that cannot be placed
135 */
136 public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
137 // Initialize segment tree with basket capacities
138 SegmentTree tree = new SegmentTree(baskets);
139 int basketCount = baskets.length;
140 int unplacedCount = 0;
141
142 // Try to place each fruit
143 for (int fruitSize : fruits) {
144 // Find leftmost basket with capacity >= fruitSize
145 int basketPosition = tree.query(1, 1, basketCount, fruitSize);
146
147 if (basketPosition < 0) {
148 // No suitable basket found, fruit cannot be placed
149 unplacedCount++;
150 } else {
151 // Place fruit in basket by setting its capacity to 0
152 tree.modify(1, 1, basketCount, basketPosition, 0);
153 }
154 }
155
156 return unplacedCount;
157 }
158}
159
1class SegmentTree {
2public:
3 vector<int> nums; // Original array of values
4 vector<int> tree; // Segment tree array storing maximum values
5
6 // Constructor: Initialize segment tree with given array
7 SegmentTree(vector<int>& nums) {
8 this->nums = nums;
9 int n = nums.size();
10 tree.resize(n * 4); // Allocate 4n space for segment tree
11 build(1, 1, n); // Build tree starting from root node 1
12 }
13
14 // Build segment tree recursively
15 // u: current node index, l: left boundary, r: right boundary
16 void build(int node, int left, int right) {
17 // Base case: leaf node
18 if (left == right) {
19 tree[node] = nums[left - 1]; // Store value (1-indexed to 0-indexed conversion)
20 return;
21 }
22
23 // Recursive case: build left and right subtrees
24 int mid = (left + right) >> 1; // Equivalent to (left + right) / 2
25 build(node * 2, left, mid); // Build left child
26 build(node * 2 + 1, mid + 1, right); // Build right child
27 pushup(node); // Update current node based on children
28 }
29
30 // Modify a single element at position i to value v
31 // u: current node, l: left boundary, r: right boundary, i: target position, v: new value
32 void modify(int node, int left, int right, int targetPos, int newValue) {
33 // Base case: reached the target leaf node
34 if (left == right) {
35 tree[node] = newValue;
36 return;
37 }
38
39 // Recursive case: traverse to the correct child
40 int mid = (left + right) >> 1;
41 if (targetPos <= mid) {
42 modify(node * 2, left, mid, targetPos, newValue); // Target in left subtree
43 } else {
44 modify(node * 2 + 1, mid + 1, right, targetPos, newValue); // Target in right subtree
45 }
46 pushup(node); // Update current node after modification
47 }
48
49 // Query the leftmost position where value >= threshold
50 // u: current node, l: left boundary, r: right boundary, v: threshold value
51 // Returns: 1-indexed position or -1 if not found
52 int query(int node, int left, int right, int threshold) {
53 // If maximum in this range is less than threshold, no valid position exists
54 if (tree[node] < threshold) {
55 return -1;
56 }
57
58 // Base case: reached a leaf node that satisfies the condition
59 if (left == right) {
60 return left; // Return 1-indexed position
61 }
62
63 // Check left subtree first (to find leftmost position)
64 int mid = (left + right) >> 1;
65 if (tree[node * 2] >= threshold) {
66 return query(node * 2, left, mid, threshold); // Search in left subtree
67 }
68 // Otherwise, search in right subtree
69 return query(node * 2 + 1, mid + 1, right, threshold);
70 }
71
72 // Update parent node based on its children (maintains max property)
73 void pushup(int node) {
74 tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
75 }
76};
77
78class Solution {
79public:
80 // Count the number of fruits that cannot be placed in any basket
81 int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
82 // Initialize segment tree with basket capacities
83 SegmentTree segTree(baskets);
84 int n = baskets.size();
85 int unplacedCount = 0;
86
87 // Process each fruit
88 for (int fruitSize : fruits) {
89 // Find the leftmost basket that can hold this fruit (capacity >= fruitSize)
90 int basketIndex = segTree.query(1, 1, n, fruitSize);
91
92 if (basketIndex < 0) {
93 // No basket can hold this fruit
94 unplacedCount++;
95 } else {
96 // Place fruit in basket by setting its capacity to 0
97 segTree.modify(1, 1, n, basketIndex, 0);
98 }
99 }
100
101 return unplacedCount;
102 }
103};
104
1// Global variables for segment tree
2let nums: number[];
3let tr: number[];
4
5/**
6 * Initializes the segment tree with the given array
7 * @param numsArray - The input array to build the segment tree from
8 */
9function initializeSegmentTree(numsArray: number[]): void {
10 nums = numsArray;
11 const n = nums.length;
12 tr = Array(n * 4).fill(0);
13 build(1, 1, n);
14}
15
16/**
17 * Builds the segment tree recursively
18 * @param nodeIndex - Current node index in the tree
19 * @param left - Left boundary of the current segment
20 * @param right - Right boundary of the current segment
21 */
22function build(nodeIndex: number, left: number, right: number): void {
23 // Base case: leaf node
24 if (left === right) {
25 tr[nodeIndex] = nums[left - 1];
26 return;
27 }
28
29 // Calculate middle point
30 const mid = (left + right) >> 1;
31
32 // Recursively build left and right subtrees
33 build(nodeIndex * 2, left, mid);
34 build(nodeIndex * 2 + 1, mid + 1, right);
35
36 // Update current node based on children
37 pushup(nodeIndex);
38}
39
40/**
41 * Modifies a single element in the segment tree
42 * @param nodeIndex - Current node index in the tree
43 * @param left - Left boundary of the current segment
44 * @param right - Right boundary of the current segment
45 * @param targetIndex - Index of the element to modify (1-indexed)
46 * @param newValue - New value to set
47 */
48function modify(nodeIndex: number, left: number, right: number, targetIndex: number, newValue: number): void {
49 // Base case: found the target leaf node
50 if (left === right) {
51 tr[nodeIndex] = newValue;
52 return;
53 }
54
55 // Calculate middle point
56 const mid = (left + right) >> 1;
57
58 // Recursively modify the appropriate subtree
59 if (targetIndex <= mid) {
60 modify(nodeIndex * 2, left, mid, targetIndex, newValue);
61 } else {
62 modify(nodeIndex * 2 + 1, mid + 1, right, targetIndex, newValue);
63 }
64
65 // Update current node after modification
66 pushup(nodeIndex);
67}
68
69/**
70 * Queries the leftmost index where the value is >= threshold
71 * @param nodeIndex - Current node index in the tree
72 * @param left - Left boundary of the current segment
73 * @param right - Right boundary of the current segment
74 * @param threshold - Minimum value threshold
75 * @returns The leftmost index (1-indexed) where value >= threshold, or -1 if not found
76 */
77function query(nodeIndex: number, left: number, right: number, threshold: number): number {
78 // No element in this segment satisfies the condition
79 if (tr[nodeIndex] < threshold) {
80 return -1;
81 }
82
83 // Base case: leaf node
84 if (left === right) {
85 return left;
86 }
87
88 // Calculate middle point
89 const mid = (left + right) >> 1;
90
91 // Check left subtree first (to find leftmost valid position)
92 if (tr[nodeIndex * 2] >= threshold) {
93 return query(nodeIndex * 2, left, mid, threshold);
94 }
95
96 // If left subtree doesn't have valid element, check right subtree
97 return query(nodeIndex * 2 + 1, mid + 1, right, threshold);
98}
99
100/**
101 * Updates parent node value based on its children (maintains max value)
102 * @param nodeIndex - Current node index to update
103 */
104function pushup(nodeIndex: number): void {
105 tr[nodeIndex] = Math.max(tr[nodeIndex * 2], tr[nodeIndex * 2 + 1]);
106}
107
108/**
109 * Counts the number of fruits that cannot be placed in baskets
110 * @param fruits - Array of fruit sizes
111 * @param baskets - Array of basket capacities
112 * @returns Number of fruits that remain unplaced
113 */
114function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
115 // Initialize segment tree with basket capacities
116 initializeSegmentTree(baskets);
117 const basketCount = baskets.length;
118 let unplacedCount = 0;
119
120 // Process each fruit
121 for (const fruitSize of fruits) {
122 // Find the leftmost basket that can hold this fruit
123 const basketIndex = query(1, 1, basketCount, fruitSize);
124
125 if (basketIndex < 0) {
126 // No basket can hold this fruit
127 unplacedCount++;
128 } else {
129 // Place fruit in basket (set capacity to 0)
130 modify(1, 1, basketCount, basketIndex, 0);
131 }
132 }
133
134 return unplacedCount;
135}
136
Time and Space Complexity
Time Complexity: O((m + n) × log n)
The time complexity consists of two main parts:
-
Building the segment tree: The
build
method is called once during initialization. It visits each node in the segment tree exactly once. Since the segment tree hasO(4n)
nodes for an array of sizen
, and each node operation takesO(1)
time, building takesO(n)
time. -
Processing fruits: For each of the
m
fruits (wherem = len(fruits)
):- The
query
operation traverses from root to leaf, takingO(log n)
time - If a suitable basket is found, the
modify
operation also traverses from root to leaf, takingO(log n)
time
Therefore, processing all fruits takes
O(m × log n)
time. - The
The total time complexity is O(n + m × log n) = O((m + n) × log n)
.
When m ≈ n
(fruits and baskets have similar sizes), this simplifies to O(n × log n)
, which matches the reference answer.
Space Complexity: O(n)
The space complexity comes from:
- The segment tree array
self.tr
with size4n = O(n)
- The input array
self.nums
storing a reference tobaskets
with sizen
- The recursion stack depth during
build
,query
, andmodify
operations isO(log n)
The dominant factor is the segment tree array, giving us a total space complexity of O(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Index Confusion Between 0-based and 1-based Systems
The Pitfall: The segment tree implementation uses 1-based indexing internally (for easier tree navigation), while Python arrays use 0-based indexing. This creates multiple places where index conversion errors can occur:
- In
build()
: Converting from 1-based tree positions to 0-based array access - In
query()
: Returning 1-based positions that need to be used withmodify()
- Forgetting that
query()
returns 1-based indices while the original arrays are 0-based
Example Bug:
# Incorrect: Using the returned position directly with the array basket_position = tree.query(1, 1, n, fruit_size) if basket_position >= 0: baskets[basket_position] = 0 # Wrong! This would access wrong index
Solution: Maintain consistency by:
- Keeping all segment tree operations in 1-based indexing
- Only converting to 0-based when accessing the original array in leaf nodes
- Document clearly which methods use which indexing system
2. Segment Tree Array Size Allocation
The Pitfall:
Allocating insufficient space for the segment tree array. While 4n
is mathematically sufficient, some implementations might use 2n
thinking it's enough for a binary tree, leading to array index out of bounds errors.
Why This Happens:
The segment tree needs space for internal nodes. For an array of size n
, the tree height is ⌈log₂ n⌉
, and the maximum number of nodes is 2^(h+1) - 1
, which can be up to 4n
for non-power-of-2 sizes.
Solution:
Always allocate 4n
space for the segment tree array:
self.tr = [0] * (n << 2) # Correct: 4n space # NOT: self.tr = [0] * (2 * n) # Insufficient!
3. Incorrect Tree Navigation with Bit Operations
The Pitfall: Misunderstanding or misusing bit operations for tree navigation:
- Left child:
node_idx << 1
(multiply by 2) - Right child:
node_idx << 1 | 1
(multiply by 2 and add 1)
Common Mistakes:
# Wrong: Using addition instead of OR right_child = (node_idx << 1) + 1 # Works but less idiomatic # Wrong: Incorrect operator precedence right_child = node_idx << 1 | 1 # Correct right_child = node_idx << (1 | 1) # Wrong! This shifts by 1, not what we want
Solution: Use parentheses to ensure correct precedence and stick to the standard idiom:
left_child = node_idx << 1 right_child = (node_idx << 1) | 1
4. Not Handling Edge Cases in Query
The Pitfall: The query method assumes there's always a valid segment to search. If all baskets are already used (capacity 0) and a new fruit needs placement, the method should correctly return -1.
Potential Bug: Not checking if the maximum value in the root node is sufficient before diving into recursion could lead to unnecessary traversal or incorrect results.
Solution:
The current implementation correctly checks if self.tr[node_idx] < min_value
at the beginning of query()
, which handles this case efficiently. Always ensure this check is present.
5. Forgetting to Update Parent Nodes After Modification
The Pitfall:
After modifying a leaf node, forgetting to call pushup()
to propagate changes up the tree. This would cause future queries to use stale maximum values.
Example Bug:
def modify(self, node_idx, left, right, target_pos, new_value):
if left == right:
self.tr[node_idx] = new_value
return # Forgot to call pushup after recursive calls!
# ... recursive calls ...
# Missing: self.pushup(node_idx)
Solution:
Always call pushup()
after modifying child nodes to maintain the tree invariant that each node contains the maximum of its children.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!