Problem Statement in English

You’re given a 2D plane with several squares placed on it. Each square is defined by its bottom-left corner coordinates $(x, y)$ and its side length $l$. The squares may overlap with each other.

You need to return the y-coordinate of a horizontal line that divides the plane into two regions such that the area covered by the squares above the line is equal to the area covered by the squares below the line. If there are multiple such lines, return any one of them. The answer should be accurate within $10^{-5}$.

Approach

This was my first continuous binary search problem. The idea is to binary search on the y-coordinate that separates the squares into two equal areas. But here we need to possibly have a decimal value for the y-coordinate, so we do a continuous binary search.

Imagine that as $y$ tends towards $\text{inf}$, we’re submerging all the squares, and as $y$ tends towards $-\text{inf}$, none of the squares are submerged. We need to find the point where half the area is submerged.

We binary search through the various possible y-coordinates, and for each mid-point, we calculate the area of the squares below that y-coordinate. If the area is less than half the total area, we need to increase our y-coordinate, otherwise we decrease it.

So here low is initialized to the minimum y-coordinate of the squares, and high is initialized to the maximum y-coordinate plus the side length of the square (this gives us the highest possible y-coordinate found in any square). This is the range we will binary search through.

So to submerge more, we need to move low higher, and to submerge less, we need to move high lower.

We then perform binary search for a fixed number of iterations (60 in this case) to ensure precision. To figure out how many iterations are needed, we can use the formula $\frac{range}{2^k} \leq \epsilon$, where k is the number of iterations, and $\epsilon$ is the desired precision. But $60$ is a good enough number to ensure precision within $10^{-5}$.

Solution in Python


class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        low, high, total_area = float('inf'), float('-inf'), 0

        for x, y, l in squares:
            total_area += l*l
            low = min(low, y)
            high = max(high, y+l)
        
        target_area = total_area / 2.0

        for i in range(60):
            mid = (low+high) / 2.0

            curr_area = 0
            for _, y, l in squares:
                curr_y = max(0, min(l, mid-y))
                curr_area += l*curr_y
            
            if curr_area < target_area:
                low = mid
            else:
                high = mid

        return mid

Complexity

  • Time: $O(n \log m)$
    Where n is the number of squares and m is the range of y-coordinates.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

Mistakes I Made

I had to look this one up :(

And we are done.