# Separate Squares I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/separate-squares-i)
Canonical: https://scaleengineer.com/dsa/problems/separate-squares-i
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## 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 of the squares above the line _equals_ the total area of the squares below the line.

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

**Note**: Squares **may** overlap. Overlapping areas should be counted **multiple times**.

**Example 1:**

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

**Output:** 1.00000

**Explanation:**

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

Any horizontal line between `y = 1` and `y = 2` will have 1 square unit above it and 1 square unit below it. The lowest option is 1.

**Example 2:**

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

**Output:** 1.16667

**Explanation:**

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

The areas are:

* Below the line: `7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5`.
* Above the line: `5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5`.

Since the areas above and below the line are equal, the output is `7/6 = 1.16667`.

**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 `1012`.

# Approaches
## Binary Search on Y-coordinate
This approach leverages the monotonic nature of the area function. The total area of squares below a horizontal line `y = h` is a monotonically increasing function of `h`. This property allows us to use binary search to efficiently find the specific `h` where the area below the line is exactly half of the total area of all squares.
**Time:** O(N * K), where N is the number of squares and K is the number of binary search iterations. K is a constant determined by the required precision (e.g., K ≈ 100). · **Space:** O(1) extra space. The algorithm only requires a few variables to store the search bounds and calculated areas, not counting the input storage.
**Pros:** Conceptually simple and straightforward to implement.; Requires minimal extra space (`O(1)`), making it very memory-efficient.
**Cons:** For the given constraints, this approach is less efficient than the sweep-line algorithm. The time complexity has a factor of `N` multiplied by a constant `K` (number of iterations), which is larger than `N log N`.
### Explanation
The core idea is to find a value `h` such that the function `AreaBelow(h)` equals `TotalArea / 2`. Since `AreaBelow(h)` is monotonic (as `h` increases, the area below it can only increase or stay the same), we can apply binary search on the value of `h`.

First, we compute the total area of all squares and determine the target area, which is half of the total. Then, we establish a search range for `h`. The lowest possible `y` is 0, and the highest can be the maximum top edge among all squares. 

We then perform a standard binary search. For each midpoint `mid` of our current search range, we calculate the total area below `y = mid`. If this area is smaller than our target, we know the line must be higher, so we discard the lower half of the search range. If the area is greater than or equal to the target, the line might be correct or too high, so we discard the upper half to seek the minimum possible `h`. This process is repeated for a fixed number of iterations (e.g., 100) to guarantee the required precision.

```java
class Solution {
    public double separateSquares(int[][] squares) {
        long totalArea = 0;
        double maxY = 0;
        for (int[] s : squares) {
            totalArea += (long)s[2] * s[2];
            maxY = Math.max(maxY, s[1] + s[2]);
        }
        double targetArea = totalArea / 2.0;

        double low = 0.0;
        double high = maxY;

        // Binary search for 100 iterations for high precision
        for (int i = 0; i < 100; ++i) {
            double mid = low + (high - low) / 2;
            if (calculateAreaBelow(mid, squares) < targetArea) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return high;
    }

    private double calculateAreaBelow(double h, int[][] squares) {
        double area = 0;
        for (int[] s : squares) {
            long y = s[1];
            long l = s[2];
            if (h <= y) {
                continue;
            }
            if (h >= y + l) {
                area += (double)l * l;
            } else {
                area += (double)l * (h - y);
            }
        }
        return area;
    }
}
```
### Algorithm
- Calculate `totalArea` by summing `l*l` for all squares. The `targetArea` is `totalArea / 2.0`.
- Define a search range for the y-coordinate `h`. A safe lower bound is `0.0` and a safe upper bound can be the maximum possible top edge of any square (`max(y_i + l_i)`), or a large enough number like `2e9 + 7`.
- Perform a binary search for `h` within this range for a fixed number of iterations (e.g., 100) to achieve the required precision.
- In each iteration, with a candidate value `mid`:
  - Define a helper function `calculateAreaBelow(mid, squares)` that iterates through all `N` squares and sums up the area below the line `y = mid`.
  - For each square `[x, y, l]`, the area contribution is:
    - `0` if `mid <= y`.
    - `l*l` if `mid >= y + l`.
    - `l * (mid - y)` if `y < mid < y + l`.
  - If `calculateAreaBelow(mid, squares)` is less than `targetArea`, it means `mid` is too low, so we update `low = mid`.
  - Otherwise, `mid` is a potential answer or is too high. To find the minimum `h`, we search in the lower half by updating `high = mid`.
- After the iterations, `high` (or `low`) will be the answer.

