Facebook Pixel

732. My Calendar III

HardDesignSegment TreeBinary SearchOrdered SetPrefix Sum
Leetcode Link

Problem Description

You need to implement a calendar system that tracks the maximum number of overlapping events at any point in time.

A k-booking occurs when k events overlap at some point in time. For example, if 3 events all share a common time period, that creates a 3-booking.

The task is to implement a MyCalendarThree class with the following methods:

  1. MyCalendarThree(): Initializes an empty calendar object.

  2. book(startTime, endTime): Adds a new event to the calendar with time interval [startTime, endTime) (note: the interval is half-open, meaning it includes startTime but excludes endTime). After adding this event, the method returns the maximum k-booking among all events in the calendar.

For each call to book(), you need to:

  • Add the new event to your calendar
  • Determine the maximum number of events that overlap at any single point in time across the entire calendar
  • Return this maximum overlap count

The solution uses a Segment Tree data structure with lazy propagation to efficiently handle the large time range (up to 10^9) and track overlapping intervals. The segment tree:

  • Dynamically creates nodes as needed to handle the large range
  • Uses the modify() operation to increment the count for the interval [start+1, end] by 1
  • Uses the query() operation to find the maximum overlap count across all time points
  • Employs lazy propagation (add field) to efficiently update interval ranges without updating every single point

The key insight is that each booking increases the overlap count by 1 for all time points in its interval, and we need to track the maximum overlap count across all time points.

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

Intuition

When we think about finding the maximum number of overlapping events, we need to track how many events are active at each point in time. The naive approach would be to maintain a counter for every single time point, but with a time range up to 10^9, this would require too much memory.

The key observation is that we're dealing with interval updates - when we book an event from time start to end, we're essentially saying "increase the booking count by 1 for all time points in this range." After multiple bookings, we want to know the maximum booking count across all time points.

This naturally leads us to think about data structures that can efficiently handle:

  1. Range updates (add 1 to all values in a range)
  2. Range queries (find the maximum value in a range)

A Segment Tree is perfect for this because it can perform both operations in O(log n) time. However, updating every single point in a range would still be inefficient. This is where lazy propagation comes in - instead of immediately updating all child nodes when we modify a range, we mark the node with a "lazy" value (add) that will be pushed down to children only when needed.

The reason we use modify(start + 1, end, 1) instead of modify(start, end, 1) is likely due to how the coordinate system is set up in this implementation - the segment tree uses 1-based indexing internally, so we shift the start point by 1.

Since the time range can be up to 10^9, creating all nodes upfront would waste memory. Instead, we use dynamic node creation - nodes are only created when they're actually needed during modifications or queries. This way, we only create nodes for the parts of the time range that are actually used, making the solution both time and space efficient.

The maximum k-booking is simply the maximum value across the entire range after all bookings, which we obtain by querying the full range [1, 10^9 + 1].

Learn more about Segment Tree, Binary Search and Prefix Sum patterns.

Solution Approach

The solution uses a Segment Tree with Lazy Propagation to efficiently handle range updates and queries. Let's walk through the implementation:

Segment Tree Structure

Each Node in the segment tree represents an interval [l, r] and maintains:

  • l, r: The left and right boundaries of the interval
  • mid: The midpoint, calculated as (l + r) >> 1 (bitwise right shift for division by 2)
  • v: The maximum number of bookings in this interval
  • add: The lazy propagation value (pending updates to be pushed to children)
  • left, right: Pointers to child nodes (created dynamically)

Core Operations

1. Modify Operation (modify(l, r, v))

This operation adds value v to all elements in range [l, r]:

  • If the current node's interval is completely within [l, r], we update the node's value and lazy marker, then return (lazy propagation)
  • Otherwise, we push down any pending updates to children
  • Recursively modify the left child if the target range overlaps with [node.l, node.mid]
  • Recursively modify the right child if the target range overlaps with [node.mid + 1, node.r]
  • After modifying children, we push up to update the current node's value

2. Query Operation (query(l, r))

