Facebook Pixel

699. Falling Squares

HardSegment TreeArrayOrdered Set
Leetcode Link

Problem Description

You are simulating squares falling onto a 2D plane along the X-axis. When a square is dropped, it falls straight down until it either lands on top of another square or reaches the ground (X-axis).

You're given a 2D array positions where each positions[i] = [left_i, sideLength_i] represents:

  • left_i: The X-coordinate where the left edge of the square is positioned
  • sideLength_i: The side length of the square

The squares are dropped one at a time in the order given. Each square:

  1. Falls vertically downward (in the negative Y direction)
  2. Stops when it lands on the top of another square or on the X-axis
  3. Freezes in place once it lands (cannot move anymore)
  4. Does NOT count as landing if it only brushes the sides of another square

After each square is dropped, you need to record the maximum height among all stacks of squares at that moment.

Your task is to return an array ans where ans[i] represents the tallest stack height after dropping the i-th square.

For example, if you drop a square with side length 2 at position 1, it lands on the X-axis with height 2. If you then drop another square with side length 3 at position 2 (which overlaps with the first square from position 2 to 3), it will land on top of the first square, resulting in a height of 2 + 3 = 5 at that position.

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

Intuition

When a square falls, we need to find the maximum height of all existing squares within its landing range [left, left + sideLength - 1]. The new square will land on top of the highest point in this range, so its final height will be max_height_in_range + sideLength.

After placing the square, we need to update the height for the entire range it covers to this new height, since any future square landing in this range needs to know about this new obstacle.

This problem essentially requires us to:

  1. Query the maximum height in a given range [l, r]
  2. Update all positions in a range [l, r] to a new height value
  3. Track the overall maximum height after each operation

These operations naturally lead us to think about data structures that efficiently handle range queries and range updates. A naive approach would be to maintain an array of heights for each position, but with coordinates up to 10^8, this becomes impractical.

A Segment Tree is perfect for this scenario because:

  • It can query the maximum value in any range in O(log n) time
  • It can update all values in a range to a new value in O(log n) time using lazy propagation
  • With dynamic node creation, we only create nodes as needed, avoiding the memory issue of large coordinate ranges

The lazy propagation technique is crucial here - when we update a range to a new height, we don't immediately update all child nodes. Instead, we mark the node with an add flag and only push down the update when we need to access the children later. This keeps our updates efficient even for large ranges.

By maintaining the running maximum height (mx) as we process each square, we can easily return the tallest stack height after each drop.

Learn more about Segment Tree patterns.

Solution Approach

The solution uses a dynamic Segment Tree with lazy propagation to efficiently handle range queries and updates.

Segment Tree Structure

Each node in the segment tree contains:

  • l, r: The left and right boundaries of the interval this node represents
  • mid: The midpoint (l + r) >> 1 for splitting the interval
  • v: The maximum height value in this interval
  • add: The lazy propagation marker for pending updates
  • left, right: Pointers to child nodes (created dynamically)

The tree is initialized with root covering the range [1, 10^9] to handle all possible coordinates.

Key Operations

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

  • Returns the maximum height in the range [l, r]
  • If the current node's interval is completely within [l, r], return its value v
  • Otherwise, recursively query relevant child nodes and return the maximum
  • Before accessing children, apply any pending updates via pushdown()

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

  • Updates all positions in range [l, r] to height v
  • If the current node's interval is completely within [l, r], update its value and mark with lazy flag
  • Otherwise, recursively modify relevant child nodes
  • After modifying children, update parent's value via pushup()

3. Lazy Propagation (pushdown())

  • Creates child nodes dynamically if they don't exist
  • If there's a pending update (add != 0), propagate it to both children
  • Sets children's values and lazy markers to the parent's add value
  • Clears the parent's lazy marker

4. Value Update (pushup())

  • After modifying children, updates parent's value to be the maximum of its children's values
  • Ensures the tree maintains correct maximum values after modifications

Main Algorithm

For each square [l, w] in positions:

  1. Calculate the right boundary: r = l + w - 1
  2. Query the maximum height in range [l, r]: h_base = tree.query(l, r)
  3. Calculate new height for this square: h = h_base + w
  4. Update the running maximum: mx = max(mx, h)
  5. Record the current maximum in the answer array
  6. Update the segment tree: set all positions in [l, r] to height h

The time complexity is O(n log C) where n is the number of squares and C is the coordinate range (10^9). The space complexity is O(n log C) for the dynamically created nodes.

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 walk through a small example with positions = [[1, 2], [2, 3], [6, 1]].

Initial Setup:

  • Create a segment tree with root covering range [1, 10^9]
  • Initialize mx = 0 (running maximum height)
  • Initialize empty result array ans = []

Drop Square 1: [1, 2] (left=1, width=2)

  • Right boundary: r = 1 + 2 - 1 = 2, so square covers [1, 2]
  • Query maximum height in range [1, 2]:
    • Tree is empty, returns 0
  • New height: h = 0 + 2 = 2
  • Update maximum: mx = max(0, 2) = 2
  • Add to result: ans = [2]
  • Update tree: Set range [1, 2] to height 2
    • Tree now has: positions 1-2 with height 2

Drop Square 2: [2, 3] (left=2, width=3)

  • Right boundary: r = 2 + 3 - 1 = 4, so square covers [2, 4]
  • Query maximum height in range [2, 4]:
    • Position 2 has height 2 (from square 1)
    • Positions 3-4 have height 0
    • Maximum in range = 2
  • New height: h = 2 + 3 = 5 (lands on top of square 1)
  • Update maximum: mx = max(2, 5) = 5
  • Add to result: ans = [2, 5]
  • Update tree: Set range [2, 4] to height 5
    • Tree now has: position 1 with height 2, positions 2-4 with height 5

Drop Square 3: [6, 1] (left=6, width=1)

  • Right boundary: r = 6 + 1 - 1 = 6, so square covers [6, 6]
  • Query maximum height in range [6, 6]:
    • Position 6 has height 0 (no squares here)
    • Maximum in range = 0
  • New height: h = 0 + 1 = 1 (lands on ground)
  • Update maximum: mx = max(5, 1) = 5 (remains 5)
  • Add to result: ans = [2, 5, 5]
  • Update tree: Set range [6, 6] to height 1
    • Tree now has: position 1 with height 2, positions 2-4 with height 5, position 6 with height 1

Final Result: [2, 5, 5]

The segment tree efficiently handles these operations:

  • When querying range [2, 4] in step 2, it finds the overlap with existing square at position 2
  • Lazy propagation ensures we don't update every single position individually
  • Dynamic node creation means we only create nodes for positions we actually use (1-6) rather than the entire range [1, 10^9]

Solution Implementation

1from typing import List
2
3
4class Node:
5    """Node for dynamic segment tree."""
6  
7    def __init__(self, left: int, right: int):
8        self.left_child = None  # Left child node
9        self.right_child = None  # Right child node
10        self.left_bound = left  # Left boundary of the interval
11        self.right_bound = right  # Right boundary of the interval
12        self.mid = (left + right) >> 1  # Midpoint of the interval
13        self.max_value = 0  # Maximum value in this interval
14        self.lazy_tag = 0  # Lazy propagation tag for range updates
15
16
17class SegmentTree:
18    """Dynamic segment tree for range maximum query and range update."""
19  
20    def __init__(self):
21        # Initialize root node covering range [1, 10^9]
22        self.root = Node(1, int(1e9))
23  
24    def modify(self, left: int, right: int, value: int, node: Node = None) -> None:
25        """
26        Update all elements in range [left, right] to value.
27      
28        Args:
29            left: Left boundary of update range
30            right: Right boundary of update range
31            value: Value to set for the range
32            node: Current node in recursion (defaults to root)
33        """
34        if left > right:
35            return
36      
37        if node is None:
38            node = self.root
39      
40        # If current node's interval is completely within update range
41        if node.left_bound >= left and node.right_bound <= right:
42            node.max_value = value
43            node.lazy_tag = value
44            return
45      
46        # Push down lazy tag before going to children
47        self._push_down(node)
48      
49        # Recursively update left child if needed
50        if left <= node.mid:
51            self.modify(left, right, value, node.left_child)
52      
53        # Recursively update right child if needed
54        if right > node.mid:
55            self.modify(left, right, value, node.right_child)
56      
57        # Update current node's value based on children
58        self._push_up(node)
59  
60    def query(self, left: int, right: int, node: Node = None) -> int:
61        """
62        Query maximum value in range [left, right].
63      
64        Args:
65            left: Left boundary of query range
66            right: Right boundary of query range
67            node: Current node in recursion (defaults to root)
68      
69        Returns:
70            Maximum value in the specified range
71        """
72        if left > right:
73            return 0
74      
75        if node is None:
76            node = self.root
77      
78        # If current node's interval is completely within query range
79        if node.left_bound >= left and node.right_bound <= right:
80            return node.max_value
81      
82        # Push down lazy tag before querying children
83        self._push_down(node)
84      
85        max_val = 0
86      
87        # Query left child if needed
88        if left <= node.mid:
89            max_val = max(max_val, self.query(left, right, node.left_child))
90      
91        # Query right child if needed
92        if right > node.mid:
93            max_val = max(max_val, self.query(left, right, node.right_child))
94      
95        return max_val
96  
97    def _push_up(self, node: Node) -> None:
98        """
99        Update parent node's value based on children's values.
100      
101        Args:
102            node: Node to update
103        """
104        node.max_value = max(node.left_child.max_value, node.right_child.max_value)
105  
106    def _push_down(self, node: Node) -> None:
107        """
108        Push lazy tag down to children and create children if they don't exist.
109      
110        Args:
111            node: Node whose lazy tag needs to be pushed down
112        """
113        # Create left child if it doesn't exist
114        if node.left_child is None:
115            node.left_child = Node(node.left_bound, node.mid)
116      
117        # Create right child if it doesn't exist
118        if node.right_child is None:
119            node.right_child = Node(node.mid + 1, node.right_bound)
120      
121        # If there's a lazy tag, propagate it to children
122        if node.lazy_tag:
123            node.left_child.max_value = node.lazy_tag
124            node.right_child.max_value = node.lazy_tag
125            node.left_child.lazy_tag = node.lazy_tag
126            node.right_child.lazy_tag = node.lazy_tag
127            node.lazy_tag = 0  # Clear the lazy tag after propagation
128
129
130class Solution:
131    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
132        """
133        Simulate falling squares and return maximum height after each square falls.
134      
135        Args:
136            positions: List of [left, side_length] pairs representing squares
137      
138        Returns:
139            List of maximum heights after each square falls
140        """
141        result = []
142        max_height = 0
143        tree = SegmentTree()
144      
145        for left_pos, side_length in positions:
146            # Calculate right boundary of the square
147            right_pos = left_pos + side_length - 1
148          
149            # Find current maximum height in the range where square will land
150            current_height = tree.query(left_pos, right_pos)
151          
152            # New height after this square lands
153            new_height = current_height + side_length
154          
155            # Update global maximum height
156            max_height = max(max_height, new_height)
157            result.append(max_height)
158          
159            # Update the height in the range covered by this square
160            tree.modify(left_pos, right_pos, new_height)
161      
162        return result
163
1/**
2 * Node class representing 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
13  
14    public Node(int l, int r) {
15        this.l = l;
16        this.r = r;
17        this.mid = (l + r) >> 1;  // Equivalent to (l + r) / 2
18    }
19}
20
21/**
22 * Segment Tree implementation with lazy propagation
23 * Supports range updates and range maximum queries
24 */
25class SegmentTree {
26    private Node root = new Node(1, (int) 1e9);  // Root node covering range [1, 10^9]
27  
28    public SegmentTree() {
29    }
30  
31    /**
32     * Public method to modify a range [l, r] with value v
33     */
34    public void modify(int l, int r, int v) {
35        modify(l, r, v, root);
36    }
37  
38    /**
39     * Private recursive method to modify a range [l, r] with value v
40     * @param l Left boundary of the range to modify
41     * @param r Right boundary of the range to modify
42     * @param v Value to set in the range
43     * @param node Current node being processed
44     */
45    public void modify(int l, int r, int v, Node node) {
46        // Base case: invalid range
47        if (l > r) {
48            return;
49        }
50      
51        // If current node's range is completely within [l, r]
52        if (node.l >= l && node.r <= r) {
53            node.v = v;     // Update node value
54            node.add = v;   // Mark for lazy propagation
55            return;
56        }
57      
58        // Push down lazy updates to children
59        pushdown(node);
60      
61        // Recursively update left subtree if needed
62        if (l <= node.mid) {
63            modify(l, r, v, node.left);
64        }
65      
66        // Recursively update right subtree if needed
67        if (r > node.mid) {
68            modify(l, r, v, node.right);
69        }
70      
71        // Update current node's value based on children
72        pushup(node);
73    }
74  
75    /**
76     * Public method to query maximum value in range [l, r]
77     */
78    public int query(int l, int r) {
79        return query(l, r, root);
80    }
81  
82    /**
83     * Private recursive method to query maximum value in range [l, r]
84     * @param l Left boundary of the query range
85     * @param r Right boundary of the query range
86     * @param node Current node being processed
87     * @return Maximum value in the range [l, r]
88     */
89    public int query(int l, int r, Node node) {
90        // Base case: invalid range
91        if (l > r) {
92            return 0;
93        }
94      
95        // If current node's range is completely within [l, r]
96        if (node.l >= l && node.r <= r) {
97            return node.v;
98        }
99      
100        // Push down lazy updates to children
101        pushdown(node);
102      
103        int maxValue = 0;
104      
105        // Query left subtree if needed
106        if (l <= node.mid) {
107            maxValue = Math.max(maxValue, query(l, r, node.left));
108        }
109      
110        // Query right subtree if needed
111        if (r > node.mid) {
112            maxValue = Math.max(maxValue, query(l, r, node.right));
113        }
114      
115        return maxValue;
116    }
117  
118    /**
119     * Push up operation: Update parent node value based on children
120     * @param node Node to update
121     */
122    public void pushup(Node node) {
123        node.v = Math.max(node.left.v, node.right.v);
124    }
125  
126    /**
127     * Push down operation: Propagate lazy updates to children
128     * Creates children nodes if they don't exist (dynamic segment tree)
129     * @param node Node whose updates need to be pushed down
130     */
131    public void pushdown(Node node) {
132        // Create left child if it doesn't exist
133        if (node.left == null) {
134            node.left = new Node(node.l, node.mid);
135        }
136      
137        // Create right child if it doesn't exist
138        if (node.right == null) {
139            node.right = new Node(node.mid + 1, node.r);
140        }
141      
142        // Propagate lazy update to children if exists
143        if (node.add != 0) {
144            Node leftChild = node.left;
145            Node rightChild = node.right;
146          
147            // Apply lazy update to children
148            leftChild.add = node.add;
149            rightChild.add = node.add;
150            leftChild.v = node.add;
151            rightChild.v = node.add;
152          
153            // Clear lazy update from current node
154            node.add = 0;
155        }
156    }
157}
158
159/**
160 * Solution class for the Falling Squares problem
161 */
162class Solution {
163    /**
164     * Simulates falling squares and returns the maximum height after each drop
165     * @param positions Array where positions[i] = [left_i, sideLength_i]
166     * @return List of maximum heights after each square falls
167     */
168    public List<Integer> fallingSquares(int[][] positions) {
169        List<Integer> ans = new ArrayList<>();
170        SegmentTree tree = new SegmentTree();
171        int maxHeight = 0;
172      
173        // Process each falling square
174        for (int[] position : positions) {
175            int left = position[0];
176            int sideLength = position[1];
177            int right = left + sideLength - 1;
178          
179            // Find current maximum height in the range where square will land
180            int currentMaxHeight = tree.query(left, right);
181          
182            // Calculate new height after square lands
183            int newHeight = currentMaxHeight + sideLength;
184          
185            // Update overall maximum height
186            maxHeight = Math.max(maxHeight, newHeight);
187            ans.add(maxHeight);
188          
189            // Update the range with new height
190            tree.modify(left, right, newHeight);
191        }
192      
193        return ans;
194    }
195}
196
1class Node {
2public:
3    Node* left;
4    Node* right;
5    int rangeLeft;      // Left boundary of the range this node represents
6    int rangeRight;     // Right boundary of the range this node represents
7    int rangeMid;       // Mid point of the range
8    int maxValue;       // Maximum value in this range
9    int lazyTag;        // Lazy propagation tag for range updates
10
11    Node(int l, int r) {
12        this->rangeLeft = l;
13        this->rangeRight = r;
14        this->rangeMid = (l + r) >> 1;
15        this->left = nullptr;
16        this->right = nullptr;
17        this->maxValue = 0;
18        this->lazyTag = 0;
19    }
20};
21
22class SegmentTree {
23private:
24    Node* root;
25
26    // Helper function to update a range [l, r] with value v
27    void modify(int l, int r, int v, Node* node) {
28        if (l > r) {
29            return;
30        }
31      
32        // If current node's range is completely within [l, r]
33        if (node->rangeLeft >= l && node->rangeRight <= r) {
34            node->maxValue = v;
35            node->lazyTag = v;
36            return;
37        }
38      
39        // Push down lazy tag before going to children
40        pushdown(node);
41      
42        // Recursively update left and right children if needed
43        if (l <= node->rangeMid) {
44            modify(l, r, v, node->left);
45        }
46        if (r > node->rangeMid) {
47            modify(l, r, v, node->right);
48        }
49      
50        // Update current node's value based on children
51        pushup(node);
52    }
53
54    // Helper function to query maximum value in range [l, r]
55    int query(int l, int r, Node* node) {
56        if (l > r) {
57            return 0;
58        }
59      
60        // If current node's range is completely within [l, r]
61        if (node->rangeLeft >= l && node->rangeRight <= r) {
62            return node->maxValue;
63        }
64      
65        // Push down lazy tag before querying children
66        pushdown(node);
67      
68        int result = 0;
69        // Query left child if range overlaps
70        if (l <= node->rangeMid) {
71            result = max(result, query(l, r, node->left));
72        }
73        // Query right child if range overlaps
74        if (r > node->rangeMid) {
75            result = max(result, query(l, r, node->right));
76        }
77      
78        return result;
79    }
80
81    // Update parent node's value based on children's values
82    void pushup(Node* node) {
83        node->maxValue = max(node->left->maxValue, node->right->maxValue);
84    }
85
86    // Push lazy tag to children nodes (lazy propagation)
87    void pushdown(Node* node) {
88        // Create children nodes if they don't exist (dynamic segment tree)
89        if (!node->left) {
90            node->left = new Node(node->rangeLeft, node->rangeMid);
91        }
92        if (!node->right) {
93            node->right = new Node(node->rangeMid + 1, node->rangeRight);
94        }
95      
96        // If there's a lazy tag, propagate it to children
97        if (node->lazyTag) {
98            Node* leftChild = node->left;
99            Node* rightChild = node->right;
100          
101            // Update children's values and lazy tags
102            leftChild->maxValue = node->lazyTag;
103            rightChild->maxValue = node->lazyTag;
104            leftChild->lazyTag = node->lazyTag;
105            rightChild->lazyTag = node->lazyTag;
106          
107            // Clear current node's lazy tag
108            node->lazyTag = 0;
109        }
110    }
111
112public:
113    SegmentTree() {
114        // Initialize root with range [1, 10^9]
115        root = new Node(1, 1000000000);
116    }
117
118    // Public interface for range update
119    void modify(int l, int r, int v) {
120        modify(l, r, v, root);
121    }
122
123    // Public interface for range query
124    int query(int l, int r) {
125        return query(l, r, root);
126    }
127};
128
129class Solution {
130public:
131    vector<int> fallingSquares(vector<vector<int>>& positions) {
132        vector<int> result;
133        SegmentTree* segTree = new SegmentTree();
134        int maxHeight = 0;
135      
136        for (auto& position : positions) {
137            int left = position[0];
138            int sideLength = position[1];
139            int right = left + sideLength - 1;
140          
141            // Query current maximum height in range [left, right]
142            int currentMaxHeight = segTree->query(left, right);
143          
144            // New height after dropping this square
145            int newHeight = currentMaxHeight + sideLength;
146          
147            // Update global maximum height
148            maxHeight = max(maxHeight, newHeight);
149            result.push_back(maxHeight);
150          
151            // Update the range [left, right] with new height
152            segTree->modify(left, right, newHeight);
153        }
154      
155        return result;
156    }
157};
158
1// Node structure for segment tree
2interface TreeNode {
3    left: TreeNode | null;
4    right: TreeNode | null;
5    leftBound: number;      // Left boundary of the segment
6    rightBound: number;     // Right boundary of the segment
7    midPoint: number;       // Midpoint of the segment
8    value: number;          // Maximum value in this segment
9    lazyTag: number;        // Lazy propagation tag for updates
10}
11
12// Create a new tree node
13function createNode(leftBound: number, rightBound: number): TreeNode {
14    return {
15        left: null,
16        right: null,
17        leftBound,
18        rightBound,
19        midPoint: (leftBound + rightBound) >> 1,
20        value: 0,
21        lazyTag: 0
22    };
23}
24
25// Root of the segment tree (covers range [1, 10^9])
26let segmentTreeRoot: TreeNode = createNode(1, 1e9);
27
28// Update the segment tree for range [left, right] with value
29function modify(left: number, right: number, value: number): void {
30    modifyNode(left, right, value, segmentTreeRoot);
31}
32
33// Recursive helper to modify a range in the segment tree
34function modifyNode(left: number, right: number, value: number, node: TreeNode): void {
35    // Invalid range
36    if (left > right) {
37        return;
38    }
39  
40    // Current node completely within update range
41    if (node.leftBound >= left && node.rightBound <= right) {
42        node.value = value;
43        node.lazyTag = value;
44        return;
45    }
46  
47    // Ensure children exist and push down lazy updates
48    pushdown(node);
49  
50    // Update left child if needed
51    if (left <= node.midPoint) {
52        modifyNode(left, right, value, node.left!);
53    }
54  
55    // Update right child if needed
56    if (right > node.midPoint) {
57        modifyNode(left, right, value, node.right!);
58    }
59  
60    // Update current node value based on children
61    pushup(node);
62}
63
64// Query the maximum value in range [left, right]
65function query(left: number, right: number): number {
66    return queryNode(left, right, segmentTreeRoot);
67}
68
69// Recursive helper to query a range in the segment tree
70function queryNode(left: number, right: number, node: TreeNode): number {
71    // Invalid range
72    if (left > right) {
73        return 0;
74    }
75  
76    // Current node completely within query range
77    if (node.leftBound >= left && node.rightBound <= right) {
78        return node.value;
79    }
80  
81    // Ensure children exist and push down lazy updates
82    pushdown(node);
83  
84    let maxValue = 0;
85  
86    // Query left child if needed
87    if (left <= node.midPoint) {
88        maxValue = Math.max(maxValue, queryNode(left, right, node.left!));
89    }
90  
91    // Query right child if needed
92    if (right > node.midPoint) {
93        maxValue = Math.max(maxValue, queryNode(left, right, node.right!));
94    }
95  
96    return maxValue;
97}
98
99// Update parent node value based on children values
100function pushup(node: TreeNode): void {
101    node.value = Math.max(node.left!.value, node.right!.value);
102}
103
104// Push down lazy updates to children and create children if needed
105function pushdown(node: TreeNode): void {
106    // Create left child if it doesn't exist
107    if (node.left === null) {
108        node.left = createNode(node.leftBound, node.midPoint);
109    }
110  
111    // Create right child if it doesn't exist
112    if (node.right === null) {
113        node.right = createNode(node.midPoint + 1, node.rightBound);
114    }
115  
116    // Propagate lazy tag to children if exists
117    if (node.lazyTag !== 0) {
118        const leftChild = node.left;
119        const rightChild = node.right;
120      
121        // Apply lazy tag to both children
122        leftChild.lazyTag = node.lazyTag;
123        rightChild.lazyTag = node.lazyTag;
124        leftChild.value = node.lazyTag;
125        rightChild.value = node.lazyTag;
126      
127        // Clear current node's lazy tag
128        node.lazyTag = 0;
129    }
130}
131
132// Main function to process falling squares
133function fallingSquares(positions: number[][]): number[] {
134    const result: number[] = [];
135  
136    // Reset segment tree for new test case
137    segmentTreeRoot = createNode(1, 1e9);
138  
139    let maxHeight = 0;
140  
141    // Process each falling square
142    for (const [leftPosition, sideLength] of positions) {
143        const rightPosition = leftPosition + sideLength - 1;
144      
145        // Find current maximum height in the range where square will fall
146        const currentHeight = query(leftPosition, rightPosition) + sideLength;
147      
148        // Update global maximum height
149        maxHeight = Math.max(maxHeight, currentHeight);
150        result.push(maxHeight);
151      
152        // Update the range with new height after square falls
153        modify(leftPosition, rightPosition, currentHeight);
154    }
155  
156    return result;
157}
158

