HardNo. 0699
Falling Squares — LeetCode 699 Python Solution
- Topics
- Segment Tree, Array, Ordered Set
- Reading time
- 13 min
- Source
- leetcode.com
The problem
There are several squares being dropped onto the X-axis of a 2D plane. You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
Example
- Input
- positions = [[1,2],[2,3],[6,1]]
- Output
- [2,5,5]
- Explanation
- After the first drop, the tallest stack is square 1 with a height of 2.
Python solution
class Node:
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) >> 1
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e9))
def modify(self, l, r, v, node=None):
if l > r:
return
if node is None:
node = self.root
if node.l >= l and node.r <= r:
node.v = v
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if l > r:
return 0
if node is None:
node = self.root
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v = max(v, self.query(l, r, node.left))
if r > node.mid:
v = max(v, self.query(l, r, node.right))
return v
def pushup(self, node):
node.v = max(node.left.v, node.right.v)
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add:
node.left.v = node.add
node.right.v = node.add
node.left.add = node.add
node.right.add = node.add
node.add = 0
class Solution:
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
ans = []
mx = 0
tree = SegmentTree()
for l, w in positions:
r = l + w - 1
h = tree.query(l, r) + w
mx = max(mx, h)
ans.append(mx)
tree.modify(l, r, h)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0850 | Rectangle Area II | Hard |
| 2569 | Handling Sum Queries After Update | Hard |
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
Frequently asked questions
- How hard is LeetCode 699. Falling Squares?
LeetCode 699. Falling Squares is rated Hard on LeetCode.
- What is the time complexity of LeetCode 699. Falling Squares?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 699. Falling Squares?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 699. Falling Squares cover?
LeetCode 699. Falling Squares is tagged Segment Tree, Array and Ordered Set on LeetCode.