This finds the maximum value in range [l, r]:

  • If the current node's interval is completely within [l, r], return the node's value
  • Otherwise, push down pending updates and recursively query children
  • Return the maximum value from relevant children

3. Push Down (pushdown(node))

This propagates lazy updates to children:

  • Creates child nodes if they don't exist (dynamic node creation)
  • If there's a pending update (node.add != 0):
    • Add the pending value to both children's values and lazy markers
    • Clear the current node's lazy marker

4. Push Up (pushup(node))

Updates the current node's value based on its children:

  • Sets node.v = max(node.left.v, node.right.v)

MyCalendarThree Implementation

The MyCalendarThree class:

  1. Initializes a segment tree covering range [1, 10^9 + 1]
  2. For each book(start, end) call:
    • Performs modify(start + 1, end, 1) to increment the booking count in the interval
    • Queries the entire range [1, 10^9 + 1] to find the maximum booking count
    • Returns this maximum value

The time complexity for each booking is O(log n) where n is the range size, and the space complexity is O(m log n) where m is the number of bookings, since nodes are created dynamically only when needed.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate how the solution works. Suppose we have the following sequence of bookings:

  1. book(10, 20) - Event from time 10 to 20
  2. book(50, 60) - Event from time 50 to 60
  3. book(10, 40) - Event from time 10 to 40
  4. book(5, 15) - Event from time 5 to 15

Initial State:

  • Segment tree root covers range [1, 1000000001]
  • All values are 0 (no bookings yet)

After book(10, 20):

  • Call modify(11, 20, 1) to add 1 to range [11, 20]
  • The segment tree lazily marks this range with +1
  • Query entire range returns maximum value: 1
  • Timeline visualization: [10, 20) has 1 booking

After book(50, 60):

  • Call modify(51, 60, 1) to add 1 to range [51, 60]
  • This creates a separate branch in the tree (no overlap with previous)
  • Query returns maximum value: 1 (still no overlaps)
  • Timeline: [10, 20) has 1 booking, [50, 60) has 1 booking

After book(10, 40):

  • Call modify(11, 40, 1) to add 1 to range [11, 40]
  • Range [11, 20] now has value 2 (overlaps with first booking)
  • Range [21, 40] has value 1
  • Query returns maximum value: 2
  • Timeline: [10, 20) has 2 bookings, [20, 40) has 1 booking, [50, 60) has 1 booking

After book(5, 15):

  • Call modify(6, 15, 1) to add 1 to range [6, 15]
  • Range [11, 15] now has value 3 (overlaps with first and third bookings)
  • Range [6, 10] has value 1
  • Range [16, 20] has value 2
  • Query returns maximum value: 3
  • Timeline: [5, 10) has 1 booking, [10, 15) has 3 bookings, [15, 20) has 2 bookings, [20, 40) has 1 booking, [50, 60) has 1 booking

The segment tree efficiently tracks these overlaps using lazy propagation:

  • When we modify a range, we don't immediately update all affected nodes
  • Instead, we mark parent nodes with a lazy "add" value
  • These lazy values are pushed down only when we need to access child nodes
  • The tree dynamically creates nodes only for the ranges we actually use (not all 10^9 positions)

This way, each book() operation runs in O(log n) time, making it efficient even for the large time range.

Solution Implementation

