3454. Separate Squares II

HardSegment TreeArrayBinary SearchSweep Line

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 2D integer array squares. Each squares[i] = [xi, yi, li] represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.

Find the minimum y-coordinate value of a horizontal line such that the total area covered by squares above the line equals the total area covered by squares below the line.

Answers within 10^-5 of the actual answer will be accepted.

Note: Squares may overlap. Overlapping areas should be counted only once in this version.

In other words, each square spans horizontally from xi to xi + li and vertically from yi to yi + li. Because squares can overlap, when computing the covered area you must count each region of the plane only once, regardless of how many squares cover it. Your goal is to choose a horizontal line y = k so that the union area lying strictly below the line is equal to the union area lying strictly above the line. Among all valid lines, you should return the smallest such k.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Ordered Set / Fenwick / Segment Tree?

This problem maps to Ordered Set / Fenwick / Segment Tree through a short path in the full flowchart.

The problem requires computing union area of overlapping squares using a sweep line with a segment tree for tracking active x-intervals.

Open in Flowchart

Intuition

The key observation is that the horizontal line we want is determined by the union area of all squares. If the total covered area (counting overlaps only once) is S, then we need a line y = k such that the union area below it equals S / 2. As we move a horizontal line upward from the bottom, the area below it increases monotonically from 0 to S, so there is exactly one position where the area below equals half. This monotonic growth is what lets us pinpoint the answer.

The challenge is computing the union area while accounting for overlaps. A natural way to handle overlapping rectangular regions is the sweep line technique. Imagine sweeping a horizontal line from the bottom to the top. At any given height, the squares that are currently "active" cover some set of intervals on the x-axis. The total length of this covered x-interval (union of intervals, overlaps counted once) tells us the width of the covered region at that height. Multiplying this width by the vertical distance the sweep line travels before the active set changes gives us an area slice.

The active set only changes at the top and bottom edges of squares. So we treat each square's bottom edge as an event that adds its x-interval to the active coverage, and each top edge as an event that removes it. By sorting all these events by their y coordinate and processing them in order, we can accumulate the union area piece by piece between consecutive event heights.

To efficiently track the total covered x-length as intervals are added and removed, we use a segment tree over the discretized x-coordinates. Each node maintains a cnt (how many active intervals fully cover this range) and a length (the covered length within this range). When cnt > 0, the whole range is covered; otherwise the covered length is the sum from its children. This lets us query the current covered width in O(1) at the root after each update.

The algorithm therefore runs in two passes. The first pass sweeps through all events to compute the total union area S, giving us the target S / 2. The second pass repeats the sweep, accumulating area slice by slice. As soon as adding the next slice would reach or exceed the target, we know the answer lies within that slice. Since the width stays constant during that interval, we can solve for the exact y by a simple linear interpolation: y0 + (target - area) / width, where width is the current covered x-length. Because the area grows monotonically, the first y reaching half is automatically the minimum valid line.

Pattern Learn more about Segment Tree and Binary Search patterns.

Solution Approach

We solve this problem using the Sweep Line algorithm combined with a Segment Tree for interval coverage. The implementation proceeds through the following steps.

1. Preprocess Event Points

For each square [x1, y1, l], we compute its top-right corner as x2 = x1 + l and y2 = y1 + l. We then generate two events:

A bottom edge event (y1, x1, x2, 1), where 1 means we add the interval [x1, x2] to the active coverage.
A top edge event (y2, x1, x2, -1), where -1 means we remove the interval.

We also collect every x1 and x2 into a set xs so we can discretize the x-coordinates later.

xs = set()
segs = []
for x1, y1, l in squares:
    x2, y2 = x1 + l, y1 + l
    xs.update([x1, x2])
    segs.append((y1, x1, x2, 1))
    segs.append((y2, x1, x2, -1))

2. Sort Event Points

We sort segs by y coordinate in ascending order, so the sweep line moves from bottom to top.

3. Build the Segment Tree

We sort the distinct x-coordinates into st and build a segment tree over them. Each Node keeps two pieces of information:

cnt: how many active intervals fully cover this node's range.
length: the total covered x-length within this node's range.

A dictionary d maps each x-coordinate to its index for quick lookup when updating the tree.

The crucial part is pushup, which recomputes a node's covered length:

If cnt > 0, the entire range is covered, so length = nums[r + 1] - nums[l].
Else if it's a leaf, length = 0.
Otherwise, length = left child length + right child length.

def pushup(self, u):
    if self.tr[u].cnt:
        self.tr[u].length = self.nums[self.tr[u].r + 1] - self.nums[self.tr[u].l]
    elif self.tr[u].l == self.tr[u].r:
        self.tr[u].length = 0
    else:
        self.tr[u].length = self.tr[u << 1].length + self.tr[u << 1 | 1].length

Note that we index intervals rather than points: the segment tree covers n - 1 unit intervals between n discretized coordinates. When updating the interval [x1, x2], we modify the range [d[x1], d[x2] - 1].

4. First Scan — Compute the Total Union Area

We sweep through all events in order. Between the previous sweep height y0 and the current event height y, the covered width is tree.length (the union x-length at the root). The area of this slice is (y - y0) * tree.length, which we add to the running area. Then we apply the current event by calling modify to add or remove its interval, and update y0.

area = 0
y0 = 0
for y, x1, x2, k in segs:
    area += (y - y0) * tree.length
    tree.modify(1, d[x1], d[x2] - 1, k)
    y0 = y

After this pass, area holds the total union area S, and the target becomes target = area / 2.

5. Second Scan — Locate the Answer

We repeat the sweep, but this time we look for the moment the accumulated area first reaches the target. For each slice, we compute its area t = (y - y0) * tree.length. If area + t >= target, the dividing line lies inside this slice. Since the width tree.length is constant throughout the slice, we interpolate linearly:

return y0 + (target - area) / tree.length

Otherwise, we add t to area, apply the event, and continue.

area = 0
y0 = 0
for y, x1, x2, k in segs:
    t = (y - y0) * tree.length
    if area + t >= target:
        return y0 + (target - area) / tree.length
    area += t
    tree.modify(1, d[x1], d[x2] - 1, k)
    y0 = y

Because the area below the sweep line grows monotonically, the first height reaching half the total area is exactly the minimum valid y, satisfying the problem's requirement.

Complexity Analysis

Let n be the number of squares. Sorting the events takes O(n log n), and each of the O(n) segment tree updates costs O(log n). Therefore the overall time complexity is O(n log n), and the space complexity is O(n) for storing the events and the segment tree.

Example Walkthrough

Consider two overlapping squares:

squares = [[0, 0, 2], [1, 1, 2]]

Square A: [0, 0, 2] → spans x from 0 to 2, y from 0 to 2.
Square B: [1, 1, 2] → spans x from 1 to 3, y from 1 to 3.

They overlap in the region x ∈ [1, 2], y ∈ [1, 2].

Step 1 — Preprocess Event Points

For each square we generate a bottom edge (+1) and a top edge (-1):

Event source	`(y, x1, x2, k)`
A bottom	`(0, 0, 2, +1)`
A top	`(2, 0, 2, -1)`
B bottom	`(1, 1, 3, +1)`
B top	`(3, 1, 3, -1)`

Collected x-coordinates: xs = {0, 1, 2, 3}.

Step 2 — Sort Events by y

segs = [(0, 0, 2, +1), (1, 1, 3, +1), (2, 0, 2, -1), (3, 1, 3, -1)]

Step 3 — Build the Segment Tree

Discretized coordinates: st = [0, 1, 2, 3], with mapping d = {0:0, 1:1, 2:2, 3:3}. The tree covers the unit intervals [0,1], [1,2], [2,3] (3 intervals between 4 points).

Step 4 — First Scan: Compute Total Union Area

Start with area = 0, y0 = 0.

Event	slice = `(y - y0) * width`	running `area`	action	new `width`
`(0, 0, 2, +1)`	`(0-0) * 0 = 0`	`0`	add `[0,2]` → cover intervals `[0,1],[1,2]`	`2`
`(1, 1, 3, +1)`	`(1-0) * 2 = 2`	`2`	add `[1,3]` → also cover `[2,3]`	`3`
`(2, 0, 2, -1)`	`(2-1) * 3 = 3`	`5`	remove `[0,2]` → `[0,1]` off, `[1,2]` still on via B	`2`
`(3, 1, 3, -1)`	`(3-2) * 2 = 2`	`7`	remove `[1,3]` → all off	`0`

Total union area S = 7. Target = S / 2 = 3.5.

Sanity check: A has area 4, B has area 4, overlap is 1, so union = 4 + 4 - 1 = 7. ✓

Step 5 — Second Scan: Locate the Answer

Reset area = 0, y0 = 0. We look for the slice where accumulated area first reaches 3.5.

Event	`t = (y - y0) * width`	`area + t` vs target `3.5`	decision
`(0, 0, 2, +1)`	`(0-0)*0 = 0`	`0 < 3.5`	add slice (area=0), apply, y0=0
`(1, 1, 3, +1)`	`(1-0)*2 = 2`	`0 + 2 = 2 < 3.5`	add slice (area=2), apply, y0=1
`(2, 0, 2, -1)`	`(2-1)*3 = 3`	`2 + 3 = 5 ≥ 3.5`	answer lies in this slice

At this point the line is inside the interval y ∈ [1, 2] where the constant width is 3. We interpolate:

y = y0 + (target - area) / width
  = 1 + (3.5 - 2) / 3
  = 1 + 1.5 / 3
  = 1.5

Result

The minimum y-coordinate is 1.5.

Verification: Below y = 1.5 — square A contributes the region y ∈ [0, 1.5] over x ∈ [0, 2] (area 3), and square B contributes y ∈ [1, 1.5] over x ∈ [2, 3] (the part of B not already counted, area 0.5), totaling 3.5. The area above also equals 3.5. ✓

Solution Implementation

1from typing import List
2
3
4class Node:
5    """A node in the segment tree, representing an interval over compressed x-coordinates."""
6
7    __slots__ = ("left", "right", "count", "length")
8
9    def __init__(self):
10        # Boundaries of the interval (indices into the compressed coordinate array)
11        self.left = self.right = 0
12        # How many active segments fully cover this interval
13        self.count = 0
14        # Total covered length of the x-axis within this interval
15        self.length = 0
16
17
18class SegmentTree:
19    """Segment tree used to track the total covered length on the x-axis during a sweep."""
20
21    def __init__(self, nums: List[int]):
22        # nums holds the sorted, unique x-coordinates (compressed boundaries)
23        n = len(nums) - 1
24        self.nums = nums
25        # Allocate 4n nodes (a safe upper bound for a segment tree)
26        self.tree = [Node() for _ in range(n << 2)]
27        self.build(1, 0, n - 1)
28
29    def build(self, u: int, left: int, right: int) -> None:
30        """Recursively build the tree over the index range [left, right]."""
31        self.tree[u].left, self.tree[u].right = left, right
32        if left != right:
33            mid = (left + right) >> 1
34            self.build(u << 1, left, mid)
35            self.build(u << 1 | 1, mid + 1, right)
36
37    def modify(self, u: int, left: int, right: int, k: int) -> None:
38        """Add k to the coverage count of every elementary interval inside [left, right]."""
39        if self.tree[u].left >= left and self.tree[u].right <= right:
40            # Current node is fully inside the target range
41            self.tree[u].count += k
42        else:
43            mid = (self.tree[u].left + self.tree[u].right) >> 1
44            if left <= mid:
45                self.modify(u << 1, left, right, k)
46            if right > mid:
47                self.modify(u << 1 | 1, left, right, k)
48        self.push_up(u)
49
50    def push_up(self, u: int) -> None:
51        """Recalculate the covered length of node u from its state and children."""
52        if self.tree[u].count:
53            # This interval is fully covered, so its length spans the whole interval
54            self.tree[u].length = (
55                self.nums[self.tree[u].right + 1] - self.nums[self.tree[u].left]
56            )
57        elif self.tree[u].left == self.tree[u].right:
58            # Leaf node with no coverage contributes nothing
59            self.tree[u].length = 0
60        else:
61            # Otherwise, the covered length is the sum from both children
62            self.tree[u].length = (
63                self.tree[u << 1].length + self.tree[u << 1 | 1].length
64            )
65
66    @property
67    def length(self) -> int:
68        """Total covered length on the x-axis (stored at the root)."""
69        return self.tree[1].length
70
71
72class Solution:
73    def separateSquares(self, squares: List[List[int]]) -> float:
74        xs = set()
75        segments = []
76        # Build horizontal edge events for the sweep along the y-axis
77        for x1, y1, side in squares:
78            x2, y2 = x1 + side, y1 + side
79            xs.update([x1, x2])
80            # Bottom edge opens coverage (+1); top edge closes it (-1)
81            segments.append((y1, x1, x2, 1))
82            segments.append((y2, x1, x2, -1))
83        # Sort events by y-coordinate to sweep upward
84        segments.sort()
85
86        # Compress x-coordinates and map each coordinate to its index
87        sorted_xs = sorted(xs)
88        tree = SegmentTree(sorted_xs)
89        index = {x: i for i, x in enumerate(sorted_xs)}
90
91        # First pass: compute the total area covered by all squares
92        area = 0
93        prev_y = 0
94        for y, x1, x2, k in segments:
95            # Accumulate area = covered width * height since the last event
96            area += (y - prev_y) * tree.length
97            tree.modify(1, index[x1], index[x2] - 1, k)
98            prev_y = y
99
100        # We want to find the y at which the lower portion equals half the area
101        target = area / 2
102
103        # Second pass: replay the sweep until the accumulated area reaches the target
104        area = 0
105        prev_y = 0
106        for y, x1, x2, k in segments:
107            strip = (y - prev_y) * tree.length
108            if area + strip >= target:
109                # The dividing line lies within this strip;
110                # interpolate the exact y-position using the current width
111                return prev_y + (target - area) / tree.length
112            area += strip
113            tree.modify(1, index[x1], index[x2] - 1, k)
114            prev_y = y
115        return 0
116

1/**
2 * Represents a single node in the segment tree.
3 * Each node covers a range of compressed x-interval indices.
4 */
5class Node {
6    int left;   // Left boundary index of this node's interval (in compressed coordinates)
7    int right;  // Right boundary index of this node's interval (in compressed coordinates)
8    int count;  // How many active rectangles fully cover this interval
9    int length; // Total covered length on the x-axis within this interval
10}
11
12/**
13 * A segment tree built over compressed x-coordinates.
14 * It is used to maintain the total covered length on the x-axis
15 * as horizontal scan-line segments are added and removed.
16 */
17class SegmentTree {
18    private Node[] tree;  // Array-based representation of the segment tree
19    private int[] nums;   // Sorted, unique x-coordinates used for coordinate compression
20
21    /**
22     * Builds the segment tree from the given sorted unique x-coordinates.
23     *
24     * @param nums sorted unique x-coordinates
25     */
26    public SegmentTree(int[] nums) {
27        this.nums = nums;
28        int n = nums.length - 1; // Number of elementary intervals between coordinates
29        tree = new Node[n << 2];
30        for (int i = 0; i < tree.length; ++i) {
31            tree[i] = new Node();
32        }
33        build(1, 0, n - 1);
34    }
35
36    /**
37     * Recursively constructs the tree structure for the range [l, r].
38     *
39     * @param u current node index
40     * @param l left boundary of the interval
41     * @param r right boundary of the interval
42     */
43    private void build(int u, int l, int r) {
44        tree[u].left = l;
45        tree[u].right = r;
46        if (l != r) {
47            int mid = (l + r) >> 1;
48            build(u << 1, l, mid);
49            build(u << 1 | 1, mid + 1, r);
50        }
51    }
52
53    /**
54     * Adds k to the coverage count over the range [l, r].
55     * k is +1 when a segment enters and -1 when it leaves.
56     *
57     * @param u current node index
58     * @param l left boundary of the update range
59     * @param r right boundary of the update range
60     * @param k delta to apply to the coverage count
61     */
62    public void modify(int u, int l, int r, int k) {
63        if (tree[u].left >= l && tree[u].right <= r) {
64            // Current node is fully inside the update range
65            tree[u].count += k;
66        } else {
67            int mid = (tree[u].left + tree[u].right) >> 1;
68            if (l <= mid) {
69                modify(u << 1, l, r, k);
70            }
71            if (r > mid) {
72                modify(u << 1 | 1, l, r, k);
73            }
74        }
75        pushup(u);
76    }
77
78    /**
79     * Recomputes the covered length of node u from its current state
80     * and, if necessary, from its children.
81     *
82     * @param u current node index
83     */
84    private void pushup(int u) {
85        if (tree[u].count > 0) {
86            // Entire interval is covered by at least one rectangle
87            tree[u].length = nums[tree[u].right + 1] - nums[tree[u].left];
88        } else if (tree[u].left == tree[u].right) {
89            // Leaf node with no coverage
90            tree[u].length = 0;
91        } else {
92            // Combine the covered lengths of both children
93            tree[u].length = tree[u << 1].length + tree[u << 1 | 1].length;
94        }
95    }
96
97    /**
98     * Returns the total covered length on the x-axis at the root.
99     *
100     * @return covered length at the current scan-line position
101     */
102    public int query() {
103        return tree[1].length;
104    }
105}
106
107class Solution {
108    /**
109     * Finds the horizontal line y = answer that splits the total area of all
110     * squares into two equal halves, using a sweep line plus segment tree.
111     *
112     * @param squares each square given as [x, y, sideLength]
113     * @return the y-coordinate of the dividing line
114     */
115    public double separateSquares(int[][] squares) {
116        Set<Integer> xs = new HashSet<>();      // Distinct x-coordinates for compression
117        List<int[]> segs = new ArrayList<>();   // Horizontal scan-line events
118
119        // Convert each square into an entering and a leaving horizontal segment.
120        for (int[] sq : squares) {
121            int x1 = sq[0], y1 = sq[1], l = sq[2];
122            int x2 = x1 + l, y2 = y1 + l;
123            xs.add(x1);
124            xs.add(x2);
125            // Event format: [y, x1, x2, type], type = +1 (enter), -1 (leave)
126            segs.add(new int[] {y1, x1, x2, 1});
127            segs.add(new int[] {y2, x1, x2, -1});
128        }
129
130        // Process events from bottom to top.
131        segs.sort(Comparator.comparingInt(a -> a[0]));
132
133        // Collect and sort the unique x-coordinates.
134        int[] st = new int[xs.size()];
135        int i = 0;
136        for (int x : xs) {
137            st[i++] = x;
138        }
139        Arrays.sort(st);
140
141        SegmentTree tree = new SegmentTree(st);
142
143        // Map each x-coordinate to its compressed index.
144        Map<Integer, Integer> d = new HashMap<>(st.length);
145        for (i = 0; i < st.length; i++) {
146            d.put(st[i], i);
147        }
148
149        // First pass: compute the total area covered by all squares.
150        double area = 0.0;
151        int y0 = 0;
152        for (int[] s : segs) {
153            int y = s[0], x1 = s[1], x2 = s[2], k = s[3];
154            // Add the slab between the previous and current y levels.
155            area += (double) (y - y0) * tree.query();
156            tree.modify(1, d.get(x1), d.get(x2) - 1, k);
157            y0 = y;
158        }
159
160        double target = area / 2.0; // Half of the total area
161
162        // Second pass: sweep again to locate where the accumulated area reaches the target.
163        area = 0.0;
164        y0 = 0;
165        for (int[] s : segs) {
166            int y = s[0], x1 = s[1], x2 = s[2], k = s[3];
167            double t = (double) (y - y0) * tree.query();
168            if (area + t >= target) {
169                // The dividing line lies within the current slab; interpolate.
170                return y0 + (target - area) / tree.query();
171            }
172            area += t;
173            tree.modify(1, d.get(x1), d.get(x2) - 1, k);
174            y0 = y;
175        }
176
177        return 0.0;
178    }
179}
180

1// A node in the segment tree representing a coverage interval over compressed x-coordinates.
2struct Node {
3    int left = 0;    // left index bound of this node (in compressed coordinate space)
4    int right = 0;   // right index bound of this node
5    int count = 0;   // how many intervals fully cover this node (lazy coverage counter)
6    int length = 0;  // total covered length within this node's range
7};
8
9class SegmentTree {
10private:
11    vector<Node> tree;  // 1-indexed segment tree storage
12    vector<int> nums;   // compressed (sorted, unique) x-coordinates
13
14    // Recursively build the tree structure over index range [l, r].
15    void build(int u, int l, int r) {
16        tree[u].left = l;
17        tree[u].right = r;
18        if (l != r) {
19            int mid = (l + r) >> 1;
20            build(u << 1, l, mid);
21            build(u << 1 | 1, mid + 1, r);
22        }
23    }
24
25    // Recompute the covered length of node u based on its coverage count and children.
26    void pushUp(int u) {
27        if (tree[u].count > 0) {
28            // Fully covered: actual length spans real coordinates.
29            tree[u].length = nums[tree[u].right + 1] - nums[tree[u].left];
30        } else if (tree[u].left == tree[u].right) {
31            // Leaf node with no coverage contributes nothing.
32            tree[u].length = 0;
33        } else {
34            // Otherwise sum the covered lengths of both children.
35            tree[u].length = tree[u << 1].length + tree[u << 1 | 1].length;
36        }
37    }
38
39public:
40    // Construct the tree from sorted unique x-coordinates.
41    // Indices range over [0, n-1] where each index i maps the gap [nums[i], nums[i+1]].
42    SegmentTree(const vector<int>& nums)
43        : nums(nums) {
44        int n = (int) nums.size() - 1;
45        tree.assign(n << 2, Node());
46        build(1, 0, n - 1);
47    }
48
49    // Add k to the coverage count over the index interval [l, r], then update lengths.
50    void modify(int u, int l, int r, int k) {
51        if (tree[u].left >= l && tree[u].right <= r) {
52            // Current node is fully inside the target interval.
53            tree[u].count += k;
54        } else {
55            int mid = (tree[u].left + tree[u].right) >> 1;
56            if (l <= mid) modify(u << 1, l, r, k);
57            if (r > mid) modify(u << 1 | 1, l, r, k);
58        }
59        pushUp(u);
60    }
61
62    // Return the currently covered length across the whole coordinate range.
63    int query() const {
64        return tree[1].length;
65    }
66};
67
68class Solution {
69public:
70    double separateSquares(vector<vector<int>>& squares) {
71        set<int> xs;                       // unique x-coordinates for compression
72        vector<array<int, 4>> segs;        // events: {y, x1, x2, type}
73
74        // Convert each square into two horizontal scanline events.
75        for (auto& sq : squares) {
76            int x1 = sq[0], y1 = sq[1], l = sq[2];
77            int x2 = x1 + l, y2 = y1 + l;
78            xs.insert(x1);
79            xs.insert(x2);
80            segs.push_back({y1, x1, x2, 1});   // bottom edge: coverage begins
81            segs.push_back({y2, x1, x2, -1});  // top edge: coverage ends
82        }
83
84        // Sort events from bottom to top by y-coordinate.
85        sort(segs.begin(), segs.end(), [](const auto& a, const auto& b) {
86            return a[0] < b[0];
87        });
88
89        // Build the compressed x-coordinate list.
90        vector<int> st;
91        st.reserve(xs.size());
92        for (int x : xs) st.push_back(x);
93
94        SegmentTree tree(st);
95
96        // Map each real x-coordinate to its compressed index.
97        unordered_map<int, int> d;
98        d.reserve(st.size() * 2);
99        for (int i = 0; i < (int) st.size(); i++) d[st[i]] = i;
100
101        // First pass: accumulate the total area of the union of all squares.
102        double area = 0.0;
103        int y0 = 0;
104        for (auto& s : segs) {
105            int y = s[0], x1 = s[1], x2 = s[2], k = s[3];
106            // Area contributed by the slab between y0 and y equals width * height.
107            area += (double) (y - y0) * tree.query();
108            tree.modify(1, d[x1], d[x2] - 1, k);
109            y0 = y;
110        }
111
112        // Target is half of the total covered area.
113        double target = area / 2.0;
114
115        // Second pass: scan again to locate the y where accumulated area hits target.
116        area = 0.0;
117        y0 = 0;
118        for (auto& s : segs) {
119            int y = s[0], x1 = s[1], x2 = s[2], k = s[3];
120            double t = (double) (y - y0) * tree.query();
121            if (area + t >= target) {
122                // The split line lies within this slab; interpolate the exact y.
123                return y0 + (target - area) / tree.query();
124            }
125            area += t;
126            tree.modify(1, d[x1], d[x2] - 1, k);
127            y0 = y;
128        }
129
130        return 0.0;
131    }
132};
133