Time and Space Complexity

Time Complexity: O(n log C) where n is the number of falling squares and C is the coordinate range (10^9 in this case).

For each of the n positions:

  • The query operation traverses the segment tree from root to leaf, creating nodes dynamically as needed. In the worst case, this takes O(log C) time since the tree height is bounded by log(10^9) ≈ 30.
  • The modify operation similarly traverses the tree with O(log C) time complexity.

Since we perform both operations for each position, the total time complexity is O(n × 2 log C) = O(n log C).

Note: While the reference answer states O(n log n), this is slightly imprecise for this dynamic segment tree implementation. The complexity depends on the coordinate range C rather than the number of elements n, since the tree spans coordinates from 1 to 10^9.

Space Complexity: O(n log C) in the worst case.

The segment tree uses dynamic node creation (lazy initialization). Nodes are only created when accessed during query or modify operations. For each position, we might create up to O(log C) nodes along the path from root to the relevant leaves. With n positions, the worst-case space complexity is O(n log C).

In practice, the space usage is often much less than the worst case because:

  • Nodes are shared between operations when they access overlapping ranges
  • The tree only materializes the portions that are actually accessed
  • Adjacent or overlapping squares may reuse existing nodes

The reference answer's O(n) space complexity would be more accurate for a compressed coordinate segment tree where coordinates are mapped to a smaller range [1, n].

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

