Separate Squares I
Separate Squares I is a medium binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (sweep line over edges), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from binary search on y up.
Problem
You are given squares, where squares[i] = [x, y, l] describes an axis-aligned square with bottom-left corner (x, y) and side length l.
Find the smallest y-coordinate of a horizontal line such that the total area of the squares above the line equals the total area below it. Squares may overlap; overlapping parts are counted once for each square that covers them. Return the answer as a decimal number; results within 10^-5 of the exact value are accepted.
Examples
Example 1
- Input
squares = [[0,0,2],[3,1,2]]- Output
1.50000- Why
- The total area is 8. At y = 1.5 the first square has 2 x 1.5 = 3 below and the second has 2 x 0.5 = 1 below, so 4 is below and 4 is above.
Example 2
- Input
squares = [[0,0,1],[5,2,1]]- Output
1.00000- Why
- Every line from y = 1 to y = 2 splits the area 1 / 1; the smallest such y is 1.
Example 3
- Input
squares = [[0,0,4],[1,1,2]]- Output
2.00000- Why
- The squares overlap, but overlap is counted twice: total 20, and at y = 2 the area below is 4 x 2 + 2 x 1 = 10.
Constraints
1 <= squares.length <= 5 * 10^4squares[i] = [x, y, l], the bottom-left corner and the side length.0 <= x, y <= 10^9,1 <= l <= 10^9- The total area of all squares is at most
10^12. - Answers within
10^-5of the expected value are accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Binary search on y | O(n · I) | O(1) |
| Optimal (sweep line over edges) | O(n log n) | O(n) |
1Binary search on y
O(n · I)I = 100 iterations, each scanning all n squares.O(1)Only a few running numbers.The area below a horizontal line, below(y), only grows as the line moves up, so the answer is the smallest y with below(y) >= total / 2. Binary search on y between the lowest bottom edge and the highest top edge, computing below(y) in O(n) each time.
- Compute total = sum of l² and the range lo = min y, hi = max(y + l).
- Repeat 100 times: mid = (lo + hi) / 2.
- below(mid) = sum over squares of l * clamp(mid - y, 0, l).
- If 2 * below(mid) >= total, set hi = mid; otherwise lo = mid.
- Return hi.
class Solution {
public double separateSquares(int[][] squares) {
double total = 0, lo = Double.MAX_VALUE, hi = 0;
for (int[] s : squares) {
total += (double) s[2] * s[2];
lo = Math.min(lo, s[1]);
hi = Math.max(hi, (double) s[1] + s[2]);
}
for (int iter = 0; iter < 100; iter++) {
double mid = (lo + hi) / 2;
double below = 0;
for (int[] s : squares) {
double h = Math.min(Math.max(mid - s[1], 0), s[2]);
below += h * s[2];
}
if (2 * below >= total) hi = mid;
else lo = mid;
}
return hi;
}
}class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
total = sum(l * l for _, _, l in squares)
lo = min(y for _, y, _ in squares)
hi = max(y + l for _, y, l in squares)
lo, hi = float(lo), float(hi)
for _ in range(100):
mid = (lo + hi) / 2
below = 0.0
for _, y, l in squares:
h = min(max(mid - y, 0.0), l)
below += h * l
if 2 * below >= total:
hi = mid
else:
lo = mid
return hiclass Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
double total = 0, lo = DBL_MAX, hi = 0;
for (auto& s : squares) {
total += (double)s[2] * s[2];
lo = min(lo, (double)s[1]);
hi = max(hi, (double)s[1] + s[2]);
}
for (int iter = 0; iter < 100; iter++) {
double mid = (lo + hi) / 2;
double below = 0;
for (auto& s : squares) {
double h = min(max(mid - s[1], 0.0), (double)s[2]);
below += h * s[2];
}
if (2 * below >= total) hi = mid;
else lo = mid;
}
return hi;
}
};function separateSquares(squares) {
let total = 0, lo = Infinity, hi = 0;
for (const [, y, l] of squares) {
total += l * l;
lo = Math.min(lo, y);
hi = Math.max(hi, y + l);
}
for (let iter = 0; iter < 100; iter++) {
const mid = (lo + hi) / 2;
let below = 0;
for (const [, y, l] of squares) {
const h = Math.min(Math.max(mid - y, 0), l);
below += h * l;
}
if (2 * below >= total) hi = mid;
else lo = mid;
}
return hi;
}2Optimal (sweep line over edges)
O(n log n)Sorting the 2n events dominates; the sweep itself is linear.O(n)The event list holds 2n entries.below(y) is piecewise linear: between two consecutive edges its slope is the total width of the squares the line currently crosses. Turn every square into two events, +l at its bottom and -l at its top, sort them by y, and sweep upward accumulating area. In the first stretch where the accumulated area would reach half, solve the linear equation for the exact y.
- Create events (y, +l) and (y + l, -l) for every square; total = sum of l²; half = total / 2.
- Sort events by y. Set area = 0, width = 0, prev = first event's y.
- For each event: dy = y - prev. If width > 0 and area + width * dy >= half, return prev + (half - area) / width.
- Otherwise area += width * dy, width += delta, prev = y.
- Return prev (not reached for valid input).
class Solution {
public double separateSquares(int[][] squares) {
int n = squares.length;
long[][] events = new long[2 * n][];
double total = 0;
for (int i = 0; i < n; i++) {
long y = squares[i][1], l = squares[i][2];
events[2 * i] = new long[] { y, l };
events[2 * i + 1] = new long[] { y + l, -l };
total += (double) l * l;
}
Arrays.sort(events, (a, b) -> Long.compare(a[0], b[0]));
double half = total / 2, area = 0;
long width = 0, prev = events[0][0];
for (long[] e : events) {
long dy = e[0] - prev;
if (width > 0 && area + (double) width * dy >= half) {
return prev + (half - area) / width;
}
area += (double) width * dy;
width += e[1];
prev = e[0];
}
return prev;
}
}class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
events = []
total = 0
for _, y, l in squares:
events.append((y, l))
events.append((y + l, -l))
total += l * l
events.sort(key=lambda e: e[0])
half = total / 2
area = 0.0
width = 0
prev = events[0][0]
for y, delta in events:
dy = y - prev
if width > 0 and area + width * dy >= half:
return prev + (half - area) / width
area += width * dy
width += delta
prev = y
return float(prev)class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
vector<pair<long long, long long>> events;
double total = 0;
for (auto& s : squares) {
long long y = s[1], l = s[2];
events.push_back({y, l});
events.push_back({y + l, -l});
total += (double)l * l;
}
sort(events.begin(), events.end(), [](const auto& a, const auto& b) { return a.first < b.first; });
double half = total / 2, area = 0;
long long width = 0, prev = events[0].first;
for (auto& [y, delta] : events) {
long long dy = y - prev;
if (width > 0 && area + (double)width * dy >= half) {
return prev + (half - area) / width;
}
area += (double)width * dy;
width += delta;
prev = y;
}
return (double)prev;
}
};function separateSquares(squares) {
const events = [];
let total = 0;
for (const [, y, l] of squares) {
events.push([y, l]);
events.push([y + l, -l]);
total += l * l;
}
events.sort((a, b) => a[0] - b[0]);
const half = total / 2;
let area = 0, width = 0, prev = events[0][0];
for (const [y, delta] of events) {
const dy = y - prev;
if (width > 0 && area + width * dy >= half) {
return prev + (half - area) / width;
}
area += width * dy;
width += delta;
prev = y;
}
return prev;
}Edge cases to test
- A single square: the answer is its vertical middle
- A gap between squares where the area below stays exactly half; the lowest y of that gap is the answer
- Overlapping squares, which are still counted once each
- Squares sharing the same bottom or top edge
Hints
Hint 1
Let below(y) be the area under the line y. It never decreases as y grows. What can you do with a monotone function?
Hint 2
Binary search on y works. For an exact answer, notice below(y) is piecewise linear: its slope only changes at the bottom and top edges of squares.
Hint 3
Sweep the edges in sorted order, tracking the total width of the squares currently crossed by the line, until the accumulated area reaches half.
FAQ
What is the best time complexity for Separate Squares I?
Optimal (sweep line over edges) runs in O(n log n) time and O(n) extra space. Sorting the 2n events dominates; the sweep itself is linear.
Which pattern does Separate Squares I use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Magnetic Force Between Two Balls.
Is there a brute force solution for Separate Squares I?
Yes. Binary search on y takes O(n · I) time and O(1) space. The area below a horizontal line, below(y), only grows as the line moves up, so the answer is the smallest y with below(y) = total / 2.
Which edge cases should I test for Separate Squares I?
A single square: the answer is its vertical middle; A gap between squares where the area below stays exactly half; the lowest y of that gap is the answer; Overlapping squares, which are still counted once each; Squares sharing the same bottom or top edge.