Falling Squares — LeetCode 699 Python Solution
HardSegment TreeArrayOrdered Set
- Problem
- #699
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Related problems
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.