1class Node:
2    """
3    Node class for dynamic segment tree.
4    Each node represents a range [l, r] and stores the maximum value in that range.
5    """
6    def __init__(self, left: int, right: int):
7        self.left_child = None  # Left child node
8        self.right_child = None  # Right child node
9        self.left_bound = left  # Left boundary of the range
10        self.right_bound = right  # Right boundary of the range
11        self.mid = (left + right) >> 1  # Midpoint of the range
12        self.max_value = 0  # Maximum value in this range
13        self.lazy_add = 0  # Lazy propagation value for range updates
14
15
16class SegmentTree:
17    """
18    Dynamic Segment Tree implementation with lazy propagation.
19    Supports range updates and range maximum queries.
20    """
21    def __init__(self):
22        # Initialize root node covering range [1, 10^9 + 1]
23        self.root = Node(1, int(1e9 + 1))
24
25    def modify(self, left: int, right: int, value: int, node: Node = None) -> None:
26        """
27        Add a value to all elements in range [left, right].
28      
29        Args:
30            left: Left boundary of update range
31            right: Right boundary of update range
32            value: Value to add to the range
33            node: Current node in recursion (default: root)
34        """
35        if left > right:
36            return
37      
38        if node is None:
39            node = self.root
40      
41        # If current node's range is completely within update range
42        if node.left_bound >= left and node.right_bound <= right:
43            node.max_value += value
44            node.lazy_add += value
45            return
46      
47        # Push down lazy updates before recursing
48        self.pushdown(node)
49      
50        # Recursively update left subtree if needed
51        if left <= node.mid:
52            self.modify(left, right, value, node.left_child)
53      
54        # Recursively update right subtree if needed
55        if right > node.mid:
56            self.modify(left, right, value, node.right_child)
57      
58        # Update current node's value based on children
59        self.pushup(node)
60
61    def query(self, left: int, right: int, node: Node = None) -> int:
62        """
63        Query the maximum value in range [left, right].
64      
65        Args:
66            left: Left boundary of query range
67            right: Right boundary of query range
68            node: Current node in recursion (default: root)
69      
70        Returns:
71            Maximum value in the specified range
72        """
73        if left > right:
74            return 0
75      
76        if node is None:
77            node = self.root
78      
79        # If current node's range is completely within query range
80        if node.left_bound >= left and node.right_bound <= right:
81            return node.max_value
82      
83        # Push down lazy updates before querying
84        self.pushdown(node)
85      
86        max_val = 0
87      
88        # Query left subtree if needed
89        if left <= node.mid:
90            max_val = max(max_val, self.query(left, right, node.left_child))
91      
92        # Query right subtree if needed
93        if right > node.mid:
94            max_val = max(max_val, self.query(left, right, node.right_child))
95      
96        return max_val
97
98    def pushup(self, node: Node) -> None:
99        """
100        Update parent node's value based on children's values.
101      
102        Args:
103            node: Node to update
104        """
105        node.max_value = max(node.left_child.max_value, node.right_child.max_value)
106
107    def pushdown(self, node: Node) -> None:
108        """
109        Push lazy updates from parent to children and create children if needed.
110      
111        Args:
112            node: Node whose lazy updates need to be pushed down
113        """
114        # Create left child if it doesn't exist
115        if node.left_child is None:
116            node.left_child = Node(node.left_bound, node.mid)
117      
118        # Create right child if it doesn't exist
119        if node.right_child is None:
120            node.right_child = Node(node.mid + 1, node.right_bound)
121      
122        # Push down lazy updates if any
123        if node.lazy_add:
124            node.left_child.max_value += node.lazy_add
125            node.right_child.max_value += node.lazy_add
126            node.left_child.lazy_add += node.lazy_add
127            node.right_child.lazy_add += node.lazy_add
128            node.lazy_add = 0
129
130
131class MyCalendarThree:
132    """
133    Calendar booking system that tracks the maximum number of overlapping events.
134    Uses a segment tree to efficiently handle range updates and queries.
135    """
136    def __init__(self):
137        self.tree = SegmentTree()
138
139    def book(self, start: int, end: int) -> int:
140        """
141        Book a new event in the calendar and return the maximum number of overlapping events.
142      
143        Args:
144            start: Start time of the event
145            end: End time of the event (exclusive)
146      
147        Returns:
148            Maximum number of overlapping events after this booking
149        """
150        # Increment count for range [start+1, end] (using 1-indexed coordinates)
151        self.tree.modify(start + 1, end, 1)
152      
153        # Query the maximum overlap across the entire range
154        return self.tree.query(1, int(1e9 + 1))
155
156
157# Your MyCalendarThree object will be instantiated and called as such:
158# obj = MyCalendarThree()
159# param_1 = obj.book(start, end)
160
1/**
2 * Node class represents a node in the segment tree
3 * Each node maintains information about a range [l, r]
4 */
5class Node {
6    Node left;          // Left child node
7    Node right;         // Right child node
8    int l;              // Left boundary of the range
9    int r;              // Right boundary of the range
10    int mid;            // Midpoint of the range
11    int v;              // Maximum value in this range
12    int add;            // Lazy propagation value to be added
13  
14    /**
15     * Constructor for a node with given range [l, r]
16     * @param l left boundary
17     * @param r right boundary
18     */
19    public Node(int l, int r) {
20        this.l = l;
21        this.r = r;
22        this.mid = (l + r) >> 1;  // Calculate midpoint using bit shift (equivalent to division by 2)
23    }
24}
25
26/**
27 * Segment Tree implementation with lazy propagation
28 * Supports range update and range maximum query
29 */
30class SegmentTree {
31    private Node root;  // Root node of the segment tree
32  
33    /**
34     * Constructor initializes the segment tree with range [1, 10^9 + 1]
35     */
36    public SegmentTree() {
37        root = new Node(1, (int) 1e9 + 1);
38    }
39  
40    /**
41     * Public method to modify (add value) to a range [l, r]
42     * @param l left boundary of the range
43     * @param r right boundary of the range
44     * @param v value to add
45     */
46    public void modify(int l, int r, int v) {
47        modify(l, r, v, root);
48    }
49  
50    /**
51     * Private recursive method to perform range update
52     * @param l left boundary of update range
53     * @param r right boundary of update range
54     * @param v value to add
55     * @param node current node being processed
56     */
57    private void modify(int l, int r, int v, Node node) {
58        // Invalid range check
59        if (l > r) {
60            return;
61        }
62      
63        // If current node's range is completely within update range
64        if (node.l >= l && node.r <= r) {
65            node.v += v;      // Update the maximum value
66            node.add += v;    // Mark for lazy propagation
67            return;
68        }
69      
70        // Create children if needed and push down lazy values
71        pushdown(node);
72      
73        // Recursively update left child if needed
74        if (l <= node.mid) {
75            modify(l, r, v, node.left);
76        }
77      
78        // Recursively update right child if needed
79        if (r > node.mid) {
80            modify(l, r, v, node.right);
81        }
82      
83        // Update current node's value based on children
84        pushup(node);
85    }
86  
87    /**
88     * Public method to query maximum value in range [l, r]
89     * @param l left boundary of query range
90     * @param r right boundary of query range
91     * @return maximum value in the range
92     */
93    public int query(int l, int r) {
94        return query(l, r, root);
95    }
96  
97    /**
98     * Private recursive method to perform range maximum query
99     * @param l left boundary of query range
100     * @param r right boundary of query range
101     * @param node current node being processed
102     * @return maximum value in the range
103     */
104    private int query(int l, int r, Node node) {
105        // Invalid range check
106        if (l > r) {
107            return 0;
108        }
109      
110        // If current node's range is completely within query range
111        if (node.l >= l && node.r <= r) {
112            return node.v;
113        }
114      
115        // Create children if needed and push down lazy values
116        pushdown(node);
117      
118        int maxValue = 0;
119      
120        // Query left child if needed
121        if (l <= node.mid) {
122            maxValue = Math.max(maxValue, query(l, r, node.left));
123        }
124      
125        // Query right child if needed
126        if (r > node.mid) {
127            maxValue = Math.max(maxValue, query(l, r, node.right));
128        }
129      
130        return maxValue;
131    }
132  
133    /**
134     * Update parent node's value based on its children
135     * @param node parent node to update
136     */
137    private void pushup(Node node) {
138        node.v = Math.max(node.left.v, node.right.v);
139    }
140  
141    /**
142     * Push down lazy propagation values to children
143     * Creates children nodes if they don't exist
144     * @param node parent node whose lazy values need to be pushed down
145     */
146    private void pushdown(Node node) {
147        // Create left child if it doesn't exist
148        if (node.left == null) {
149            node.left = new Node(node.l, node.mid);
150        }
151      
152        // Create right child if it doesn't exist
153        if (node.right == null) {
154            node.right = new Node(node.mid + 1, node.r);
155        }
156      
157        // Push down lazy propagation value if exists
158        if (node.add != 0) {
159            Node leftChild = node.left;
160            Node rightChild = node.right;
161          
162            // Apply lazy value to children
163            leftChild.add += node.add;
164            rightChild.add += node.add;
165            leftChild.v += node.add;
166            rightChild.v += node.add;
167          
168            // Clear parent's lazy value
169            node.add = 0;
170        }
171    }
172}
173
174/**
175 * MyCalendarThree class to handle booking intervals
176 * Tracks the maximum number of overlapping events
177 */
178class MyCalendarThree {
179    private SegmentTree tree;  // Segment tree to track overlapping events
180  
181    /**
182     * Constructor initializes the calendar
183     */
184    public MyCalendarThree() {
185        tree = new SegmentTree();
186    }
187  
188    /**
189     * Book a new event in the calendar
190     * @param start start time of the event
191     * @param end end time of the event (exclusive)
192     * @return maximum number of overlapping events after booking
193     */
194    public int book(int start, int end) {
195        // Increment count for range [start+1, end]
196        // Note: start+1 is used to handle the inclusive start boundary
197        tree.modify(start + 1, end, 1);
198      
199        // Return the maximum overlap count across all time points
200        return tree.query(1, (int) 1e9 + 1);
201    }
202}
203
204/**
205 * Your MyCalendarThree object will be instantiated and called as such:
206 * MyCalendarThree obj = new MyCalendarThree();
207 * int param_1 = obj.book(start,end);
208 */
209
1/**
2 * Dynamic Segment Tree Node
3 * Represents a node in the segment tree with lazy propagation
4 */
5class Node {
6public:
7    Node* left;       // Left child node
8    Node* right;      // Right child node
9    int l;            // Left boundary of the range
10    int r;            // Right boundary of the range
11    int mid;          // Midpoint of the range
12    int maxValue;     // Maximum value in this node's range
13    int lazyAdd;      // Lazy propagation value to be added
14
15    Node(int l, int r) {
16        this->l = l;
17        this->r = r;
18        this->mid = (l + r) >> 1;  // Equivalent to (l + r) / 2
19        this->left = this->right = nullptr;
20        maxValue = lazyAdd = 0;
21    }
22};
23
24/**
25 * Dynamic Segment Tree with Lazy Propagation
26 * Supports range updates and range maximum queries
27 */
28class SegmentTree {
29private:
30    Node* root;
31
32public:
33    SegmentTree() {
34        // Initialize with range [1, 1e9 + 1] to cover all possible values
35        root = new Node(1, 1e9 + 1);
36    }
37
38    /**
39     * Public interface for range modification
40     * Adds value v to all elements in range [l, r]
41     */
42    void modify(int l, int r, int v) {
43        modify(l, r, v, root);
44    }
45
46    /**
47     * Private recursive function for range modification
48     * Updates the segment tree by adding v to range [l, r]
49     */
50    void modify(int l, int r, int v, Node* node) {
51        // Base case: invalid range
52        if (l > r) {
53            return;
54        }
55      
56        // If current node's range is completely within [l, r]
57        if (node->l >= l && node->r <= r) {
58            node->maxValue += v;
59            node->lazyAdd += v;  // Mark for lazy propagation
60            return;
61        }
62      
63        // Push down lazy values before continuing
64        pushdown(node);
65      
66        // Recursively update left subtree if needed
67        if (l <= node->mid) {
68            modify(l, r, v, node->left);
69        }
70      
71        // Recursively update right subtree if needed
72        if (r > node->mid) {
73            modify(l, r, v, node->right);
74        }
75      
76        // Update current node's value based on children
77        pushup(node);
78    }
79
80    /**
81     * Public interface for range query
82     * Returns the maximum value in range [l, r]
83     */
84    int query(int l, int r) {
85        return query(l, r, root);
86    }
87
88    /**
89     * Private recursive function for range query
90     * Finds the maximum value in range [l, r]
91     */
92    int query(int l, int r, Node* node) {
93        // Base case: invalid range
94        if (l > r) {
95            return 0;
96        }
97      
98        // If current node's range is completely within [l, r]
99        if (node->l >= l && node->r <= r) {
100            return node->maxValue;
101        }
102      
103        // Push down lazy values before querying children
104        pushdown(node);
105      
106        int maxResult = 0;
107      
108        // Query left subtree if there's overlap
109        if (l <= node->mid) {
110            maxResult = max(maxResult, query(l, r, node->left));
111        }
112      
113        // Query right subtree if there's overlap
114        if (r > node->mid) {
115            maxResult = max(maxResult, query(l, r, node->right));
116        }
117      
118        return maxResult;
119    }
120
121    /**
122     * Updates parent node's value based on its children
123     * Called after modifying children nodes
124     */
125    void pushup(Node* node) {
126        node->maxValue = max(node->left->maxValue, node->right->maxValue);
127    }
128
129    /**
130     * Pushes down lazy values to children nodes
131     * Creates children nodes dynamically if they don't exist
132     */
133    void pushdown(Node* node) {
134        // Create left child if it doesn't exist
135        if (!node->left) {
136            node->left = new Node(node->l, node->mid);
137        }
138      
139        // Create right child if it doesn't exist
140        if (!node->right) {
141            node->right = new Node(node->mid + 1, node->r);
142        }
143      
144        // Push down lazy values if any
145        if (node->lazyAdd) {
146            Node* leftChild = node->left;
147            Node* rightChild = node->right;
148          
149            // Apply lazy value to both children
150            leftChild->maxValue += node->lazyAdd;
151            rightChild->maxValue += node->lazyAdd;
152            leftChild->lazyAdd += node->lazyAdd;
153            rightChild->lazyAdd += node->lazyAdd;
154          
155            // Clear current node's lazy value
156            node->lazyAdd = 0;
157        }
158    }
159};
160
161/**
162 * MyCalendarThree class
163 * Tracks the maximum number of concurrent events at any time
164 */
165class MyCalendarThree {
166public:
167    SegmentTree* tree;
168
169    MyCalendarThree() {
170        tree = new SegmentTree();
171    }
172
173    /**
174     * Books an event in the time range [start, end)
175     * Returns the maximum number of concurrent events after booking
176     * 
177     * @param start: Start time of the event (inclusive)
178     * @param end: End time of the event (exclusive)
179     * @return Maximum number of concurrent events
180     */
181    int book(int start, int end) {
182        // Add 1 to the range [start+1, end] to represent the event
183        // Note: start+1 is used to make the range inclusive at start
184        tree->modify(start + 1, end, 1);
185      
186        // Query the entire range to find the maximum concurrent events
187        return tree->query(1, 1e9 + 1);
188    }
189};
190
191/**
192 * Your MyCalendarThree object will be instantiated and called as such:
193 * MyCalendarThree* obj = new MyCalendarThree();
194 * int param_1 = obj->book(start,end);
195 */
196
1// Node structure for segment tree
2interface SegmentNode {
3    left: SegmentNode | null;
4    right: SegmentNode | null;
5    leftBound: number;
6    rightBound: number;
7    midPoint: number;
8    maxValue: number;
9    lazyAdd: number;
10}
11
12// Create a new segment tree node
13function createNode(leftBound: number, rightBound: number): SegmentNode {
14    return {
15        left: null,
16        right: null,
17        leftBound,
18        rightBound,
19        midPoint: Math.floor((leftBound + rightBound) / 2),
20        maxValue: 0,
21        lazyAdd: 0
22    };
23}
24
25// Global segment tree root
26let segmentTreeRoot: SegmentNode = createNode(1, 1000000001);
27
28// Update the maximum value of a node based on its children
29function pushUp(node: SegmentNode): void {
30    if (node.left && node.right) {
31        node.maxValue = Math.max(node.left.maxValue, node.right.maxValue);
32    }
33}
34
35// Push down lazy propagation values to children
36function pushDown(node: SegmentNode): void {
37    // Create children nodes if they don't exist
38    if (node.left === null) {
39        node.left = createNode(node.leftBound, node.midPoint);
40    }
41    if (node.right === null) {
42        node.right = createNode(node.midPoint + 1, node.rightBound);
43    }
44  
45    // Propagate lazy values to children
46    if (node.lazyAdd !== 0) {
47        node.left.lazyAdd += node.lazyAdd;
48        node.right.lazyAdd += node.lazyAdd;
49        node.left.maxValue += node.lazyAdd;
50        node.right.maxValue += node.lazyAdd;
51        node.lazyAdd = 0;
52    }
53}
54
55// Modify range [left, right] by adding value
56function modifyRange(left: number, right: number, value: number, node: SegmentNode = segmentTreeRoot): void {
57    // Invalid range
58    if (left > right) {
59        return;
60    }
61  
62    // Current node is completely within the range
63    if (node.leftBound >= left && node.rightBound <= right) {
64        node.maxValue += value;
65        node.lazyAdd += value;
66        return;
67    }
68  
69    // Push down before recursing
70    pushDown(node);
71  
72    // Recursively update left child if range overlaps
73    if (left <= node.midPoint && node.left) {
74        modifyRange(left, right, value, node.left);
75    }
76  
77    // Recursively update right child if range overlaps
78    if (right > node.midPoint && node.right) {
79        modifyRange(left, right, value, node.right);
80    }
81  
82    // Update current node's value based on children
83    pushUp(node);
84}
85
86// Query maximum value in range [left, right]
87function queryRange(left: number, right: number, node: SegmentNode = segmentTreeRoot): number {
88    // Invalid range
89    if (left > right) {
90        return 0;
91    }
92  
93    // Current node is completely within the range
94    if (node.leftBound >= left && node.rightBound <= right) {
95        return node.maxValue;
96    }
97  
98    // Push down before recursing
99    pushDown(node);
100  
101    let maxResult = 0;
102  
103    // Query left child if range overlaps
104    if (left <= node.midPoint && node.left) {
105        maxResult = Math.max(maxResult, queryRange(left, right, node.left));
106    }
107  
108    // Query right child if range overlaps
109    if (right > node.midPoint && node.right) {
110        maxResult = Math.max(maxResult, queryRange(left, right, node.right));
111    }
112  
113    return maxResult;
114}
115
116// Book a new event and return the maximum number of concurrent events
117function book(startTime: number, endTime: number): number {
118    // Add 1 to the range [startTime+1, endTime] to track overlapping events
119    modifyRange(startTime + 1, endTime, 1);
120  
121    // Query the maximum value in the entire range
122    return queryRange(1, 1000000001);
123}
124

