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) {

    // ------------------------------------------------------------
    // BUILD SWEEP EVENTS + COLLECT ALL X-COORDINATES
    // ------------------------------------------------------------
    // For each square:
    //   - At y = bottom, we ADD its horizontal interval [x, x+l]
    //   - At y = top, we REMOVE that interval
    //
    // We also collect all x and x+l values for coordinate compression.
    // ------------------------------------------------------------
    const events = [];
    const xs = [];
    for (const [x, y, l] of squares) {
        const x2 = x + l;
        events.push([y,     x, x2, +1]); // entering event
        events.push([y + l, x, x2, -1]); // leaving event
        xs.push(x, x2);
    }

    // ------------------------------------------------------------
    // COORDINATE COMPRESSION FOR X-AXIS
    // ------------------------------------------------------------
    // We sort all x-values and remove duplicates.
    // This lets us map large coordinates → small indices.
    // ------------------------------------------------------------
    xs.sort((a, b) => a - b);
    const uniq = [];
    for (let i = 0; i < xs.length; i++)
        if (i === 0 || xs[i] !== xs[i - 1]) uniq.push(xs[i]);

    const m = uniq.length;
    const segN = Math.max(1, m - 1); // number of x-segments

    // Precompute the length of each compressed segment [uniq[i], uniq[i+1]]
    const segLen = new Float64Array(segN);
    for (let i = 0; i < segN; i++) segLen[i] = uniq[i + 1] - uniq[i];

    // Map each unique x-value → compressed index
    const idx = new Map();
    for (let i = 0; i < m; i++) idx.set(uniq[i], i);

    // Replace x1,x2 in events with compressed indices
    for (const e of events) {
        e[1] = idx.get(e[1]); // left index
        e[2] = idx.get(e[2]); // right index
    }

    // Sort events by y-coordinate (sweep from bottom to top)
    events.sort((a, b) => a[0] - b[0]);

    // ------------------------------------------------------------
    // SEGMENT TREE SETUP
    // ------------------------------------------------------------
    // count[node]  = how many intervals currently cover this segment
    // covered[node] = total covered length in this segment
    //
    // If count[node] > 0, the entire segment is covered.
    // Otherwise, we sum children.
    // ------------------------------------------------------------
    const size = 4 * segN;
    const count = new Int32Array(size);
    const covered = new Float64Array(size);

    // ------------------------------------------------------------
    // SEGMENT TREE UPDATE
    // ------------------------------------------------------------
    // Adds or removes coverage on interval [ql, qr)
    // node covers [l, r)
    // ------------------------------------------------------------
    function update(node, l, r, ql, qr, val) {
        // No overlap
        if (ql >= r || qr <= l) return;

        // Fully inside update range
        if (ql <= l && r <= qr) {
            count[node] += val;
        } else {
            // Partial overlap → recurse
            const mid = (l + r) >> 1;
            update(node << 1,     l,   mid, ql, qr, val);
            update((node << 1)|1, mid, r,   ql, qr, val);
        }

        // Recompute covered length
        if (count[node] > 0) {
            // Entire segment is covered
            covered[node] = uniq[r] - uniq[l];
        } else if (l + 1 < r) {
            // No direct coverage → sum children
            covered[node] = covered[node << 1] + covered[(node << 1) | 1];
        } else {
            // Leaf segment, uncovered
            covered[node] = 0;
        }
    }

    // ------------------------------------------------------------
    // SWEEP LINE: BUILD VERTICAL STRIPS
    // ------------------------------------------------------------
    // As we sweep upward:
    //   - Between events, the covered horizontal length is constant.
    //   - Each strip contributes: coveredWidth * height
    //
    // We store:
    //   y0[k] = bottom of strip
    //   y1[k] = top of strip
    //   cov[k] = covered horizontal length in that strip
    // ------------------------------------------------------------
    const y0 = [], y1 = [], cov = [];
    let i = 0;
    let prevY = events[0][0];

    while (i < events.length) {
        const y = events[i][0];
        const dy = y - prevY;

        // If we moved upward, record the strip
        if (dy > 0) {
            const c = covered[1]; // total covered width at this moment
            if (c > 0) {
                y0.push(prevY);
                y1.push(y);
                cov.push(c);
            }
            prevY = y;
        }

        // Process all events at this y-level
        while (i < events.length && events[i][0] === y) {
            const [, lIdx, rIdx, type] = events[i];
            if (lIdx < rIdx) update(1, 0, segN, lIdx, rIdx, type);
            i++;
        }
    }

    // ------------------------------------------------------------
    // COMPUTE TOTAL UNION AREA
    // ------------------------------------------------------------
    let total = 0;
    for (let k = 0; k < cov.length; k++)
        total += cov[k] * (y1[k] - y0[k]);

    // If no area at all, return the lowest y
    if (total === 0) return events[0][0];

    const half = total / 2;
    let acc = 0;

    // ------------------------------------------------------------
    // FIND THE BALANCING HEIGHT
    // ------------------------------------------------------------
    // We walk through strips until accumulated area ≥ half.
    // Inside the strip, area grows linearly with y, so we solve:
    //
    //   acc + cov[k] * (h - y0[k]) = half
    //
    // → h = y0[k] + (half - acc) / cov[k]
    // ------------------------------------------------------------
    for (let k = 0; k < cov.length; k++) {
        const area = cov[k] * (y1[k] - y0[k]);
        if (acc + area >= half)
            return y0[k] + (half - acc) / cov[k];
        acc += area;
    }

    // If somehow not found (floating-point edge), return topmost y
    return y1[y1.length - 1];
};