Common Pitfalls

1. Incorrect Range Calculation for Square Boundaries

A common mistake is miscalculating the right boundary of a square. Given a square at position left with side length sideLength, developers often incorrectly calculate:

  • Wrong: right = left + sideLength
  • Correct: right = left + sideLength - 1

This is because if a square starts at position left and has width sideLength, it occupies positions [left, left + sideLength - 1] inclusive.

Example: A square at position 2 with side length 3 occupies positions [2, 3, 4], not [2, 3, 4, 5].

2. Not Handling Dynamic Node Creation Properly

When implementing a dynamic segment tree, forgetting to create child nodes before accessing them leads to NullPointerException or AttributeError. The pushdown() method must always create child nodes if they don't exist before propagating lazy values.

Problem Code:

def _push_down(self, node: Node) -> None:
    # Wrong: Directly accessing children without checking existence
    if node.lazy_tag:
        node.left_child.max_value = node.lazy_tag  # Error if left_child is None
        node.right_child.max_value = node.lazy_tag

Solution: Always create children first in pushdown().

3. Forgetting to Clear Lazy Tag After Propagation

After pushing down a lazy tag to children, failing to clear the parent's lazy tag causes incorrect results in subsequent operations.

Problem Code:

def _push_down(self, node: Node) -> None:
    if node.lazy_tag:
        node.left_child.lazy_tag = node.lazy_tag
        node.right_child.lazy_tag = node.lazy_tag
        # Forgot: node.lazy_tag = 0

