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.
Which of the following uses divide and conquer strategy?
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
1e9in 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
lfor the left boundary,rfor the right boundary,vfor the value at this node (height),midas the midpoint of the interval, andaddfor lazy propagation updates. -
Lazy Propagation: When updating an interval, the
modifymethod applies the lazy propagation technique. If an update is pending (indicated byaddbeing 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
querymethod 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 themodifymethod 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
mxvariable, which keeps track of the overall tallest stack after each drop. At each iteration,mxis appended to the answer listans. -
Returning the Result: After processing all the squares in the
positionslist, the answer listanscontaining 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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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
861class 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}
1281class 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};
1261type 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}
92Depth first search can be used to find whether two components in a graph are connected.
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
modifyandquerypotentially 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 to10^9). -
Modify Operation: For each of the
nposition updates (wherenis the length ofpositionsarray), themodifyfunction 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
queryand onemodify, making the total time complexity: O(n * logN), where N is the upper limit of the range (10^9in 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 formodifyorqueryoperations. Given that the depth of the tree is logarithmic with respect to N and eachmodifyandqueryonly 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
modifyandqueryoperation 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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.