Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

When overlaps count only once, summing square areas is incorrect. Sweep a horizontal line upward instead. Between consecutive square-edge heights, the union's horizontal width is constant, so the area of that strip is its width times its height.

Approach

Create an add event at each square's bottom and a remove event at its top. Compress all horizontal endpoints and maintain their elementary intervals in a segment tree. Each node stores an active coverage count and covered length: a positive count covers its whole span; otherwise use its children's lengths, or zero at a leaf.

Sort events by height. Before applying each event, add the current union width times the height since the previous event to the total area. Same-height events contribute no intervening area. At the end, all intervals have been removed, leaving the tree empty for a second sweep.

Accumulate strip areas again until reaching half the total. Within that strip, return previousHeight + remainingArea / unionWidth. Processing strips upward and returning at the first crossing gives the smallest balancing height, including when a later gap has zero width.

class SegmentTree():
    def __init__(self, xs: List[int]):
        self.xs = xs
        self.n = len(xs) - 1
        self.count = [0] * (4 * self.n)
        self.covered = [0] * (4 * self.n)

    def update(self, sql, sqr, l, r, op, pos):
        if sqr <= self.xs[l] or sql >= self.xs[r + 1]:
            return  # no overlap
        if sql <= self.xs[l] and sqr >= self.xs[r + 1]:
            self.count[pos] += op  # full overlap
        else:
            # partial overlap
            mid = (l + r) // 2
            self.update(sql, sqr, l, mid, op, pos * 2 + 1)
            self.update(sql, sqr, mid + 1, r, op, pos * 2 + 2)
        if self.count[pos] > 0:
            self.covered[pos] = self.xs[r + 1] - self.xs[l]
        elif l == r:
            self.covered[pos] = 0
        else:
            self.covered[pos] = self.covered[pos * 2 + 1] + self.covered[pos * 2 + 2]

    def query(self):
        return self.covered[0]

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        xs = set()
        events = []

        for x, y, size in squares:
            xs.add(x)
            xs.add(x + size)
            events.append([y, x, x + size, 1])  # add segment
            events.append([y + size, x, x + size, -1])  # remove segment

        xs = sorted(xs)
        events.sort()
        st = SegmentTree(xs)

        # get total area
        total_area = 0
        py = events[0][0]

        for y, sql, sqr, op in events:
            total_area += st.query() * (y - py)
            st.update(sql, sqr, 0, st.n - 1, op, 0)
            py = y

        # get smallest y for first half of total area
        acc_area = 0
        py = events[0][0]

        for y, sql, sqr, op in events:
            comb_width = st.query()
            curr_area = comb_width * (y - py)
            if acc_area + curr_area >= total_area / 2:
                # acc_area + (comb_width * last_gap_to_mid) = total_area / 2
                # last_gap_to_mid = ((total_area / 2) - acc_area) / comb_width
                # smallest_y = py + last_gap_to_mid
                return py + ((total_area / 2) - acc_area) / comb_width
            acc_area += curr_area
            st.update(sql, sqr, 0, st.n - 1, op, 0)
            py = y

Complexity analysis

Let n = squares.length. Time: O(n log n). Auxiliary space: O(n) for compressed coordinates, events, and the segment tree.