Separate Squares I - Solution & Explanation

Problem Overview: You are given several axis-aligned squares on a 2D plane. The task is to find a horizontal line y = k such that the total area of all squares below the line equals the total area above it. Overlapping regions are counted multiple times because each square contributes independently.

Approach 1: Linear Scan over Candidate Heights (Brute Force) (Time: O(n * R), Space: O(1))

The most direct idea is to test many candidate values for the horizontal split line. For each candidate y, iterate through every square and compute how much of that square lies below the line. If the square's bottom is yi and side length is l, the contributed area below the line is 0 if y <= yi, l * l if y >= yi + l, and l * (y - yi) if the line cuts through the square. Summing these contributions gives the area below the line. Compare it with half of the total square area and adjust the candidate height. This approach demonstrates the core geometry but scanning many possible heights is inefficient when coordinates are large.

Approach 2: Binary Search on the Split Line (Time: O(n log R), Space: O(1))

The key observation is monotonicity. As the horizontal line moves upward, the area below it never decreases. This makes the function suitable for binary search. First compute the total area of all squares. The target is totalArea / 2. Search between the smallest bottom edge and the largest top edge among all squares. For each midpoint mid, iterate through the array and compute the partial area contributed by each square below mid. If the accumulated area is smaller than half, move the search range upward; otherwise move it downward. After enough iterations (or once the precision threshold is reached), the midpoint approximates the required separating line.

This works because each square contributes area as a piecewise linear function of y. Summing these functions across the array preserves monotonic growth, which guarantees binary search convergence. The computation inside each step is a simple clamp operation using min and max.

Recommended for interviews: The binary search approach is what interviewers expect. Recognizing the monotonic relationship between the line height and accumulated area is the core insight. Starting with the brute-force reasoning shows you understand the geometry, but applying binary search to reduce the search space demonstrates algorithmic maturity and leads to the optimal O(n log R) solution.