Separate Squares II

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.

Example 1

1
2
3
4
5
6


Input: squares = [[0,0,1],[2,2,1]]
Output: 1.00000
Explanation:
![](https://assets.leetcode.com/uploads/2025/01/15/4065example1drawio.png)
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

1
2
3
4
5
6


Input: squares = [[0,0,2],[1,1,1]]
Output: 1.00000
Explanation:
![](https://assets.leetcode.com/uploads/2025/01/15/4065example2drawio.png)
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^4
squares[i] = [xi, yi, li]
squares[i].length == 3
0 <= xi, yi <= 10^9
1 <= li <= 10^9
The total area of all the squares will not exceed 1015.

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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.

Problem#

Example 1#

Example 2#

Constraints#

Examples#

Solution#

Method 1 – Line Sweep + Binary Search#

Intuition#

Approach#

Code#

Complexity#