Time and Space Complexity

Time Complexity: O(n × log M) where n is the number of bookings and M is the range of values (10^9 in this case).

For each book operation:

  • The modify operation traverses the segment tree from root to leaves, creating nodes as needed. The depth of the tree is O(log M) where M = 10^9 is the range of the segment tree.
  • The query operation also traverses the tree with depth O(log M).
  • Therefore, each booking takes O(log M) time.
  • For n bookings, the total time complexity is O(n × log M).

Since M is a constant (10^9), this can be simplified to O(n × log 10^9) = O(n × 30) = O(n) in practical terms, though technically it's O(n × log M).

Space Complexity: O(n) where n is the number of bookings.

The segment tree uses dynamic node creation (lazy propagation):

  • Nodes are only created when needed during pushdown operations.
  • Each book operation potentially creates at most O(log M) new nodes along the path from root to the affected leaves.
  • After n bookings, the maximum number of nodes created is O(n × log M).
  • However, due to overlapping intervals and reuse of existing nodes, the actual space used is bounded by O(min(n × log M, M)).
  • Since we're dealing with intervals and not all positions in the range [1, 10^9] will be accessed, the practical space complexity is O(n) as stated in the reference answer.

The reference answer simplifies the complexity by considering that the number of distinct nodes created is proportional to the number of bookings rather than the full range, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Range Indexing

