#699

Hard

LeetCode Problem Workspace

Falling Squares

Solve Falling Squares by efficiently computing maximum stack heights using arrays with segment tree optimization techniques.

array segment tree ordered set

Problem Statement

You are given several squares dropped one by one onto the X-axis of a 2D plane. Each square is defined by its left edge and side length in an array positions where positions[i] = [lefti, sideLengthi]. Squares fall downward until they land on the X-axis or on top of previously dropped squares without sliding past edges.

After each drop, the square freezes in place, and you need to return an array representing the tallest height after every drop. Squares that only touch the side of another square do not contribute to stacking height. Constraints include 1 <= positions.length <= 1000, 1 <= lefti <= 10^8, and 1 <= sideLengthi <= 10^6.

Examples

Example 1

Input: positions = [[1,2],[2,3],[6,1]]

Output: [2,5,5]

After the first drop, the tallest stack is square 1 with a height of 2. After the second drop, the tallest stack is squares 1 and 2 with a height of 5. After the third drop, the tallest stack is still squares 1 and 2 with a height of 5. Thus, we return an answer of [2, 5, 5].

Example 2

Input: positions = [[100,100],[200,100]]

Output: [100,100]

After the first drop, the tallest stack is square 1 with a height of 100. After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100. Thus, we return an answer of [100, 100]. Note that square 2 only brushes the right side of square 1, which does not count as landing on it.

Constraints

1 <= positions.length <= 1000
1 <= lefti <= 108
1 <= sideLengthi <= 106

Solution Approach

Coordinate Compression

Map all left and right edges of squares to a smaller index range to efficiently manage large coordinate values. This allows segment tree or ordered set operations to run in O(log N) time rather than depending on potentially huge X-axis values.

Segment Tree for Range Maximum

Use a segment tree to track maximum heights in the current covered intervals. For each square, query the maximum height in its landing interval and update the tree with the new height after placing the square.

Iterative Drop Simulation

Process squares in order. For each square, compute its landing height using the segment tree, update the maximum stack height, and append it to the result array. This captures the tallest stack dynamically as each square lands.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

Time complexity is O(N log N) because each square involves a log N query and update on the segment tree across N squares. Space complexity is O(N) for storing the compressed coordinates and segment tree nodes.

What Interviewers Usually Probe

Check if candidates handle very large X coordinates efficiently.
Look for proper use of range maximum queries using a segment tree or ordered set.
Watch for mistakes in determining whether squares actually stack or just touch sides.

Common Pitfalls or Variants

Common pitfalls

Failing to compress coordinates, causing memory overflow for large lefti values.
Mistaking side contact for stacking, resulting in incorrect height calculation.
Updating heights incorrectly across overlapping intervals, which produces wrong maximum heights.

Follow-up variants

Falling rectangles instead of squares, where width varies for each drop.
Allowing squares to slide horizontally if they touch a side, introducing physics-based landing rules.
Computing total area covered by all stacked squares after each drop instead of just maximum height.

FAQ

What data structure is optimal for solving Falling Squares?

A segment tree or ordered set is optimal for efficiently tracking maximum heights in intervals as squares fall.

Do squares stacking only by side contact count?

No, only squares that fully land on top of another contribute to the height; side contact is ignored.

How do you handle very large X coordinates in Falling Squares?

Coordinate compression maps large positions into a manageable range for segment tree or ordered set operations.

Why use a segment tree instead of simple array scanning?

A segment tree reduces query and update time to O(log N), avoiding slow O(N^2) scans for overlapping intervals.

Can this pattern be applied to rectangles instead of squares?

Yes, the array plus segment tree pattern generalizes to rectangles where widths and heights vary per drop.

terminal

Solution

Solution 1: Segment Tree

According to the problem description, we need to maintain a set of intervals that support modification and query operations. In this case, we can use a segment tree to solve the problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

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 ans

Continue Practicing

#729 my calendar i #731 my calendar ii #850 rectangle area ii