Separate Squares II
HardUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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 * 10^4squares[i] = [xi, yi, li]squares[i].length == 30 <= xi, yi <= 10^91 <= li <= 10^9- The total area of all the squares will not exceed
1015.
Solution
Method 1 – Line Sweep + Binary Search
Intuition
We want to find the minimum y such that the area above and below y is equal, counting overlapping areas only once. We can use a line sweep to compute the union area below any y, and binary search to find the y where the area below is half the total area.
Approach
- Collect all unique x-coordinates from the squares' left and right edges.
- For a given y, for each x-interval, collect all y-intervals (from squares) that intersect with y, and merge them to compute the total area below y.
- Use binary search on y to find the value where the area below y is half the total area.
- Return the minimum such y.
Code
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
vector<long long> xs;
for (auto& sq : squares) {
xs.push_back(sq[0]);
xs.push_back((long long)sq[0] + sq[2]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto area = [&](double y) -> double {
double res = 0;
for (int i = 0; i + 1 < xs.size(); ++i) {
vector<pair<double, double>> segs;
for (auto& sq : squares) {
long long xl = sq[0], xr = (long long)sq[0] + sq[2];
if (xl <= xs[i] && xs[i+1] <= xr) {
double yl = sq[1], yr = sq[1] + sq[2];
if (yl < y) segs.push_back({yl, min(y, yr)});
}
}
if (segs.empty()) continue;
sort(segs.begin(), segs.end());
double last = -1e20;
double sum = 0;
for (auto& seg : segs) {
if (seg.first > last) {
sum += seg.second - seg.first;
last = seg.second;
} else if (seg.second > last) {
sum += seg.second - last;
last = seg.second;
}
}
res += sum * (xs[i+1] - xs[i]);
}
return res;
};
double l = 0, r = 1e9 + 1, total = area(1e9 + 1);
for (int it = 0; it < 50; ++it) {
double m = (l + r) / 2;
if (area(m) * 2 < total) l = m;
else r = m;
}
return l;
}
};
Java
import java.util.*;
class Solution {
public double separateSquares(int[][] squares) {
Set<Long> xs = new HashSet<>();
for (int[] sq : squares) {
xs.add((long)sq[0]);
xs.add((long)sq[0] + sq[2]);
}
List<Long> xlist = new ArrayList<>(xs);
Collections.sort(xlist);
double total = area(squares, xlist, 1e9 + 1);
double l = 0, r = 1e9 + 1;
for (int it = 0; it < 50; ++it) {
double m = (l + r) / 2;
if (area(squares, xlist, m) * 2 < total) l = m;
else r = m;
}
return l;
}
private double area(int[][] squares, List<Long> xs, double y) {
double res = 0;
for (int i = 0; i + 1 < xs.size(); ++i) {
List<double[]> segs = new ArrayList<>();
for (int[] sq : squares) {
long xl = sq[0], xr = (long)sq[0] + sq[2];
if (xl <= xs.get(i) && xs.get(i+1) <= xr) {
double yl = sq[1], yr = sq[1] + sq[2];
if (yl < y) segs.add(new double[]{yl, Math.min(y, yr)});
}
}
if (segs.isEmpty()) continue;
segs.sort(Comparator.comparingDouble(a -> a[0]));
double last = -1e20, sum = 0;
for (double[] seg : segs) {
if (seg[0] > last) {
sum += seg[1] - seg[0];
last = seg[1];
} else if (seg[1] > last) {
sum += seg[1] - last;
last = seg[1];
}
}
res += sum * (xs.get(i+1) - xs.get(i));
}
return res;
}
}
Python
class Solution:
def separateSquares(self, squares: list[list[int]]) -> float:
xs = set()
for x, y, l in squares:
xs.add(x)
xs.add(x + l)
xs = sorted(xs)
def area(y):
res = 0
for i in range(len(xs) - 1):
segs = []
for x0, y0, l in squares:
if x0 <= xs[i] and xs[i+1] <= x0 + l:
yl, yr = y0, y0 + l
if yl < y:
segs.append((yl, min(y, yr)))
if not segs: continue
segs.sort()
last = -1e20
sum_ = 0
for a, b in segs:
if a > last:
sum_ += b - a
last = b
elif b > last:
sum_ += b - last
last = b
res += sum_ * (xs[i+1] - xs[i])
return res
total = area(1e9 + 1)
l, r = 0, 1e9 + 1
for _ in range(50):
m = (l + r) / 2
if area(m) * 2 < total:
l = m
else:
r = m
return l
Complexity
- ⏰ Time complexity:
O(n log n + K log M), where n = number of squares, K = number of unique x-intervals, M = search range. Each area computation is O(nK), binary search is log M steps. - 🧺 Space complexity:
O(n + K), for storing x-coordinates and intervals.