Separate Squares I & II

Problem Statement

Separate Squares I (LC 3453)

You are given a list of axis-aligned squares on a 2D plane. Each square is defined by [x, y, side] where (x, y) is the bottom-left corner and side is the side length. Find a horizontal line y = k such that the total area of squares above the line equals the total area of squares below the line. Squares intersected by the line are split, and only the portion on each side counts.

Example:

Input: squares = [[0, 0, 2], [1, 3, 2]]
Output: 2.5
Explanation: Square 1 has area 4 (fully below y=2.5), square 2 spans y=3 to y=5, 
so 0.5 of its height is below → area below = 4 + 2*0.5 = 5, area above = 2*1.5 = 3.
Wait — we need equal split. Binary search finds the exact y.

Separate Squares II (LC 3454)

Same setup, but squares can overlap. When squares overlap, the overlapping region's area is counted only once. Find y = k that splits the total union area equally.

Constraints:

• 1 <= squares.length <= 10^4
• 0 <= x, y <= 10^9
• 1 <= side <= 10^9

Difficulty: Medium (I), Hard (II)

---

Pattern Recognition

• What is the input structure? A list of geometric rectangles (squares) with coordinates.
• What are we optimizing? Finding a threshold value k that balances a continuous function (area above vs below).
• What pattern does this fit? Binary Search on the answer. The area below y = k is a monotonically increasing function of k, so binary search finds the exact split point.
• Why does this pattern fit? As you increase k, the area below the line monotonically increases. This monotonicity is the precondition for binary search. For Part II, the union area calculation requires coordinate compression and sweep line.

---

Approach

Part I — Separate Squares I

Brute Force

Try many values of k, compute area below for each, pick the one closest to half.

Time: Depends on precision — effectively unbounded for exact answer. Why insufficient: No systematic way to converge.

Optimal — Binary Search on k

Key Insight: The function area_below(k) is continuous and monotonically non-decreasing. Binary search on k in the range [min_y, max_y] converges to the exact split point.

Step-by-step:

1. Compute total_area = sum of all square areas.
2. Find the search range: lo = min(y), hi = max(y + side).
3. Binary search on k:
   • For each square, compute how much area lies below y = k.
   • If a square is entirely below (y + side <= k): full area.
   • If entirely above (y >= k): zero area.
   • If intersected: side * (k - y) (the width times the height below the line).
4. If area_below >= total_area / 2, search lower. Otherwise, search higher.
5. After sufficient iterations (50-100 for float precision), return k.

function separateSquares(squares):
    total_area = sum(s^2 for each square)
    lo = min(y for each square)
    hi = max(y + side for each square)
    for 100 iterations:
        mid = (lo + hi) / 2
        below = computeAreaBelow(mid, squares)
        if below >= total_area / 2:
            hi = mid
        else:
            lo = mid
    return lo

Time: O(n * iterations) where iterations is ~60 for sufficient precision. Space: O(1).

Part II — Separate Squares II (Union Area)

Key Insight: When squares overlap, you cannot just sum individual areas. You need the union area below line y = k. Use coordinate compression on x-coordinates and a sweep line to compute the union width at each y-level.

Step-by-step:

1. Binary search on k as before.
2. For area_below(k): use a sweep-line approach.
   • Collect all y-events (square bottom edges = "start", min(square top, k) = "end").
   • Sort events by y-coordinate.
   • At each y-level, compute the union of x-intervals using coordinate compression.
   • Accumulate area = union_width * delta_y between consecutive events.
3. Binary search finds the k where union area below = total union area / 2.

Time: O(n log n * iterations) for each binary search step — the sweep line costs O(n log n). Space: O(n) for events and coordinate compression.

---

Walkthrough

Part I Example

squares = [[0, 0, 3], [2, 2, 4]]

• Square A: bottom-left (0,0), side 3, spans y=0 to y=3, area = 9
• Square B: bottom-left (2,2), side 4, spans y=2 to y=6, area = 16
• Total area = 25, target = 12.5

Binary search:

Iteration	lo	hi	mid	Area below mid	Action
1	0	6	3.0	A: 9 (full) + B: 4*1 = 4 → 13	13 >= 12.5 → hi = 3.0
2	0	3.0	1.5	A: 3*1.5 = 4.5 + B: 0 (below B) → 4.5	4.5 < 12.5 → lo = 1.5
3	1.5	3.0	2.25	A: 32.25 = 6.75 + B: 40.25 = 1 → 7.75	7.75 < 12.5 → lo = 2.25
4	2.25	3.0	2.625	A: 32.625 = 7.875 + B: 40.625 = 2.5 → 10.375	10.375 < 12.5 → lo = 2.625
5	2.625	3.0	2.8125	A: 32.8125 = 8.4375 + B: 40.8125 = 3.25 → 11.6875	11.6875 < 12.5 → lo = 2.8125
...	converging toward ~2.93

The binary search converges to the precise answer after ~60 iterations.

---

Implementation

Part I — No Overlaps

TypeScript

// Part I — No Overlaps
function separateSquaresI(squares: number[][]): number {
    let totalArea = 0;
    let lo = Infinity, hi = -Infinity;
    for (const [x, y, s] of squares) {
        totalArea += s * s;
        lo = Math.min(lo, y);
        hi = Math.max(hi, y + s);
    }
    const target = totalArea / 2;

    // ~60 iterations gives precision to 1e-18
    for (let iter = 0; iter < 100; iter++) {
        const mid = (lo + hi) / 2;
        let areaBelow = 0;
        for (const [x, y, s] of squares) {
            if (y + s <= mid) {
                areaBelow += s * s;
            } else if (y >= mid) {
                // Entirely above
            } else {
                areaBelow += s * (mid - y);
            }
        }
        if (areaBelow >= target) hi = mid;
        else lo = mid;
    }
    return lo;
}

// Part II — handles overlapping squares using sweep line
function separateSquaresII(squares: number[][]): number {
    function unionAreaBelow(k: number): number {
        const events: [number, number, number, number][] = [];
        for (const [x, y, s] of squares) {
            const yTop = Math.min(y + s, k);
            if (y >= k) continue;
            events.push([y, 0, x, x + s]);      // open
            events.push([yTop, 1, x, x + s]);    // close
        }
        if (events.length === 0) return 0;

        events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

        const xSet = new Set<number>();
        for (const [, , xl, xr] of events) {
            xSet.add(xl);
            xSet.add(xr);
        }
        const xCoords = [...xSet].sort((a, b) => a - b);

        const count = new Array(xCoords.length - 1).fill(0);
        let area = 0;
        let prevY = events[0][0];
        let i = 0;

        while (i < events.length) {
            const curY = events[i][0];
            if (curY > prevY) {
                let unionWidth = 0;
                for (let j = 0; j < count.length; j++) {
                    if (count[j] > 0) unionWidth += xCoords[j + 1] - xCoords[j];
                }
                area += unionWidth * (curY - prevY);
            }
            while (i < events.length && events[i][0] === curY) {
                const [, typ, xl, xr] = events[i];
                const delta = typ === 1 ? -1 : 1;
                for (let j = 0; j < xCoords.length - 1; j++) {
                    if (xCoords[j] >= xl && xCoords[j + 1] <= xr) count[j] += delta;
                }
                i++;
            }
            prevY = curY;
        }
        return area;
    }

    let lo = Infinity, hi = -Infinity;
    for (const [, y, s] of squares) {
        lo = Math.min(lo, y);
        hi = Math.max(hi, y + s);
    }
    const totalUnion = unionAreaBelow(hi);
    const target = totalUnion / 2;

    for (let iter = 0; iter < 100; iter++) {
        const mid = (lo + hi) / 2;
        if (unionAreaBelow(mid) >= target) hi = mid;
        else lo = mid;
    }
    return lo;
}

C++

// Part I — No Overlaps
double separateSquaresI(vector<vector<int>>& squares) {
    double totalArea = 0;
    double lo = 1e18, hi = -1e18;
    for (auto& sq : squares) {
        int x = sq[0], y = sq[1], s = sq[2];
        totalArea += (double)s * s;
        lo = min(lo, (double)y);
        hi = max(hi, (double)(y + s));
    }
    double target = totalArea / 2.0;

    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2.0;
        double areaBelow = 0;
        for (auto& sq : squares) {
            int x = sq[0], y = sq[1], s = sq[2];
            if (y + s <= mid) {
                areaBelow += (double)s * s;
            } else if (y >= mid) {
                // Entirely above
            } else {
                areaBelow += s * (mid - y);
            }
        }
        if (areaBelow >= target) hi = mid;
        else lo = mid;
    }
    return lo;
}

// Part II — handles overlapping squares using sweep line
double separateSquaresII(vector<vector<int>>& squares) {
    auto unionAreaBelow = [&](double k) -> double {
        // Events: {y, type (0=open, 1=close), xl, xr}
        vector<tuple<double, int, int, int>> events;
        for (auto& sq : squares) {
            int x = sq[0], y = sq[1], s = sq[2];
            double yTop = min((double)(y + s), k);
            if (y >= k) continue;
            events.emplace_back((double)y, 0, x, x + s);
            events.emplace_back(yTop, 1, x, x + s);
        }
        if (events.empty()) return 0.0;

        sort(events.begin(), events.end());

        set<int> xSet;
        for (auto& [yy, t, xl, xr] : events) {
            xSet.insert(xl);
            xSet.insert(xr);
        }
        vector<int> xCoords(xSet.begin(), xSet.end());

        vector<int> count(xCoords.size() - 1, 0);
        double area = 0;
        double prevY = get<0>(events[0]);
        int i = 0;

        while (i < (int)events.size()) {
            double curY = get<0>(events[i]);
            if (curY > prevY) {
                double unionWidth = 0;
                for (int j = 0; j < (int)count.size(); j++) {
                    if (count[j] > 0) unionWidth += xCoords[j + 1] - xCoords[j];
                }
                area += unionWidth * (curY - prevY);
            }
            while (i < (int)events.size() && get<0>(events[i]) == curY) {
                auto [yy, typ, xl, xr] = events[i];
                int delta = (typ == 1) ? -1 : 1;
                for (int j = 0; j < (int)xCoords.size() - 1; j++) {
                    if (xCoords[j] >= xl && xCoords[j + 1] <= xr) count[j] += delta;
                }
                i++;
            }
            prevY = curY;
        }
        return area;
    };

    double lo = 1e18, hi = -1e18;
    for (auto& sq : squares) {
        lo = min(lo, (double)sq[1]);
        hi = max(hi, (double)(sq[1] + sq[2]));
    }
    double totalUnion = unionAreaBelow(hi);
    double target = totalUnion / 2.0;

    for (int iter = 0; iter < 100; iter++) {
        double mid = (lo + hi) / 2.0;
        if (unionAreaBelow(mid) >= target) hi = mid;
        else lo = mid;
    }
    return lo;
}

Watch out:

1. Integer overflow with large coordinates. Coordinates go up to 10^9, and area can be up to 10^18. Use floats or Python's arbitrary-precision integers.
2. Precision in binary search termination. Use a fixed number of iterations (60-100) rather than a threshold like hi - lo < epsilon. The fixed iteration approach is more reliable for floating-point binary search.
3. Part II: forgetting to clip the top of squares to k. When computing area below k, a square that extends above k must be truncated at k.

---

Complexity Analysis

	Time	Space
Part I (Binary Search)	O(n * 100) ≈ O(n)	O(1)
Part II (Binary Search + Sweep Line)	O(n^2 * 100) ≈ O(n^2)	O(n)

Bottleneck: For Part I, each binary search iteration scans all squares — O(n) per iteration, ~100 iterations. For Part II, the sweep line with coordinate compression costs O(n log n) per iteration naively, but the inner loop updating the count array can be O(n) per event, making it O(n^2) per binary search step. With a segment tree, Part II can be improved to O(n log n) per step.

---

Edge Cases

1. Single square — The line splits it exactly in half: y + side / 2.
2. All squares at the same y — The answer is simply y + side / 2 if all squares are identical.
3. Non-overlapping squares spread far apart — Part I and Part II give the same answer. Good test to verify Part II logic.
4. Squares fully contained inside other squares — Part II must not double-count the inner square's area.
5. Very large coordinates (10^9) — Area values reach 10^18. Ensure no precision loss.
6. All squares above or below a certain y — Binary search boundaries must include the full range.

---

Related Problems

• LC 850 — Rectangle Area II — Union area of rectangles using sweep line + coordinate compression. Direct prerequisite for Part II.
• LC 218 — The Skyline Problem — Sweep line with events on rectangles.
• LC 1011 — Capacity To Ship Packages — Binary search on the answer with a monotonic feasibility function.
• LC 875 — Koko Eating Bananas — Another binary search on answer pattern.

---

What is Expected at Each Level

Junior: Recognize the binary search on answer pattern for Part I. Implement the area-below computation correctly for non-overlapping squares. May struggle with float precision.

Mid-level: Solve Part I cleanly with proper binary search. Articulate why the function is monotonic. Discuss the overlap problem and suggest sweep line for Part II, even if the full implementation is complex.

Senior: Implement both parts. For Part II, use coordinate compression and sweep line efficiently. Discuss segment tree optimization for the x-union computation. Handle precision and edge cases proactively.