699. Falling Squares

Problem Description

In this problem, we are simulating a scenario where squares with equal side lengths are being dropped one by one onto the X-axis of a 2D plane. Each square has a specific side length and is aligned to the X-axis from a given left edge position.

When a square is dropped, it falls straight down until it either lands on another square or reaches the X-axis. The key point to note is that squares cannot land on edges or corners — they must land on top of another square or the ground.

After placing each square, we need to note the height of the tallest stack formed by these squares. The objective is to return a list that records the maximum height of the stack after each square is placed.

This problem has the underlying mechanism of intervals and range updates since each square falls into a range along the X-axis and contributes to the height increment within that range.

Intuition

To achieve an efficient solution for the given problem, we may consider using a Segment Tree, a powerful data structure that helps perform range queries and updates in logarithmic time.

The intuition behind using a Segment Tree in this problem is as follows:

Height Queries and Updates: As we are dropping squares, we need to continuously keep track of the current height at each position on the X-axis. Segment trees enable us to inquire and update the height for a range (reflecting the sides of the square) efficiently.
Maintaining Max Heights: Segment trees support maintaining the maximum value within a segment. When a new square is dropped, it could potentially land on multiple previously dropped squares. We need to determine the maximum height across the span where the new square will land and add the side length of the new square to this height.
Lazy Propagation: We also need to use lazy propagation, a technique used with segment trees to defer and propagate updates only when necessary. This is useful in our problem because we don't need the exact height of each point on the X-axis at all times, but only the maximum height within a range when we are about to place a new square.

The provided solution code defines a SegmentTree class with methods to modify and query segments, as well as utility methods to push updates up (to parent nodes) and down (to child nodes).

When a square is dropped, we first query the segment tree for the maximum height within the range that the square will cover. We then update the heights within that range to be equal to the maximum height found plus the side length of the new square.

With each update, we also record the maximum height found so far in the overall process and append it to the ans array. The ans array thus built up will contain the height of the tallest stack of squares after each drop, which is exactly what the problem asks us to return.

In summary, the intuition is to use the properties of a Segment Tree to tackle the problem's demands for range queries and updates efficiently so that the falling squares problem can be solved effectively.

Learn more about Segment Tree patterns.

Solution Approach

The problem is approached using a data structure known as a "Segment Tree". This tree is binary in nature and is used for storing intervals or segments. It allows querying of interval or segment properties (like minimum, maximum, sum, etc.) efficiently and also handling modifications of these segments.

Here's how the Segment Tree is leveraged in the given solution:

Segment Tree Initialization: The segment tree is initialized with a vast range (1 to 1e9 in this case, which is an over-estimate of the x-axis range) to encompass all potential square positions.
Node Structure: Each node of the tree represents an interval with attributes l for the left boundary, r for the right boundary, v for the value at this node (height), mid as the midpoint of the interval, and add for lazy propagation updates.
Lazy Propagation: When updating an interval, the modify method applies the lazy propagation technique. If an update is pending (indicated by add being nonzero), it is propagated down to child nodes before any further querying or updating to ensure the updates are applied at the right time, ensuring efficiency.
Querying: When a square is dropped, we query the segment tree within the range of the square's left edge and right edge (calculated using left edge plus width). The query method retrieves the maximum height within this range.
Updating: After querying, we obtain the current maximum height where the square is to be placed. We need to update the segment such that the height of all positions within the range of the square is now h, the queried height plus the square's width. This is done using the modify method again, ensuring future queries within this interval will have the updated height.
Recording Heights: After updating the tree with a new square's height, the maximum height among all the squares (including the newly placed one) is updated in the mx variable, which keeps track of the overall tallest stack after each drop. At each iteration, mx is appended to the answer list ans.
Returning the Result: After processing all the squares in the positions list, the answer list ans containing the maximum stack height after each square drop is returned as the final solution.

Here's why the Segment Tree is the chosen data structure for this problem:

It handles dynamic updates and queries efficiently, making it highly suitable for problems that involve real-time changes and a need to maintain aggregate information.
Lazy propagation augments the segment tree's performance by deferring updates until necessary, thus optimizing the number of operations needed.

