Separate Squares I

Separate Squares I

What is this problem about?

The Separate Squares I interview question gives you a list of axis-aligned squares on a 2D plane, each defined by their bottom-left corner and side length. Find the horizontal line y = c that minimizes the absolute difference between the total area above the line and the total area below. The answer should be precise to a certain decimal tolerance. This is a binary search on a continuous value problem.

Why is this asked in interviews?

Amazon, Google, and Bloomberg ask this problem because it applies binary search to a continuous domain — a critical skill for optimization problems in geometry, computer graphics, and resource partitioning. The "find the balancing line" concept models problems in fairness allocation, halving area, and geometric median computation. It evaluates whether candidates can define a monotone condition over real numbers and apply binary search accordingly.

Algorithmic pattern used

The pattern is binary search on the answer (continuous). Define a function area_below(y) that computes the total area of all squares below height y (clipped at y). This function is monotonically increasing in y. Binary search between y_min (bottom of lowest square) and y_max (top of highest square) for the y where area_below(y) = total_area / 2. For each candidate y, compute the intersection area of each square with the region below y and sum them up.

Example explanation

Squares: [(0, 0, 2), (1, 1, 2)] — (x, y, side).

Total area: 4 + 4 = 8. Target: 4 below the line.

Binary search on y in [0, 3]:

• y=1.5: Square 1 (bottom 0, top 2): area below = 2 × 1.5 = 3. Square 2 (bottom 1, top 3): area below = 2 × 0.5 = 1. Total = 4. ✓

Answer: y = 1.5.

Common mistakes candidates make

• Using integer binary search bounds — y is continuous, not discrete; use floating-point binary search with sufficient precision iterations (~100 iterations converges to 10^-30 precision).
• Not clipping the square's contribution — a square extends from sq_y to sq_y + side; area below y is width × min(y - sq_y, side) but only if y > sq_y.
• Setting incorrect binary search bounds — min bound should be the minimum sq_y, max bound should be max(sq_y + side).
• Not handling squares entirely above the line (contribute 0) or entirely below (contribute full area).

Interview preparation tip

For the Separate Squares I coding problem, the binary search array interview pattern on continuous values is the approach. The key skill: binary search works whenever the evaluation function is monotone — area_below(y) is strictly increasing in y. Google and Bloomberg interviewers value knowing how many iterations of floating-point binary search achieves the required precision. Practice "binary search on real values" on area, weight, and time problems — this pattern appears in division-based optimization across interviews.