Skip to main content
Talentd

Separate Squares II - Solution & Explanation

HardArrayBinary SearchSegment TreeLine Sweep15 min readAsked at: Amazon, Google
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 covered by squares above the line equals the total area covered by squares below the line.

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

Note: Squares may overlap. Overlapping areas should be counted only once in this version.

 

Example 1:

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

Output: 1.00000

Explanation:

Any horizontal line between y = 1 and y = 2 results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.

Example 2:

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

Output: 1.00000

Explanation:

Since the blue square overlaps with the red square, it will not be counted again. Thus, the line y = 1 splits the squares into two equal parts.

 

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 1015.

Approach Overview

Problem Overview: You are given multiple axis-aligned squares on a 2D plane. The task is to find the y-coordinate of a horizontal line that divides the union area of these squares into two equal halves. Overlapping regions must be counted only once, which makes the problem a classic computational geometry challenge.

Approach 1: Binary Search + Area Calculation (O(n log n log R) time, O(n) space)

The idea is to binary search the y-coordinate of the dividing line. For a candidate value mid, compute how much square area lies below it. Each square contributes min(side, max(0, mid - y)) * side. Compare the accumulated area with half of the total area and move the binary search boundary accordingly. This approach works well when squares are treated independently, but it fails when overlapping areas must be counted only once.

Because overlaps must be merged, you must compute the union area of the clipped rectangles. That requires geometry techniques such as a line sweep combined with interval merging.

Approach 2: Line Sweep + Segment Tree (O(n log n) time, O(n) space)

The optimal solution computes the union area using a vertical sweep line. Convert each square into two sweep events: a start edge and an end edge. While sweeping along the y-axis, maintain the active x-intervals covered by squares. A segment tree tracks the total covered width after interval updates.

Between two consecutive sweep events, the covered x-length stays constant. Multiply that width by the vertical distance between events to accumulate area. This gives the union area of all squares. Once the total area is known, sweep again and stop when the accumulated area reaches half. Interpolate within that vertical segment to compute the exact y-coordinate.

The segment tree stores coverage counts and total covered length for compressed x-coordinates. Each event performs a range update and the root always holds the current union width. This avoids repeatedly recomputing overlaps and keeps updates at O(log n).

Recommended for interviews: The expected solution is the sweep line with a segment tree. A naive or independent-area calculation demonstrates initial reasoning, but interviewers typically expect candidates to handle overlapping regions correctly using binary search or sweep-line geometry. The sweep-line approach is both precise and efficient, achieving O(n log n) complexity.

Solution

This problem can be solved using the sweep line algorithm to calculate the total area of all squares.

We treat the top and bottom boundaries of each square as event points for the sweep line, sorted by y coordinate in ascending order. For each event point, we use a segment tree to maintain the length of the covered x-axis interval below the current sweep line, allowing us to calculate the area increment between the current sweep line and the previous one.

The specific steps are as follows:

  1. Preprocess Event Points: For each square, calculate the y coordinates of its top and bottom boundaries and add them as event points to the event list. Each event point contains the y coordinate, left boundary x_1, right boundary x_2, and a flag (indicating whether it's the top or bottom boundary).
  2. Sort Event Points: Sort all event points by y coordinate in ascending order.
  3. Build Segment Tree: Build a segment tree using the discretized x coordinates to maintain the length of the currently covered x-axis intervals.
  4. Scan Event Points: Traverse the sorted event point list. For each event point:
    • Calculate the area increment between the current event point and the previous one, and add it to the total area.
    • Based on the type of the current event point (top or bottom boundary), update the segment tree by increasing or decreasing the coverage count of the corresponding x-axis interval.
  5. Calculate Target Area: The target area is half of the total area.
  6. Scan Event Points Again: Traverse the event point list again, calculating the cumulative area. When the cumulative area reaches the target area, calculate and return the corresponding y coordinate.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of squares.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search with Independent AreaO(n log R)O(1)Works only if overlaps are allowed to be double-counted; useful as an initial intuition
Binary Search + Line SweepO(n log n log R)O(n)When computing union area for each binary search step
Line Sweep + Segment TreeO(n log n)O(n)Optimal solution for computing union area and locating the split line efficiently

Video Solution

Separate Squares II | LeetCode 3454 | Sweep Line + Segment Tree | Geometry Hard • Study Placement • 4,752 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Separate Squares II easy or hard?
Separate Squares II is classified as a Hard problem because it combines computational geometry, coordinate compression, sweep line processing, and segment trees. Implementing the data structure correctly and handling union area calculations requires strong algorithmic experience.
How to solve Separate Squares II in O(n log n)?
Convert each square into vertical sweep events and compress all x-coordinates. While sweeping along the y-axis, update the segment tree with interval add/remove operations. The root node stores the total covered x-length. Multiply that width by the vertical distance between events to accumulate union area and detect where half the area is reached.
What is the best approach for Separate Squares II?
The most efficient approach uses a line sweep combined with a segment tree to compute the union area of the squares. As the sweep moves vertically, active x-intervals are maintained in the segment tree to track the covered width. Area is accumulated between sweep events until half of the total area is reached. This runs in O(n log n) time.
Is Separate Squares II asked at Google/Amazon/Meta?
Problems involving line sweep, interval union, and segment trees frequently appear in interviews at companies like Google, Amazon, and Meta. Separate Squares II combines computational geometry with advanced data structures, making it a strong representation of hard interview questions.
What data structure is used in Separate Squares II?
A segment tree is used to maintain the total length of covered x-intervals during the sweep. Each node tracks how many intervals cover a range and the resulting union length. This allows fast range updates and real-time computation of the merged coverage width.
What is the time complexity of Separate Squares II?
The optimal solution runs in O(n log n) time and O(n) space. Sorting sweep events takes O(n log n), and each event updates a segment tree in O(log n). This structure efficiently maintains the union width of active intervals during the sweep.
Separate Squares II Python or Java solution approach
Both Python and Java implementations follow the same strategy: generate sweep events, compress x-coordinates, and maintain active coverage using a segment tree. Events are processed in sorted order of y. After each update, the tree provides the current covered width used to compute incremental union area.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Rectangle Area II