Separate Squares I

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atGoogle

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^4
  • squares[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^-5 of 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.

00:00
Testcase

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.

ApproachTimeSpace
Binary search on yO(n · I)O(1)
Optimal (sweep line over edges)O(n log n)O(n)

1Binary search on y

TimeO(n · I)I = 100 iterations, each scanning all n squares.
SpaceO(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.

  1. Compute total = sum of l² and the range lo = min y, hi = max(y + l).
  2. Repeat 100 times: mid = (lo + hi) / 2.
  3. below(mid) = sum over squares of l * clamp(mid - y, 0, l).
  4. If 2 * below(mid) >= total, set hi = mid; otherwise lo = mid.
  5. 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;
    }
}

2Optimal (sweep line over edges)

TimeO(n log n)Sorting the 2n events dominates; the sweep itself is linear.
SpaceO(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.

  1. Create events (y, +l) and (y + l, -l) for every square; total = sum of l²; half = total / 2.
  2. Sort events by y. Set area = 0, width = 0, prev = first event's y.
  3. For each event: dy = y - prev. If width > 0 and area + width * dy >= half, return prev + (half - area) / width.
  4. Otherwise area += width * dy, width += delta, prev = y.
  5. 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;
    }
}

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.