Generated by Codex with GPT-5

Quick facts

What the problem is really asking

This problem looks geometric, but the core idea is much simpler than it first appears.

The task is to place a horizontal line y = cut so that:

  • the total square area below the line
  • equals the total square area above the line

and among all such lines, return the smallest y value.

The most important detail is the note about overlap: if two squares overlap, that overlapping region is counted once for each square. That means the squares do not interact in any complicated way. The total area below the line is just the sum of each square’s individual contribution below the line.

That observation removes almost all of the 2D complexity.

The key simplification: x does not matter

Each square is given as [x, y, l], but the x coordinate is actually irrelevant for this problem.

Why? Because the cut is horizontal. For a single square:

  • if the line is at or below the square’s bottom edge, that square contributes 0 area below the line
  • if the line is at or above the square’s top edge, that square contributes its full area l * l
  • if the line passes through the square, the part below the line is a rectangle with: height = cut - y width = l

So one square contributes:

0                         if cut <= y
l * (cut - y)             if y < cut < y + l
l * l                     if cut >= y + l

Notice what is missing from that formula: x.

That is the breakthrough. The whole problem reduces to a 1D continuous area function over the vertical axis.

The intended solution: binary search on the cut height

Define:

area_below(cut) = total counted area strictly below or on the horizontal line y = cut

From the single-square formula above, area_below(cut) has three useful properties:

  1. It is continuous.
  2. It is monotone nondecreasing.
  3. It can be evaluated in O(n) time by summing the contribution from every square.

That makes binary search a natural fit.

The target area is:

total_area / 2

If area_below(mid) < total_area / 2, the line is too low, so the answer must be above mid.

If area_below(mid) >= total_area / 2, then mid is already high enough, and the minimum valid answer is at or below mid.

That gives a standard “first true” binary search on a real-valued answer:

  • search between the smallest square bottom and the largest square top
  • repeatedly evaluate the area below the midpoint
  • keep the left half or right half depending on whether the midpoint has reached half the total area yet

Because the answer only needs to be within 1e-5, a fixed number of iterations is enough. Around 60 to 70 iterations is comfortably safe for the constraint range here.

How to derive this in an interview

A clean way to derive the solution is:

  1. Ignore the overlap issue at first and inspect one square.
  2. Write the area-below contribution for that one square as a function of the cut height.
  3. Notice that overlaps are counted multiple times, so the total is just the sum of those per-square functions.
  4. Notice that the summed function is continuous and monotone.
  5. Conclude that the smallest cut giving half the area can be found with binary search.

That path is much stronger than starting with “I think this is binary search,” because it shows where the monotonicity comes from.

Python solution

from typing import List, Sequence


class SquareAreaDivider:
    """
    Find the smallest horizontal cut where the counted area below the line
    equals half of the total counted area.

    Overlaps are counted once per square, exactly as the problem states.
    """

    def __init__(self, squares: Sequence[Sequence[int]]) -> None:
        self.squares = squares
        self.lower_bound = min(square[1] for square in squares)
        self.upper_bound = max(square[1] + square[2] for square in squares)
        self.target_area = sum(square[2] * square[2] for square in squares) / 2.0

    def find_lowest_balancing_cut(self) -> float:
        low = float(self.lower_bound)
        high = float(self.upper_bound)

        # Maintain the invariant:
        # area_below(low) < target_area <= area_below(high)
        #
        # Returning `high` after a first-true style binary search gives the
        # smallest cut whose area-below has reached at least half the total.
        for _ in range(70):
            mid = (low + high) / 2.0
            if self._area_below_cut(mid) < self.target_area:
                low = mid
            else:
                high = mid

        return high

    def _area_below_cut(self, cut_y: float) -> float:
        total_area_below = 0.0

        for _, bottom_y, side_length in self.squares:
            square_bottom = float(bottom_y)
            square_side = float(side_length)
            square_top = square_bottom + square_side

            # The cut is below the square, so this square contributes nothing.
            if cut_y <= square_bottom:
                continue

            # The cut is above the square, so the full square is below it.
            if cut_y >= square_top:
                total_area_below += square_side * square_side
                continue

            # The cut passes through the square. Only a rectangle of height
            # (cut_y - bottom_y) lies below the line.
            total_area_below += (cut_y - square_bottom) * square_side

        return total_area_below


class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        divider = SquareAreaDivider(squares)
        return divider.find_lowest_balancing_cut()

Why this works

For every square, the counted area below the cut is a continuous function that never decreases as the cut moves upward. Summing those functions preserves both continuity and monotonicity, so the total area-below function is also continuous and monotone.

That matters because the problem asks for the minimum cut where the lower area equals half the total. For a continuous monotone function, that is exactly the leftmost point where the function reaches the target value. The binary search keeps narrowing the range around that leftmost valid cut.

Each midpoint check scans all squares once, so one check costs O(n) time. The number of checks is constant for practical purposes because the required numeric precision is fixed, so the total runtime is O(n * log(precision_range)), and the extra space is O(1) beyond the input.

Interview follow-ups

Yes. A more geometric solution treats the total area-below function as a piecewise-linear curve. Each square adds slope +l starting at its bottom edge and slope -l starting at its top edge. If those slope-change events are sorted by y, the algorithm can sweep upward, accumulate area segment by segment, and directly solve for the exact point where the accumulated area reaches half the total.

That approach works because between any two consecutive event heights, the slope is constant, so the area grows linearly in that interval. Once the target lies inside one such interval, the answer is just a simple linear equation. The tradeoff is complexity: the sweep is elegant and exact, but it is harder to discover quickly in an interview. Binary search is usually the better first answer because it is simpler and fully accepted.

Why does returning the leftmost valid cut matter, and how does the binary search guarantee it?

The statement does not ask for just any balancing line. It asks for the minimum y coordinate that works. Sometimes there can be an interval of valid answers rather than a single point. For example, if all square area below the line reaches exactly half and then no square is intersected for a while, every cut in that flat region is valid, but only the left edge of that interval is correct.

The binary search handles this by searching for the first cut where area_below(cut) >= total_area / 2. If a midpoint is already valid, the search keeps the left half instead of stopping. That “first true” pattern is exactly what makes the final answer the smallest valid cut, not just a nearby one.

What if the shapes were rectangles instead of squares?

Almost nothing changes in the main idea. For a rectangle with width w, bottom y, and height h, the area below a cut is still 0, w * (cut - y), or w * h depending on where the line falls. The x-coordinate is still irrelevant because the cut is horizontal and overlaps would still be counted independently.

So the same binary-search framework works immediately. The only change is the per-shape contribution formula. The complexity stays the same: O(n) work per midpoint and constant extra space.

What changes if overlapping area should be counted only once?

Then the problem becomes fundamentally harder, because the squares are no longer independent. The overlapping region cannot simply be counted once per square anymore, so summing per-square contributions would overcount. In that version, the x-coordinates suddenly matter because the true area below the line depends on the union of horizontal coverage, not just on vertical heights.

At that point, a correct solution usually needs a real computational-geometry sweep: maintain the union width of active x-intervals while sweeping over y-level events, often with coordinate compression and a segment tree. That is a realistic interviewer follow-up because it turns the problem into something much closer to the harder sequel problem. The tradeoff is clear: the original problem is simple because overlap is counted multiple times, while the union-area version requires substantially heavier machinery.