One of the most common mistakes is using the wrong range for the modify operation. The problem states that the interval is [startTime, endTime) (half-open), but the segment tree implementation uses 1-indexed coordinates.

Pitfall Code:

def book(self, start: int, end: int) -> int:
    # Wrong: This would include both start and end
    self.tree.modify(start, end, 1)
    # Or wrong: Off-by-one error
    self.tree.modify(start, end - 1, 1)

Correct Solution:

def book(self, start: int, end: int) -> int:
    # Correct: Convert to 1-indexed and handle half-open interval
    self.tree.modify(start + 1, end, 1)

2. Memory Issues with Static Segment Tree

Creating a complete segment tree for range [1, 10^9] upfront would require enormous memory and cause Memory Limit Exceeded.

Pitfall Code:

class SegmentTree:
    def __init__(self):
        # Wrong: Pre-allocating array for entire range
        self.tree = [0] * (4 * int(1e9))  # This will cause memory error!

Correct Solution: Dynamic node creation - nodes are only created when needed during modify/query operations:

def pushdown(self, node: Node) -> None:
    # Create children only when needed
    if node.left_child is None:
        node.left_child = Node(node.left_bound, node.mid)
    if node.right_child is None:
        node.right_child = Node(node.mid + 1, node.right_bound)

3. Forgetting Lazy Propagation

Without lazy propagation, range updates become O(n) instead of O(log n), causing Time Limit Exceeded.

Pitfall Code:

def modify(self, left: int, right: int, value: int, node: Node) -> None:
    if node.left_bound == node.right_bound:  # Leaf node
        node.max_value += value
        return
    # Wrong: Not using lazy propagation, updating all leaves
    if left <= node.mid:
        self.modify(left, right, value, node.left_child)
    if right > node.mid:
        self.modify(left, right, value, node.right_child)

Correct Solution: Use lazy propagation to defer updates:

def modify(self, left: int, right: int, value: int, node: Node) -> None:
    # If entire range is covered, update lazily
    if node.left_bound >= left and node.right_bound <= right:
        node.max_value += value
        node.lazy_add += value  # Store for lazy propagation
        return

4. Incorrect Pushup Logic

After modifying children, forgetting to update the parent node's value leads to incorrect query results.

Pitfall Code:

def modify(self, left: int, right: int, value: int, node: Node) -> None:
    # ... recursive calls ...
    # Wrong: Forgetting to update parent after modifying children
    return

Correct Solution: Always pushup after modifying children:

def modify(self, left: int, right: int, value: int, node: Node) -> None:
    # ... handle lazy propagation and recursive calls ...
  
    # Critical: Update parent based on children
    self.pushup(node)

5. Not Pushing Down Before Queries

Forgetting to push down lazy values before querying children results in stale/incorrect values.

Pitfall Code:

def query(self, left: int, right: int, node: Node) -> int:
    if node.left_bound >= left and node.right_bound <= right:
        return node.max_value
  
    # Wrong: Not pushing down lazy updates
    max_val = 0
    if left <= node.mid:
        max_val = max(max_val, self.query(left, right, node.left_child))

Correct Solution: Always push down before accessing children:

def query(self, left: int, right: int, node: Node) -> int:
    if node.left_bound >= left and node.right_bound <= right:
        return node.max_value
  
    # Essential: Push down lazy updates first
    self.pushdown(node)
  
    # Now query children with updated values
    max_val = 0
    if left <= node.mid:
        max_val = max(max_val, self.query(left, right, node.left_child))
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27
1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

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

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More