Facebook Pixel

3479. Fruits Into Baskets III

MediumSegment TreeArrayBinary SearchOrdered Set
Leetcode Link

Problem Description

You have two arrays: fruits and baskets, both of length n.

  • fruits[i] represents the quantity of the i-th type of fruit
  • baskets[j] represents the capacity of the j-th basket

You need to place fruits into baskets following these rules:

  1. Process fruits from left to right (starting from index 0)
  2. For each fruit type, find the leftmost available basket that has capacity greater than or equal to the fruit quantity
  3. Each basket can hold only one type of fruit (once a basket is used, it cannot be used again)
  4. 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. We need to quickly find if there exists any basket with capacity ≥ fruit quantity
  2. Among all such baskets, we need the leftmost one
  3. 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 capacities
  • tr: The tree array storing maximum values for each segment (size 4n to accommodate the tree structure)

The tree is built using the build method:

  1. Each leaf node (when l == r) stores the actual basket capacity
  2. Internal nodes store the maximum capacity of their children using pushup(u), which sets tr[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

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:

  1. Initialize the segment tree with basket capacities
  2. 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 using modify
  3. 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

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 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example 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:

  1. 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 has O(4n) nodes for an array of size n, and each node operation takes O(1) time, building takes O(n) time.

  2. Processing fruits: For each of the m fruits (where m = len(fruits)):

    • The query operation traverses from root to leaf, taking O(log n) time
    • If a suitable basket is found, the modify operation also traverses from root to leaf, taking O(log n) time

    Therefore, processing all fruits takes O(m × log n) time.

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 size 4n = O(n)
  • The input array self.nums storing a reference to baskets with size n
  • The recursion stack depth during build, query, and modify operations is O(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 with modify()
  • 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:

  1. Keeping all segment tree operations in 1-based indexing
  2. Only converting to 0-based when accessing the original array in leaf nodes
  3. 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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Segment Tree

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

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More