## Sweep-line Algorithm
This approach provides a more direct, analytical solution using a sweep-line algorithm. We can think of a horizontal line sweeping upwards from `y = -∞`. The area below this line increases, and the rate of increase (the slope) changes only at the bottom and top edges of the squares. By processing these "event points" in order, we can track the accumulated area and pinpoint the exact y-coordinate where it reaches the target value.
**Time:** O(N log N), dominated by the process of inserting `2N` events into a sorted data structure (like a `TreeMap` or sorting a list). The final sweep is `O(N)`. · **Space:** O(N), as we need to store up to `2N` event points. In the `TreeMap` implementation, this is the space for the map entries.
**Pros:** More efficient than binary search for large N, with a time complexity of `O(N log N)`.; Calculates the answer analytically, providing an exact result (within floating-point precision) without iterative approximation.
**Cons:** More complex to conceptualize and implement compared to binary search.; Requires additional memory to store the event points.
### Explanation
The function `AreaBelow(h)` is a continuous, piecewise linear function. Its derivative with respect to `h` is the sum of the side lengths of all squares that the line `y=h` currently intersects. This derivative, or slope, is constant between any two y-coordinates corresponding to the top or bottom edges of squares.

This structure lends itself to a sweep-line algorithm. We create event points for each square's bottom edge (`y_i`) and top edge (`y_i + l_i`). At `y_i`, the slope of the area function increases by `l_i`. At `y_i + l_i`, it decreases by `l_i`.

We gather all `2N` such events and sort them by their y-coordinate. A `TreeMap` is ideal here, as it automatically sorts the events by key (the y-coordinate) and can aggregate slope changes at the same height. We then sweep a line from bottom to top, iterating through the sorted events. Between any two consecutive event points `y_1` and `y_2`, the slope is constant. We can calculate the area added in this strip and check if our `targetArea` falls within it. If it does, we can solve a simple linear equation to find the exact `h`. Since we process y-coordinates in increasing order, the first `h` we find will be the minimum.

```java
import java.util.Map;
import java.util.TreeMap;

class Solution {
    public double separateSquares(int[][] squares) {
        long totalArea = 0;
        for (int[] s : squares) {
            totalArea += (long)s[2] * s[2];
        }
        
        if (totalArea == 0) {
            return 0.0;
        }
        double targetArea = totalArea / 2.0;

        // Use a TreeMap to store events, which keeps them sorted by y-coordinate
        // and handles aggregation of slope changes at the same y.
        Map<Integer, Long> events = new TreeMap<>();
        for (int[] s : squares) {
            int y1 = s[1];
            int y2 = s[1] + s[2];
            int l = s[2];
            events.put(y1, events.getOrDefault(y1, 0L) + l);
            events.put(y2, events.getOrDefault(y2, 0L) - l);
        }

        double currentArea = 0;
        long currentSlope = 0;
        Integer last_y = null;

        for (Map.Entry<Integer, Long> entry : events.entrySet()) {
            int y = entry.getKey();
            
            if (last_y != null) {
                double areaInStrip = (double)currentSlope * (y - last_y);
                if (currentSlope > 0 && currentArea + areaInStrip >= targetArea) {
                    return last_y + (targetArea - currentArea) / currentSlope;
                }
                currentArea += areaInStrip;
            }
            
            currentSlope += entry.getValue();
            last_y = y;
        }
        
        return -1; // Should be unreachable given problem constraints
    }
}
```
### Algorithm
- First, calculate the `totalArea` of all squares and the `targetArea` (`totalArea / 2.0`).
- Create a list of "event points". For each square `[x, y, l]`, there are two events:
  - A 'start' event at `y`, which increases the rate of area accumulation (slope) by `l`.
  - An 'end' event at `y + l`, which decreases the slope by `l`.
- A `TreeMap` is an excellent data structure for this, mapping each y-coordinate to the net change in slope at that height.
- Sort these events by their y-coordinate. The `TreeMap` handles this automatically.
- Initialize `currentArea = 0.0`, `currentSlope = 0.0`, and `last_y` to the first event's y-coordinate.
- Iterate through the sorted event points (the entries of the `TreeMap`):
  - For each event at `y`, calculate the area accumulated in the strip between `last_y` and `y`: `areaInStrip = currentSlope * (y - last_y)`.
  - Check if the `targetArea` is crossed within this strip. This happens if `currentSlope > 0` and `currentArea + areaInStrip >= targetArea`.
  - If it is, the solution `h` can be found by solving a linear equation: `h = last_y + (targetArea - currentArea) / currentSlope`. Return this value.
  - If not, update `currentArea += areaInStrip`, update `currentSlope` with the change from the current event, and set `last_y = y`.