Skip to main content
Talentd

Separate Squares I - Solution & Explanation

MediumArrayBinary Search13 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given a 2D integer array squares. Each squares[i] = [xi, yi, li] represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.

Find the minimum y-coordinate value of a horizontal line such that the total area of the squares above the line equals the total area of the squares below the line.

Answers within 10-5 of the actual answer will be accepted.

Note: Squares may overlap. Overlapping areas should be counted multiple times.

 

Example 1:

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

Output: 1.00000

Explanation:

Any horizontal line between y = 1 and y = 2 will have 1 square unit above it and 1 square unit below it. The lowest option is 1.

Example 2:

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

Output: 1.16667

Explanation:

The areas are:

  • Below the line: 7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5.
  • Above the line: 5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5.

Since the areas above and below the line are equal, the output is 7/6 = 1.16667.

 

Constraints:

  • 1 <= squares.length <= 5 * 104
  • squares[i] = [xi, yi, li]
  • squares[i].length == 3
  • 0 <= xi, yi <= 109
  • 1 <= li <= 109
  • The total area of all the squares will not exceed 1012.

Approach Overview

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.

Solution

According to the problem, we need to find a horizontal line such that the total area of squares above the line equals the total area of squares below the line. Since as the y coordinate increases, the area below the line increases and the area above the line decreases, we can use binary search to find the y coordinate of this horizontal line.

We define the left boundary of the binary search as l = 0, and the right boundary as r = max(y_i + l_i), which is the highest point of all squares. Then we calculate the midpoint mid = (l + r) / 2 and calculate the area below this horizontal line. If this area is greater than or equal to half of the total area, it means we need to move the right boundary r downward; otherwise, we move the left boundary l upward. We repeat this process until the difference between the left and right boundaries is less than a very small value (e.g., 10^{-5}).

The time complexity is O(n log(MU)), where n is the number of squares, M = 10^5, and U = max(y_i + l_i). The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan over Heights (Brute Force)O(n * R)O(1)Useful for understanding how square area contributes relative to the split line
Binary Search on Y CoordinateO(n log R)O(1)Best general solution when coordinate range is large and monotonicity holds

Video Solution

Separate Squares I | Understand WHY behind everything | Intuition | Leetcode 3453 | codestorywithMIK • codestorywithMIK • 14,643 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Separate Squares I easy or hard?
Separate Squares I is generally considered a medium-level problem. The implementation is straightforward once you recognize the monotonic relationship between the split line and accumulated area, but identifying binary search on the answer requires some algorithmic experience.
Separate Squares I Python/Java solution
Implement the binary search loop and compute partial square areas for each midpoint. The logic is identical across Python, Java, C++, Go, TypeScript, and Rust: clamp the intersection height for each square and accumulate the area until it matches half of the total.
How to solve Separate Squares I in O(n log R)?
Use binary search on the y-coordinate between the minimum bottom edge and maximum top edge of all squares. For each midpoint, compute the area contributed below the line using the formula l * clamp(mid - yi, 0, l). Compare this sum with half the total square area to decide which direction to search next.
What is the best approach for Separate Squares I?
The optimal solution uses binary search on the y-coordinate of the horizontal split line. As the line moves upward, the total area below it increases monotonically, which makes binary search valid. Each step computes the contributed area from every square, leading to an O(n log R) time complexity where R is the coordinate range.
Is Separate Squares I asked at Google/Amazon/Meta?
Problems combining geometry with binary search appear frequently in interviews at companies like Google and Amazon. The pattern of binary searching over a monotonic answer space is a common interview technique, especially when the solution requires computing a measurable property such as area.
What data structure is used in Separate Squares I?
The solution primarily uses arrays to store the square definitions and arithmetic calculations to compute partial areas. The algorithmic technique is binary search over a continuous value rather than relying on advanced data structures.
What is the time complexity of Separate Squares I?
The optimal binary search solution runs in O(n log R) time and O(1) extra space. For each binary search step you iterate through all n squares and compute the partial area below the candidate line. R represents the numeric range of possible y-values.

Ready to solve this problem?

Practice Separate Squares I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays