Lowest Horizontal Cut That Splits Square Cakes Into Equal Total Areas
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Several square cakes sit on a table, each with its sides parallel to the table's edges. You make one long horizontal cut across the whole table, along a line `y = h`. Every cake crossed by the line is split into a part below the line and a part above it; a cake entirely on one side stays whole on that side. Find where to cut so that the total area of cake below the line equals the total area of cake above it.
Model the table as the plane seen from above. Each cake is a square given by its bottom-left corner and its side length.
### Function Signature
```python
def balanced_cut_height(squares: list[list[int]]) -> list[int]:
```
### Rules
- `squares[i] = [x, y, side]` describes the square with corners `(x, y)` and `(x + side, y + side)`.
- Areas are added up cake by cake: if two squares overlap, the overlapping region counts once for each square.
- For a line `y = h`, the area below the line is the sum over all squares of the part of each square with y-coordinate less than `h`; the area above is defined symmetrically.
- Several heights can balance the areas (for example, anywhere in an empty gap between cakes). Return the **smallest** such `h`.
- Return `h` exactly as a reduced fraction `[numerator, denominator]` with `denominator > 0` and `gcd(numerator, denominator) = 1`. An integer height `h` is returned as `[h, 1]`.
### Constraints
- `1 <= len(squares) <= 10^4`
- `0 <= x, y <= 10^6`
- `1 <= side <= 10^3`
- The numerator and denominator of the answer are below `2^53`.
### Examples
**Example 1**
- Input: `squares = [[0, 0, 2], [1, 1, 1]]`
- Output: `[7, 6]`
- Explanation: The total area is 4 + 1 = 5, so each side needs 2.5. Up to `h = 1` only the first square is cut, giving area 2 below. Between 1 and 2 both squares are cut, adding 3 per unit of height, so the balance is reached at `h = 1 + 0.5 / 3 = 7/6`.
**Example 2**
- Input: `squares = [[0, 0, 1], [2, 2, 1]]`
- Output: `[1, 1]`
- Explanation: Any line between `y = 1` and `y = 2` leaves one square on each side. The smallest such height is 1.
**Example 3**
- Input: `squares = [[0, 0, 1], [0, 0, 1], [3, 1, 2]]`
- Output: `[3, 2]`
- Explanation: The first two squares are identical and both count. The total area is 1 + 1 + 4 = 6. At `h = 1` the area below is 2; above `y = 1` only the third square adds area, 2 per unit of height, so the remaining 1 is reached at `h = 1.5`.
Overview: Square cakes sit on a table with sides parallel to its edges; find the lowest horizontal cut line that splits the total cake area equally, returned as an exact fraction. Tests sweeping over heights, piecewise-linear area accumulation and exact arithmetic.
Several square cakes sit on a table, each with its sides parallel to the table's edges. You make one straight horizontal cut across the whole table along the line `y = h`. Every cake crossed by the line is split into a part below the line and a part above it; a cake entirely on one side of the line stays whole on that side. Find the height `h` at which the total area of cake below the line equals the total area of cake above it.
Model the table as the plane seen from above. Each cake is an axis-aligned square given by its bottom-left corner and its side length.
Implement `balanced_cut_height(squares)`.
**Rules**
- `squares[i] = [x, y, side]` describes the square with corners `(x, y)` and `(x + side, y + side)`.
- Areas are summed cake by cake: if two squares overlap, the overlapping region counts once for **each** square.
- For a line `y = h`, the area below is the sum over all squares of the part of each square with y-coordinate less than `h`; the area above is defined symmetrically.
- Several heights may balance the areas (for example, any height inside an empty vertical gap between cakes). Return the **smallest** such `h`.
- Return `h` exactly, as a reduced fraction `[numerator, denominator]` with `denominator > 0` and `gcd(numerator, denominator) = 1`. An integer height `h` is returned as `[h, 1]`.
**Constraints**
- `1 <= squares.length <= 10^4`
- `0 <= x, y <= 10^6`
- `1 <= side <= 10^3`
- The numerator and denominator of the answer are below `2^53`.
- Total area can reach `10^10`, and the answer's numerator can exceed `2^31 - 1`: use 64-bit integers (`long` in Java, `long long` in C++) for areas, intermediate products, and the returned pair.
**Example 1**
- Input: `squares = [[0, 0, 2], [1, 1, 1]]`
- Output: `[7, 6]`
- Explanation: The total area is 4 + 1 = 5, so each side needs 2.5. Up to `h = 1` only the first square is cut, giving area 2 below. Between `y = 1` and `y = 2` both squares are cut, adding 3 units of area per unit of height, so the balance is reached at `h = 1 + 0.5 / 3 = 7/6`.
**Example 2**
- Input: `squares = [[0, 0, 1], [2, 2, 1]]`
- Output: `[1, 1]`
- Explanation: Any line between `y = 1` and `y = 2` leaves one square on each side. The smallest such height is 1.
**Example 3**
- Input: `squares = [[0, 0, 1], [0, 0, 1], [3, 1, 2]]`
- Output: `[3, 2]`
- Explanation: The first two squares are identical and both count. The total area is 1 + 1 + 4 = 6. At `h = 1` the area below is 2; above `y = 1` only the third square adds area, 2 per unit of height, so the remaining 1 is reached at `h = 1.5`.
Constraints
- 1 <= squares.length <= 10^4
- squares[i] = [x, y, side]
- 0 <= x, y <= 10^6
- 1 <= side <= 10^3
- The numerator and denominator of the answer are below 2^53
- Total area can reach 10^10 and the answer's numerator can exceed 2^31 - 1, so use 64-bit integers
Examples
Input: ([[0, 0, 2], [1, 1, 1]],)
Expected Output: [7, 6]
Explanation: Example 1: balance inside the band where both squares are cut.
Input: ([[0, 0, 1], [2, 2, 1]],)
Expected Output: [1, 1]
Explanation: Example 2: every h in [1, 2] balances; the smallest is the gap's lower edge.
Hints
- Only the y-coordinate and side of each square matter. How does the area below the line change as h moves up by one unit?
- Between two consecutive bottom/top edges, the area below grows linearly at a rate equal to the total side length of the squares the line currently crosses.
- Sweep the sorted edge heights, find the first segment where the area below reaches half the total, and solve the linear equation there. Doubling every area keeps all arithmetic in integers.