This causes the same update to be applied multiple times.

4. Integer Overflow with Large Coordinates

The problem allows coordinates up to 10^9. Using incorrect data types or operations might cause overflow issues. While Python handles large integers automatically, in other languages like Java or C++, you need to be careful with intermediate calculations.

5. Incorrect Boundary Conditions in Recursive Calls

When deciding whether to recurse into left or right children, using wrong boundary comparisons causes missed updates or queries.

Problem Code:

# Wrong comparison operators
if left < node.mid:  # Should be <=
    self.modify(left, right, value, node.left_child)
if right >= node.mid:  # Should be >
    self.modify(left, right, value, node.right_child)

The correct conditions are:

  • Recurse left if: left <= node.mid
  • Recurse right if: right > node.mid

6. Not Maintaining Running Maximum Correctly

Some implementations forget to maintain a running maximum and instead just return the height of each individual square.

Problem Code:

for left_pos, side_length in positions:
    # ... calculate new_height
    result.append(new_height)  # Wrong: should append max(max_height, new_height)

The problem asks for the maximum height among ALL stacks after each drop, not just the height of the current stack.

7. Edge Case: Squares Landing Side-by-Side

Ensure that squares that only touch sides (no overlap) don't affect each other's landing height. A square at [1, 2] (covering positions 1-2) and another at [3, 2] (covering positions 3-4) should land independently on the ground if dropped in that order.

Testing Tip: Always test with cases like:

  • [[1, 2], [3, 2]] - Should return [2, 2] (both land on ground)
  • [[1, 2], [2, 3]] - Should return [2, 5] (second lands on first due to overlap at position 2)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal 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

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

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

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

Load More