Considering this, the given solution initializes a segment tree (with ample range), queries heights, updates intervals, applies lazy updates, and records the maximum stack height efficiently at each drop of the square, ultimately building and returning an array of maximum heights corresponding to each square drop.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume we have a set of squares with the following side lengths and positions to be dropped: [(2,3), (2,6), (2,5)]. The first value in each tuple is the side length and the second is the left edge position on the X-axis.

Initialize the Segment Tree: A segment tree is initialized that can cover the entire range of X-axis positions we expect to encounter. In practice, it's initialized to a large range, but for our example, let's simplify the interval to a smaller range that fits our needs.
Drop the First Square (2,3): The first square has a side length of 2 and starts at position 3. We query the segment tree for the maximum height between positions 3 and 4 (inclusive). Since no square has been dropped yet, the maximum height is 0. We then update the tree, setting the height of positions 3 and 4 to 2. The maximum stack height is now 2.
Drop the Second Square (2,6): The next square also has a side length of 2 but starts at position 6. We query between positions 6 and 7 and get a max height of 0. So, we update positions 6 and 7 to a height of 2. The maximum stack height is still 2 since these squares don't stack.
Drop the Third Square (2,5): The third square has a side length of 2 and starts at position 5. We query between positions 5 and 6 and find that position 6 already has a height of 2. Consequently, we update positions 5 and 6 to a new height of 4 (since the square will land on the one that's already at position 6). The maximum stack height is updated to 4.
Recording Heights: After each drop, we record the maximum stack height. So, after dropping the three squares, our recorded heights are [2, 2, 4].
Returning the Result: The final result is an array of the maximum heights recorded after each square drop: [2, 2, 4].

This example utilizes the key steps in the solution approach, focusing on how the segment tree queries and updates intervals to keep track of the heights of the squares and how lazy propagation optimizes these updates. By maintaining this structure and process, we can efficiently solve the problem of recording the maximum stack height for any number of square drops.

Solution Implementation

1class Node:
2    def __init__(self, start, end):
3        self.left = None  # left child of the interval
4        self.right = None  # right child of the interval
5        self.start = start  # start index of the interval
6        self.end = end  # end index of the interval
7        self.mid = (start + end) >> 1  # middle index for splitting intervals
8        self.value = 0  # sum value of the current interval
9        self.add = 0  # lazy propagation value to add to children nodes
10
11
12class SegmentTree:
13    def __init__(self):
14        # Initialize the segment tree with a very large end index, representing positions
15        self.root = Node(1, int(1e9))
16
17    def modify(self, start, end, value, node=None):
18        # Update the segment tree in the range [start, end] with value 'value'
19        if start > end:
20            return
21        if node is None:
22            node = self.root
23        # If node's interval is completely within [start, end], update directly
24        if node.start >= start and node.end <= end:
25            node.value = value
26            node.add = value
27            return
28        self.pushdown(node)
29        # If intervals overlap, move down the tree
30        if start <= node.mid:
31            self.modify(start, end, value, node.left)
32        if end > node.mid:
33            self.modify(start, end, value, node.right)
34        self.pushup(node)
35
36    def query(self, start, end, node=None):
37        # Query the maximum value in the range [start, end]
38        if start > end:
39            return 0
40        if node is None:
41            node = self.root
42        if node.start >= start and node.end <= end:
43            return node.value
44        self.pushdown(node)
45        max_value = 0
46        if start <= node.mid:
47            max_value = max(max_value, self.query(start, end, node.left))
48        if end > node.mid:
49            max_value = max(max_value, self.query(start, end, node.right))
50        return max_value
51
52    def pushup(self, node):
53        # Recalculates the value of internal node after modifications to its children
54        node.value = max(node.left.value, node.right.value)
55
56    def pushdown(self, node):
57        # Propagates updates to children nodes and creates them if they don't exist
58        if node.left is None:
59            node.left = Node(node.start, node.mid)
60        if node.right is None:
61            node.right = Node(node.mid + 1, node.end)
62        if node.add:
63            node.left.value = node.add
64            node.right.value = node.add
65            node.left.add = node.add
66            node.right.add = node.add
67            node.add = 0
68
69
70class Solution:
71    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
72        max_height = 0  # Track the maximum height so far
73        result = []  # Store the resulting heights
74        tree = SegmentTree()  # Initialize a new Segment Tree
75
76        for left, size in positions:
77            right = left + size - 1
78            # Find current max height within [left, right] and add size to it
79            height = tree.query(left, right) + size
80            max_height = max(max_height, height)
81            result.append(max_height)
82            # Update the height in the segment tree
83            tree.modify(left, right, height)
84
85        return result
86

1class Node {
2    Node left;
3    Node right;
4    int start;
5    int end;
6    int mid;
7    int value; 
8    int add; // Mark to indicate updates that need to be propagated down
9
10    // Constructor for Node, initializes a node with given start and end indices
11    public Node(int start, int end) {
12        this.start = start;
13        this.end = end;
14        this.mid = (start + end) >> 1; // Compute the mid point for segment division
15    }
16}
17
18class SegmentTree {
19    private Node root = new Node(1, (int) 1e9); // Initialize the root covering range [1, 1e9]
20
21    // Empty constructor for SegmentTree
22    public SegmentTree() {
23    }
24
25    // Modify range [l, r], updating with value v
26    public void modify(int l, int r, int v) {
27        modify(l, r, v, root); // Start modification from the root node
28    }
29
30    // Modify range [l, r] with value v starting from a given node
31    private void modify(int l, int r, int v, Node node) {
32        if (l > r) {
33            return;
34        }
35        // If current node's range is completely within update range
36        if (node.start >= l && node.end <= r) {
37            node.value = v;
38            node.add = v; // Set the add mark for lazy updates
39            return;
40        }
41        pushdown(node); // Ensure correct propagation of lazy updates
42
43        // Recursively modify the left and/or right children
44        if (l <= node.mid) {
45            modify(l, r, v, node.left);
46        }
47        if (r > node.mid) {
48            modify(l, r, v, node.right);
49        }
50        pushup(node); // Push up the updates after modifying children
51    }
52
53    // Query range [l, r]
54    public int query(int l, int r) {
55        return query(l, r, root); // Start query from the root node
56    }
57
58    // Query range [l, r] starting from a given node
59    private int query(int l, int r, Node node) {
60        if (l > r) {
61            return 0;
62        }
63        // If current node's range is completely within query range
64        if (node.start >= l && node.end <= r) {
65            return node.value;
66        }
67        pushdown(node); // Ensure propagation of lazy updates
68
69        // Query left and/or right children and return the max value found
70        int maxVal = 0;
71        if (l <= node.mid) {
72            maxVal = Math.max(maxVal, query(l, r, node.left));
73        }
74        if (r > node.mid) {
75            maxVal = Math.max(maxVal, query(l, r, node.right));
76        }
77        return maxVal;
78    }
79
80    // Push up the value from children to the parent
81    private void pushup(Node node) {
82        node.value = Math.max(node.left.value, node.right.value);
83    }
84
85    // Push down the lazy propagation marks to the children
86    private void pushdown(Node node) {
87        // Lazy initialization of children nodes
88        if (node.left == null) {
89            node.left = new Node(node.start, node.mid);
90        }
91        if (node.right == null) {
92            node.right = new Node(node.mid + 1, node.end);
93        }
94        // If there are updates to be propagated
95        if (node.add != 0) {
96            Node left = node.left, right = node.right;
97            left.add = node.add;
98            right.add = node.add;
99            left.value = node.add;
100            right.value = node.add;
101            node.add = 0; // Clear the mark after pushing down the updates
102        }
103    }
104}
105
106public class Solution {
107    // Method to get the height of falling squares
108    public List<Integer> fallingSquares(int[][] positions) {
109        List<Integer> result = new ArrayList<>();
110        SegmentTree tree = new SegmentTree();
111        int maxHeight = 0;
112
113        // Iterate through each square position
114        for (int[] position : positions) {
115            int start = position[0];
116            int width = position[1];
117            int end = start + width - 1;
118            // Get the max height for the range and update it with the new height
119            int height = tree.query(start, end) + width;
120            maxHeight = Math.max(maxHeight, height); // Update the max height
121            result.add(maxHeight);
122            tree.modify(start, end, height); // Modify the segment tree with new height
123        }
124
125        return result; // Return the list of max heights after each square is dropped
126    }
127}
128

1class Node {
2public:
3    Node* left;  // Pointer to left child
4    Node* right; // Pointer to right child
5    int leftBound;  // Left boundary of the segment
6    int rightBound; // Right boundary of the segment
7    int mid;        // Middle of the segment
8    int value;      // Value stored in the segment
9    int lazy;       // Lazy propagation value
10
11    // Constructor for a tree node representing a range [l, r]
12    Node(int l, int r) {
13        this->leftBound = l;
14        this->rightBound = r;
15        this->mid = (l + r) / 2;
16        this->left = this->right = nullptr;
17        value = lazy = 0;
18    }
19};
20
21class SegmentTree {
22private:
23    Node* root; // Root of the segment tree
24
25public:
26    // Constructor initializes the segment tree with a large range
27    SegmentTree() {
28        root = new Node(1, 1000000000); // Using 1e9 for simplicity
29    }
30
31    void modify(int l, int r, int v) {
32        modify(l, r, v, root);
33    }
34
35    // Recursively modifies the range [l, r] of the segment tree with a new value v
36    void modify(int l, int r, int v, Node* node) {
37        if (l > r) return;
38
39        // If the current range is completely within [l, r], update it
40        if (node->leftBound >= l && node->rightBound <= r) {
41            node->value = v;
42            node->lazy = v;
43            return;
44        }
45
46        // Propagate the lazy updates if necessary 
47        pushdown(node);
48
49        // Recursively update the left and/or right child
50        if (l <= node->mid) modify(l, r, v, node->left);
51        if (r > node->mid) modify(l, r, v, node->right);
52
53        // After updating children, push the updated information up the tree
54        pushup(node);
55    }
56
57    int query(int l, int r) {
58        return query(l, r, root);
59    }
60
61    // Recursively queries the maximum value in the range [l, r]
62    int query(int l, int r, Node* node) {
63        if (l > r) return 0;
64
65        // If the current range is completely within [l, r], return its value
66        if (node->leftBound >= l && node->rightBound <= r) return node->value;
67
68        // Propagate the lazy updates if necessary 
69        pushdown(node);
70
71        int maxVal = 0; // Variable to store the maximum value found
72
73        // Recursively query the left and/or right child
74        if (l <= node->mid) maxVal = std::max(maxVal, query(l, r, node->left));
75        if (r > node->mid) maxVal = std::max(maxVal, query(l, r, node->right));
76      
77        return maxVal;
78    }
79
80    // Pushes up the maximum values from the children to the parent node
81    void pushup(Node* node) {
82        node->value = std::max(node->left->value, node->right->value);
83    }
84
85    // Propagates the lazy updates to the children and resets the lazy value
86    void pushdown(Node* node) {
87        if (!node->left) node->left = new Node(node->leftBound, node->mid);
88        if (!node->right) node->right = new Node(node->mid + 1, node->rightBound);
89        if (node->lazy) {
90            Node* leftChild = node->left;
91            Node* rightChild = node->right;
92            leftChild->value = node->lazy;
93            rightChild->value = node->lazy;
94            leftChild->lazy = node->lazy;
95            rightChild->lazy = node->lazy;
96            node->lazy = 0;
97        }
98    }
99};
100
101class Solution {
102public:
103    vector<int> fallingSquares(vector<vector<int>>& positions) {
104        vector<int> heights;
105        SegmentTree tree;
106        int maxHeight = 0;
107
108        // Process each square
109        for (auto& position : positions) {
110            int left = position[0];
111            int width = position[1];
112            int right = left + width - 1;
113            // Query the current height and add the square's height to it
114            int height = tree.query(left, right) + width;
115            // Update the maximum height seen so far
116            maxHeight = std::max(maxHeight, height);
117            // Add the maximum height to the result list
118            heights.push_back(maxHeight);
119            // Modify the segment tree with the new height
120            tree.modify(left, right, height);
121        }
122
123        return heights;
124    }
125};
126

1type TreeNode = {
2  left: TreeNode | null;
3  right: TreeNode | null;
4  leftBound: number;
5  rightBound: number;
6  mid: number;
7  value: number;
8  lazy: number;
9};
10
11function createNode(l: number, r: number): TreeNode {
12  return {
13    left: null,
14    right: null,
15    leftBound: l,
16    rightBound: r,
17    mid: Math.floor((l + r) / 2),
18    value: 0,
19    lazy: 0
20  };
21}
22
23let root: TreeNode = createNode(1, 1000000000); // Using 1e9 for simplicity
24
25function pushdown(node: TreeNode) {
26  if (!node.left) node.left = createNode(node.leftBound, node.mid);
27  if (!node.right) node.right = createNode(node.mid + 1, node.rightBound);
28  if (node.lazy) {
29    let leftChild = node.left;
30    let rightChild = node.right;
31    leftChild.value = node.lazy;
32    rightChild.value = node.lazy;
33    leftChild.lazy = node.lazy;
34    rightChild.lazy = node.lazy;
35    node.lazy = 0;
36  }
37}
38
39function pushup(node: TreeNode) {
40  node.value = Math.max((node.left ? node.left.value : 0), (node.right ? node.right.value : 0));
41}
42
43function modify(l: number, r: number, v: number, node: TreeNode = root) {
44  if (l > r) return;
45
46  if (node.leftBound >= l && node.rightBound <= r) {
47    node.value = v;
48    node.lazy = v;
49    return;
50  }
51
52  pushdown(node);
53
54  if (l <= node.mid) modify(l, r, v, node.left);
55  if (r > node.mid) modify(l, r, v, node.right);
56
57  pushup(node);
58}
59
60function query(l: number, r: number, node: TreeNode = root): number {
61  if (l > r) return 0;
62
63  if (node.leftBound >= l && node.rightBound <= r) return node.value;
64
65  pushdown(node);
66
67  let maxVal: number = 0;
68
69  if (l <= node.mid && node.left) maxVal = Math.max(maxVal, query(l, r, node.left));
70  if (r > node.mid && node.right) maxVal = Math.max(maxVal, query(l, r, node.right));
71
72  return maxVal;
73}
74
75function fallingSquares(positions: number[][]): number[] {
76  let heights: number[] = [];
77  let maxHeight: number = 0;
78
79  for (let position of positions) {
80    let left: number = position[0];
81    let width: number = position[1];
82    let right: number = left + width - 1;
83
84    let height: number = query(left, right) + width;
85    maxHeight = Math.max(maxHeight, height);
86    heights.push(maxHeight);
87    modify(left, right, height);
88  }
89
90  return heights;
91}
92

Time and Space Complexity

The given code implements a Segment Tree to solve a problem where segments realize a 'fall' and the height of each segment after the fall is updated. To do this, the code defines methods for modifying and querying the Segment Tree:

modify: Updates the segment tree with the new value over a range [l, r].
query: Retrieves maximum value within a range [l, r].

Time Complexity

Construction of Segment Tree: The Segment Tree is lazily constructed. Each modify and query potentially leads to construction of a segment tree node. Since it's a binary tree, at most O(logN) nodes are touched for each operation, where N is the range of segments (from 1 to 10^9).
Modify Operation: For each of the n position updates (where n is the length of positions array), the modify function may traverse the tree up to a depth of O(logN), and each operation along this path is O(1). Hence, for each modify operation, the time complexity is O(logN).
Query Operation: Analogous to modify, each query takes O(logN) time, because it traverses the tree to a depth of O(logN) with O(1) work at each node.
Total Time Complexity: For each position, we perform one query and one modify, making the total time complexity: O(n * logN), where N is the upper limit of the range (10^9 in this case).

Space Complexity

Segment Tree Nodes: The Segment Tree is a binary tree that could theoretically have a node for each element in the range [1, 10^9]. However, because of lazy construction, we only create nodes when they are needed for modify or query operations. Given that the depth of the tree is logarithmic with respect to N and each modify and query only instantiates the necessary path down the tree, at most (2 * n) nodes exist at any one time due to the falling squares (each square could potentially add two new ranges), making the space complexity O(n).
Call Stack: Each modify and query operation causes recursion up to O(logN) depth.
Total Space Complexity: The combination of space used by the segment tree nodeList and the recursion call stack give a total space complexity of O(n + logN). Since n could be larger than logN, the dominant term is O(n). Hence, the overall space complexity is O(n).

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

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

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls