Watch 10 video solutions for Separate Squares II, a hard level problem involving Array, Binary Search, Segment Tree. This walkthrough by Study Placement has 4,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 104squares[i] = [xi, yi, li]squares[i].length == 30 <= xi, yi <= 1091 <= li <= 1091015.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search with Independent Area | O(n log R) | O(1) | Works only if overlaps are allowed to be double-counted; useful as an initial intuition |
| Binary Search + Line Sweep | O(n log n log R) | O(n) | When computing union area for each binary search step |
| Line Sweep + Segment Tree | O(n log n) | O(n) | Optimal solution for computing union area and locating the split line efficiently |