1// Node structure for the segment tree, holding interval bounds,
2// coverage count, and the covered length within this node.
3interface SegNode {
4    l: number; // left index in compressed coordinates
5    r: number; // right index in compressed coordinates
6    cnt: number; // how many intervals fully cover this node
7    length: number; // total covered length within this node's range
8}
9
10// Global segment tree storage and the compressed coordinate array.
11let tr: SegNode[];
12let nums: number[];
13
14// Initialize the segment tree over the compressed x-coordinates.
15function buildTree(values: number[]): void {
16    nums = values;
17    const n = values.length - 1;
18    tr = Array.from({ length: n << 2 }, () => ({
19        l: 0,
20        r: 0,
21        cnt: 0,
22        length: 0,
23    }));
24    build(1, 0, n - 1);
25}
26
27// Recursively build the tree, assigning index ranges to each node.
28function build(u: number, l: number, r: number): void {
29    tr[u].l = l;
30    tr[u].r = r;
31    if (l !== r) {
32        const mid = (l + r) >> 1;
33        build(u << 1, l, mid);
34        build((u << 1) | 1, mid + 1, r);
35    }
36}
37
38// Add k to the coverage count over the index range [l, r].
39function modify(u: number, l: number, r: number, k: number): void {
40    if (l > r) return;
41    if (tr[u].l >= l && tr[u].r <= r) {
42        // Current node fully inside the target range.
43        tr[u].cnt += k;
44    } else {
45        const mid = (tr[u].l + tr[u].r) >> 1;
46        if (l <= mid) modify(u << 1, l, r, k);
47        if (r > mid) modify((u << 1) | 1, l, r, k);
48    }
49    pushup(u);
50}
51
52// Recompute the covered length of node u based on its coverage count
53// and its children.
54function pushup(u: number): void {
55    if (tr[u].cnt > 0) {
56        // Fully covered: span the actual coordinate distance.
57        tr[u].length = nums[tr[u].r + 1] - nums[tr[u].l];
58    } else if (tr[u].l === tr[u].r) {
59        // Leaf with no coverage contributes nothing.
60        tr[u].length = 0;
61    } else {
62        // Otherwise sum the children's covered lengths.
63        tr[u].length = tr[u << 1].length + tr[(u << 1) | 1].length;
64    }
65}
66
67// The total covered length is stored at the root.
68function query(): number {
69    return tr[1].length;
70}
71
72// Find a horizontal line y such that the squares' total area
73// is split into two equal halves below and above the line.
74function separateSquares(squares: number[][]): number {
75    const xsSet = new Set<number>();
76    const segs: number[][] = [];
77
78    // Build sweep-line events: bottom edge (+1), top edge (-1).
79    for (const [x1, y1, l] of squares) {
80        const x2 = x1 + l;
81        const y2 = y1 + l;
82        xsSet.add(x1);
83        xsSet.add(x2);
84        segs.push([y1, x1, x2, 1]);
85        segs.push([y2, x1, x2, -1]);
86    }
87
88    // Process events from bottom to top.
89    segs.sort((a, b) => a[0] - b[0]);
90
91    // Compress and sort distinct x-coordinates.
92    const xs = Array.from(xsSet);
93    xs.sort((a, b) => a - b);
94
95    // Build the segment tree over the compressed x-coordinates.
96    buildTree(xs);
97
98    // Map each x-coordinate to its compressed index.
99    const d = new Map<number, number>();
100    for (let i = 0; i < xs.length; i++) {
101        d.set(xs[i], i);
102    }
103
104    // First pass: compute the total covered area.
105    let area = 0;
106    let y0 = 0;
107    for (const [y, x1, x2, k] of segs) {
108        area += (y - y0) * query();
109        modify(1, d.get(x1)!, d.get(x2)! - 1, k);
110        y0 = y;
111    }
112
113    // We want to find the y where accumulated area reaches half.
114    const target = area / 2;
115
116    // Reset state and replay the sweep to locate the splitting line.
117    buildTree(xs);
118    area = 0;
119    y0 = 0;
120    for (const [y, x1, x2, k] of segs) {
121        const curLen = query();
122        const t = (y - y0) * curLen;
123        if (area + t >= target) {
124            // The target is reached within this horizontal strip.
125            return y0 + (target - area) / curLen;
126        }
127        area += t;
128        modify(1, d.get(x1)!, d.get(x2)! - 1, k);
129        y0 = y;
130    }
131
132    return 0;
133}
134

