# Separate Squares II
**Difficulty:** HARD
[External](https://leetcode.com/problems/separate-squares-ii)
Canonical: https://scaleengineer.com/dsa/problems/separate-squares-ii
**Patterns:** [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree
---
## Problem
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 the total area covered by squares above the line _equals_ the total area covered by squares below the line.

Answers within `10-5` of the actual answer will be accepted.

**Note**: Squares **may** overlap. Overlapping areas should be counted **only once** in this version.

**Example 1:**

**Input:** squares = \[\[0,0,1\],\[2,2,1\]\]

**Output:** 1.00000

**Explanation:**

![](https://assets.glich.co/dsa/separate-squares-ii/image0.png)

Any horizontal line between `y = 1` and `y = 2` results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.

**Example 2:**

**Input:** squares = \[\[0,0,2\],\[1,1,1\]\]

**Output:** 1.00000

**Explanation:**

![](https://assets.glich.co/dsa/separate-squares-ii/image1.png)

Since the blue square overlaps with the red square, it will not be counted again. Thus, the line `y = 1` splits the squares into two equal parts.

**Constraints:**

* `1 <= squares.length <= 5 * 104`
* `squares[i] = [xi, yi, li]`
* `squares[i].length == 3`
* `0 <= xi, yi <= 109`
* `1 <= li <= 109`
* The total area of all the squares will not exceed `1015`.

# Approaches
## Binary Search on Answer with Sweep-Line
This approach leverages the monotonic nature of the area function with respect to the dividing line's y-coordinate. We can binary search for the optimal y-coordinate `h`. For each guess of `h`, we calculate the area of the union of squares below that line. This area calculation is a classic computational geometry problem that can be solved with a sweep-line algorithm and a segment tree. While correct, this method is less efficient because it involves running the entire `O(N log N)` area calculation multiple times.
**Time:** O(K * N log N), where N is the number of squares and K is the number of iterations in the binary search. K is determined by `log(Range / precision)`, which is roughly a constant factor (e.g., 100). This is generally slower than the optimal approach. · **Space:** O(N), where N is the number of squares. This space is required for the data structures used in the sweep-line algorithm, such as the event list and the segment tree.
**Pros:** Conceptually clear, as it breaks down the problem into two well-known subproblems: binary search and calculating the area of union of rectangles.; Guaranteed to find the answer within the desired precision.
**Cons:** Inefficient due to the repeated execution of the `O(N log N)` area calculation within the binary search loop.; The implementation can be complex, as the set of y-coordinates for the segment tree in the sweep-line algorithm changes with each `h`, requiring repeated setup or a more complex data structure.
### Explanation
The fundamental idea is to find a root for the equation `AreaBelow(h) - TotalArea / 2 = 0`. Since `AreaBelow(h)` is monotonic, binary search is a natural fit. The main challenge lies in efficiently computing `AreaBelow(h)`. 

A sweep-line algorithm is used for this. We treat the clipped rectangles' vertical edges as events. A vertical line sweeps across the plane from left to right. Between any two consecutive x-events, the set of active rectangles is constant. We use a segment tree to manage the y-intervals of these active rectangles and query the total length of their union on the sweep line. By multiplying this length by the distance between consecutive x-events and summing up these areas, we get the total area of the union.

This entire process is wrapped inside a binary search loop. The number of iterations for the binary search depends on the coordinate range and required precision, typically around 100 iterations for the given constraints. This leads to a high overall time complexity.
### Algorithm
- **Overall Strategy:** The area of the union of squares below a horizontal line `y = h`, let's call it `A(h)`, is a monotonically increasing function of `h`. This property allows us to use binary search on the value of `h` to find the one that splits the total area in half.
- **Area Calculation:** The main subproblem is to compute `A(h)` for a given `h`. This can be solved using a sweep-line algorithm.
- **Steps:**
  1.  First, compute the total area of the union of all squares, `TotalArea`. This is done once using a standard sweep-line algorithm. The target area for the lower half is `TargetArea = TotalArea / 2`.
  2.  Define a search range for `h`. A safe range is from the minimum possible y-coordinate to the maximum possible top-edge y-coordinate.
  3.  Perform a binary search for `h` in this range.
  4.  In each iteration, for a candidate value `mid_h`:
      a.  Create a new set of rectangles by clipping each original square with the line `y = mid_h`. A square `[x, y, l]` becomes a rectangle with corners `(x, y)` and `(x+l, min(y+l, mid_h))`.
      b.  Calculate the area of the union of these clipped rectangles using a sweep-line algorithm. This involves sweeping a vertical line from left to right and using a segment tree to maintain the length of the union of vertical intervals on the sweep line.
      c.  If the calculated area is greater than or equal to `TargetArea`, it means `mid_h` is a potential answer, so we try to find a smaller `h` by setting `high = mid_h`. Otherwise, we need a larger `h`, so we set `low = mid_h`.
  5.  The binary search continues until the range `[low, high]` is smaller than the required precision (e.g., `10^-5`).

## Horizontal Sweep-Line with Segment Tree
This is the most efficient approach, solving the problem in `O(N log N)` time. It avoids the repeated calculations of the binary search method by performing a single conceptual sweep across the y-axis. We treat the top and bottom edges of the squares as events. Between any two consecutive event y-coordinates, the set of squares crossing a horizontal line is constant. We can calculate the total length of the x-intervals covered by these squares using a segment tree. By integrating this length over y, we first find the total area and then, in a second pass, find the exact y-coordinate where the accumulated area reaches half of the total.
**Time:** O(N log N), dominated by sorting the events. The sweep itself involves 2N events, and each event triggers an `O(log N)` update on the segment tree. · **Space:** O(N), where N is the number of squares. Space is used for storing events, the coordinate compression map, and the segment tree.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; Calculates the exact answer without requiring iterative approximation (like binary search).; The core logic (sweep-line with segment tree) is a powerful technique applicable to many other geometric problems.
**Cons:** Implementation is more complex than the binary search approach, requiring careful handling of the segment tree and event processing.; Requires two passes over the data, though this does not change the overall asymptotic complexity.
### Explanation
This method reframes the problem from finding a point to integrating a function. The function to integrate, `L(y)`, is the total length of the union of horizontal segments obtained by intersecting the squares with the line at height `y`. `L(y)` is a step function, constant between the y-coordinates of the tops and bottoms of the squares. The algorithm calculates the area under this step function.

We use a horizontal sweep-line. The events are the y-coordinates. The state of the sweep-line is the set of active x-intervals, and we need to find the length of their union. A segment tree is perfectly suited for this. The x-coordinates are first compressed. The segment tree is built on these compressed coordinates. Each node stores a `count` of how many active intervals cover its range and the `length` of the union within its range. An update involves adding or removing an x-interval, which translates to incrementing or decrementing the `count` on the corresponding segment tree nodes. The total covered length is always available at the root of the tree.

Two passes are made: the first to compute the total area, and the second to find the y-value where the accumulated area equals half the total. This avoids the `log(Range)` factor from binary search, leading to a significantly faster solution.

```java
class Solution {
    class Event implements Comparable<Event> {
        long y;
        long x1, x2;
        int type; // 1 for enter, -1 for exit

        Event(long y, long x1, long x2, int type) {
            this.y = y;
            this.x1 = x1;
            this.x2 = x2;
            this.type = type;
        }

        @Override
        public int compareTo(Event other) {
            return Long.compare(this.y, other.y);
        }
    }

    class Node {
        int count;
        long length;
    }

    Node[] tree;
    long[] xCoords;
    Map<Long, Integer> xMap;

    public double separateSquares(int[][] squares) {
        List<Event> events = new ArrayList<>();
        Set<Long> xSet = new HashSet<>();

        for (int[] s : squares) {
            long x = s[0], y = s[1], l = s[2];
            events.add(new Event(y, x, x + l, 1));
            events.add(new Event(y + l, x, x + l, -1));
            xSet.add(x);
            xSet.add(x + l);
        }

        if (xSet.isEmpty()) return 0.0;
        Collections.sort(events);

        xCoords = new long[xSet.size()];
        int idx = 0;
        for (long val : xSet) xCoords[idx++] = val;
        Arrays.sort(xCoords);

        xMap = new HashMap<>();
        for (int i = 0; i < xCoords.length; i++) xMap.put(xCoords[i], i);

        tree = new Node[4 * xCoords.length];
        for (int i = 0; i < tree.length; i++) tree[i] = new Node();

        // Pass 1: Calculate total area
        long totalArea = 0;
        long lastY = events.get(0).y;
        for (int i = 0; i < events.size(); ) {
            long currentY = events.get(i).y;
            if (currentY > lastY) {
                totalArea += tree[1].length * (currentY - lastY);
            }
            int j = i;
            while (j < events.size() && events.get(j).y == currentY) {
                Event e = events.get(j);
                update(1, 0, xCoords.length - 2, xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);
                j++;
            }
            lastY = currentY;
            i = j;
        }

        if (totalArea == 0) {
            long minY = Long.MAX_VALUE;
            for(int[] s : squares) minY = Math.min(minY, s[1]);
            return minY;
        }
        
        double targetArea = totalArea / 2.0;
        
        // Pass 2: Find the split line
        for (int i = 0; i < tree.length; i++) tree[i] = new Node();
        double areaSoFar = 0;
        lastY = events.get(0).y;

        for (int i = 0; i < events.size(); ) {
            long currentY = events.get(i).y;
            if (currentY > lastY) {
                long coveredLength = tree[1].length;
                if (coveredLength > 0) {
                    double slabArea = (double) coveredLength * (currentY - lastY);
                    if (areaSoFar + slabArea >= targetArea) {
                        double neededArea = targetArea - areaSoFar;
                        return lastY + neededArea / coveredLength;
                    }
                    areaSoFar += slabArea;
                }
            }
            int j = i;
            while (j < events.size() && events.get(j).y == currentY) {
                Event e = events.get(j);
                update(1, 0, xCoords.length - 2, xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);
                j++;
            }
            lastY = currentY;
            i = j;
        }
        
        return -1.0; // Should be unreachable
    }

    private void update(int nodeIdx, int start, int end, int l, int r, int val) {
        if (l > r) return;
        if (l == start && r == end) {
            tree[nodeIdx].count += val;
        } else {
            int mid = start + (end - start) / 2;
            update(2 * nodeIdx, start, mid, l, Math.min(r, mid), val);
            update(2 * nodeIdx + 1, mid + 1, end, Math.max(l, mid + 1), r, val);
        }
        pushUp(nodeIdx, start, end);
    }

    private void pushUp(int nodeIdx, int start, int end) {
        if (tree[nodeIdx].count > 0) {
            tree[nodeIdx].length = xCoords[end + 1] - xCoords[start];
        } else {
            if (start == end) {
                tree[nodeIdx].length = 0;
            } else {
                tree[nodeIdx].length = tree[2 * nodeIdx].length + tree[2 * nodeIdx + 1].length;
            }
        }
    }
}
```
### Algorithm
- **Core Idea:** Instead of binary searching, we can find the answer directly by sweeping a horizontal line from bottom to top. The total length of the horizontal cross-section of the union of squares is a step function that only changes at the y-coordinates of the squares' top and bottom edges.
- **Steps:**
  1.  **Events and Coordinate Compression:**
      - For each square `[x, y, l]`, create two events: an 'enter' event at `y` and an 'exit' event at `y+l`. Both are associated with the x-interval `[x, x+l]`.
      - Collect all unique x-coordinates (`x` and `x+l`) and compress them into a smaller integer range to be used as indices for a segment tree.
  2.  **Segment Tree:**
      - Build a segment tree over the compressed x-coordinates. Each node in the tree will maintain a `count` (how many rectangles cover its range) and `length` (the length of the covered portion of its range).
  3.  **First Pass (Total Area):**
      - Sort the y-events. Iterate through them, processing horizontal 'slabs' between consecutive event y-coordinates.
      - For each slab between `y_prev` and `y_curr`, the area is `(covered_x_length) * (y_curr - y_prev)`. The `covered_x_length` is queried from the root of the segment tree.
      - Sum these slab areas to get the `TotalArea`.
      - After calculating a slab's area, process the event(s) at `y_curr` to update the segment tree for the next slab.
  4.  **Second Pass (Find Split Line):**
      - Calculate `TargetArea = TotalArea / 2`.
      - Reset the segment tree and an `areaSoFar` counter.
      - Perform another sweep through the sorted y-events.
      - For each slab, calculate its area. If `areaSoFar + slabArea >= TargetArea`, the split line `h` lies within this slab.
      - The exact value of `h` can be found with the formula: `h = y_prev + (TargetArea - areaSoFar) / covered_x_length`.
      - Return `h` and terminate.