Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

As a horizontal line moves upward, the total area below it never decreases and the total above never increases. Overlaps count separately in this version, so each square's contribution can be added independently. The monotone area difference supports binary search.

Approach

Search between the smallest square bottom and the largest square top. For a candidate height, calculate each square's area above and below: a square wholly on one side contributes its full area there, while a crossed square contributes its width times the corresponding vertical portion. Sum above - below.

If that difference is positive, move the lower search bound upward. Otherwise move the upper bound down, including when the areas are already equal. Continue until the bounds differ by at most 1e-5, then return the upper bound. On equality, continuing toward lower heights also handles an interval of balancing lines caused by an empty vertical gap.

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        def check(target):
            top = 0
            bot = 0

            for x, y, size in squares:
                top_limit = y + size
                bot_limit = y
                if bot_limit <= target <= top_limit:
                    top += (top_limit - target) * size
                    bot += (target - bot_limit) * size
                elif target < bot_limit:
                    top += size ** 2
                elif target > top_limit:
                    bot += size ** 2

            return top - bot # areas delta

        l = inf
        h = 0
        for x, y, size in squares:
            l = min(l, y)
            h = max(h, y + size)

        while h - l > 10**(-5):
            mid = l + (h - l) / 2
            if check(mid) > 0:
                l = mid
            else:
                h = mid

        return h

Complexity analysis

Let n = squares.length, R be the searched y-range, and epsilon = 1e-5. Time: O(n * log(R / epsilon)). Auxiliary space: O(1).