Time and Space Complexity

Time Complexity: O(n × log n)

Let n be the number of squares. The analysis proceeds as follows:

Coordinate collection and setup: For each square, we add 2 x-coordinates to the set xs and create 2 segments. This yields O(n) coordinates and O(n) segments.
Sorting:
- Sorting segs (containing 2n segments) takes O(n × log n).
- Sorting xs into st (containing up to 2n coordinates) takes O(n × log n).
Segment Tree construction: The build method recursively constructs a tree over up to 2n discretized x-intervals, creating O(n) nodes, so it takes O(n).
Sweep line with segment tree updates: There are two sweep passes, each iterating over the 2n segments. For each segment, a modify operation is performed on the segment tree, costing O(log n) per call (the recursion depth is bounded by the tree height). Each sweep thus costs O(n × log n).

Combining all parts, the dominant terms are the sorting and the sweep-line updates, giving an overall time complexity of O(n × log n).

Space Complexity: O(n)

The space usage breaks down as follows:

The set xs and sorted list st store up to 2n x-coordinates, requiring O(n) space.
The list segs stores 2n segments, requiring O(n) space.
The dictionary d maps coordinates to indices, using O(n) space.
The segment tree allocates n << 2 (i.e., 4n) Node objects, requiring O(n) space. The recursion stack during build and modify has depth O(log n).

Therefore, the total space complexity is O(n), where n is the number of squares.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the "Index Intervals, Not Points" Convention in the Segment Tree

The single most common mistake in this sweep-line + segment-tree pattern is mixing up coordinate points with the elementary intervals between them.

When you have n distinct x-coordinates stored in sorted_xs, they define only n - 1 elementary intervals. The segment tree must be built over indices [0, n - 2], not [0, n - 1]:

n = len(nums) - 1          # number of intervals, NOT number of points
self.build(1, 0, n - 1)    # indices 0 .. n-2

A natural but wrong instinct is to write self.build(1, 0, len(nums) - 1), which creates a leaf for the last coordinate that has no interval to its right. This corrupts every push_up that reads nums[right + 1], causing an index-out-of-range error or silently wrong lengths.

Tightly coupled to this is the update range. When you add a square spanning [x1, x2], you must modify:

tree.modify(1, index[x1], index[x2] - 1, k)   # note the  - 1

Why - 1? The interval [x1, x2] covers the elementary intervals starting at index[x1] up to but not including the one at index[x2]. The elementary interval with index i represents the physical span [nums[i], nums[i+1]]. So the last elementary interval inside [x1, x2] has index index[x2] - 1.

Verification trick: Pick two adjacent coordinates a < b with one square covering exactly [a, b]. After the +1 event, tree.length should equal b - a. If it equals 0 or throws, your indexing is off by one.

Pitfall 2: Using a Standard Lazy-Propagation Segment Tree (Pushdown)

Many people reach for the textbook lazy-propagation segment tree for range updates. That is the wrong tool here. The classic "area of union of rectangles" segment tree relies on a special property:

Every modify is balanced — every +1 (bottom edge) is eventually matched by a -1 (top edge) on the exact same interval [x1, x2].

Because of this balance, you never push the count down to children. Instead, count stays on the node where the range fully matches, and push_up recomputes length purely from the local count and the children's length:

def push_up(self, u):
    if self.tree[u].count:           # this whole interval is covered
        self.tree[u].length = nums[right + 1] - nums[left]
    elif leaf:
        self.tree[u].length = 0
    else:
        self.tree[u].length = left_child.length + right_child.length

If you wrongly introduce push_down, a partial -1 could "leak" a removal into children that were never individually marked, breaking the count and producing negative or nonsensical lengths. Do not pushdown; only pushup.

Pitfall 3: Misreading "Union Area" vs. "Summed Area" (the Overlap Trap)

This problem's note explicitly states overlapping regions count once. A frequent error is computing area as the simple sum of li² over all squares, or treating each square independently in the sweep. Both ignore overlap.

The correct slice area is:

area += (y - prev_y) * tree.length

where tree.length is the union width at the current sweep height — guaranteed by the segment tree's coverage logic. If you instead multiplied height by a sum of active interval widths, overlapping squares at the same height would be double-counted, inflating the total and shifting the answer.

Contrast: There is a sibling problem where overlaps are counted multiple times. For that version you'd track total summed width, not union width. Always confirm which variant you're solving.

Pitfall 4: Assuming `prev_y = 0` Is a Safe Starting Height

The code initializes prev_y = 0. This is only correct because the problem guarantees coordinates are non-negative integers (yi >= 0). The very first event has tree.length == 0 (no intervals active yet), so the slice (first_y - 0) * 0 = 0 contributes nothing — and the off-by-zero start is harmless.

However, if the constraints ever allowed negative y-coordinates, starting at 0 would be a latent bug: you'd compute area over [0, first_y] with the wrong sign or skip the region below zero entirely.

Robust fix: Anchor prev_y to the first event's y-value, which always has zero active coverage:

prev_y = segments[0][0]    # bottom-most edge; coverage is empty before this

This makes the logic correct regardless of the coordinate sign.

Pitfall 5: Division by Zero During Interpolation

The final interpolation step divides by tree.length:

return prev_y + (target - area) / tree.length

If the answer happens to land exactly at a y-level where the sweep enters a strip with tree.length == 0 (a vertical gap with no covered region), this divides by zero. With a valid problem (target > 0 and squares present) the target is reached while tree.length > 0, but defensive code should guard it:

if tree.length > 0 and area + strip >= target:
    return prev_y + (target - area) / tree.length

Skipping zero-width strips ensures the division is always well-defined and the returned k is the minimum valid line — since accumulated area only grows on strips with positive width, the first qualifying strip yields the smallest k.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering