Separate Squares I · Interview Problem

Back to problems

Leetcode

Medium

Geometry

Binary Search

Arrays

Google

Separate Squares I

Find the horizontal line that splits the total area covered by axis-aligned squares into two equal halves.

Acceptance 75%

Start Practice

Problem Statement

Problem

You are given a list of axis-aligned squares on a 2D plane. Each square is represented by its bottom-left corner and side length.

Choose a horizontal line $y = h$ such that the total area of all square regions lying strictly below the line is equal to the total area lying strictly above the line.

Return the value of $h$ .

If multiple values are possible, return any one of them. The answer should be accurate to within a small floating-point tolerance.

Notes

Squares may overlap.
Overlapping regions contribute area multiple times, once for each square.
The line is horizontal, so only the $y$ -coordinates matter for the split.

Input Format

An array of squares.
Each square is described by three values: x, y, side, where (x, y) is the bottom-left corner and side is the side length.

Although x is provided, the splitting line is horizontal, so the answer depends only on the vertical placement and sizes of the squares.

Output Format

Return a floating-point number h representing the y-coordinate of the horizontal split line.

Constraints

Each square has positive side length.
The number of squares is at least 1.
Area calculations may require floating-point precision.
Squares may overlap and can have arbitrary coordinates within typical integer limits.

Examples

Sample cases returned by the problem API.

Example 1

Input

squares = [[0,0,2],[1,1,2]]

Output

1.500000

Explanation

The total area is 8. A horizontal line at y = 1.5 splits the combined area into 4 below and 4 above, counting overlap separately for each square.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress