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 t

separateSquares.js

/**
 * @param {number[][]} squares
 * @return {number}
 */
var separateSquares = function (squares) {
    // ------------------------------------------------------------
    // STEP 1: Compute total area (counting overlaps multiple times)
    // ------------------------------------------------------------
    let totalArea = 0;
    for (const [x, y, l] of squares) {
        totalArea += l * l;
    }

    const target = totalArea / 2; // We want areaBelow(h) = target

    // ------------------------------------------------------------
    // STEP 2: Helper function to compute area below a given height h
    // ------------------------------------------------------------
    function areaBelow(h) {
        let sum = 0;

        for (const [x, y, l] of squares) {
            const bottom = y;
            const top = y + l;

            // If h is below the square entirely → contributes 0
            if (h <= bottom) continue;

            // If h is above the square entirely → contributes full area
            if (h >= top) {
                sum += l * l;
                continue;
            }

            // Otherwise, h cuts through the square
            // Height of the portion below h:
            const heightBelow = h - bottom;

            // Area = width (l) * heightBelow
            sum += l * heightBelow;
        }

        return sum;
    }

    // ------------------------------------------------------------
    // STEP 3: Binary search for the smallest h such that areaBelow(h) >= target
    // ------------------------------------------------------------

    // The balancing line must lie between the lowest bottom and highest top
    let low = Infinity;
    let high = -Infinity;

    for (const [x, y, l] of squares) {
        low = Math.min(low, y);
        high = Math.max(high, y + l);
    }

    // Binary search with precision 1e-6 (safe for 1e-5 requirement)
    for (let i = 0; i < 60; i++) {
        const mid = (low + high) / 2;
        const below = areaBelow(mid);

        if (below >= target) {
            // We already have enough area below → try lower
            high = mid;
        } else {
            // Not enough area below → move upward
            low = mid;
        }
    }

    return low; // or high; they converge
};