LeetCode Problem 3453

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

LeetCode 3453 - Separate Squares I

Problem Understanding

We are given a collection of axis-aligned squares. Each square is represented by three integers:

• xi: x-coordinate of the bottom-left corner
• yi: y-coordinate of the bottom-left corner
• li: side length

The square therefore occupies the region:

$$[x_i, x_i + l_i] \times [y_i, y_i + l_i]$$

We must find the smallest horizontal line:

$$y = h$$

such that the total area of all squares above the line equals the total area of all squares below the line.

A very important detail is that overlapping regions are counted multiple times. This means we do not need to compute the geometric union of squares. Instead, every square contributes independently to the total area.

For any chosen height h:

• The portion of a square below the line contributes to the "below" area.
• The remaining portion contributes to the "above" area.

The goal is to find the minimum height where:

$$\text{areaBelow}(h) = \text{areaAbove}(h)$$

Since the total area is fixed:

$$\text{areaBelow}(h) = \frac{\text{totalArea}}{2}$$

So the problem becomes finding the smallest height where the accumulated area below the line reaches half of the total area.

Constraints Analysis

The number of squares can be as large as:

$$5 \times 10^4$$

Coordinates and side lengths can reach:

$$10^9$$

The total area of all squares is guaranteed not to exceed:

$$10^{12}$$

The large coordinate range immediately rules out any approach that scans heights one by one.

The answer is a real number and only needs accuracy within:

$$10^{-5}$$

This strongly suggests a binary search on the answer.

Important Edge Cases

Squares may overlap heavily. Since overlaps are counted multiple times, we should process each square independently.

Multiple valid heights may exist. The problem explicitly asks for the minimum valid height.

A line may lie entirely below or above a square. In those cases the square contributes either its full area or zero area to the lower region.

Very large coordinates and areas require careful handling of integer overflow in languages such as Go. Using 64-bit integers for area calculations is necessary.

Approaches

Brute Force

A naive idea is to try many candidate heights and compute the area above and below each height.

For a chosen height h, we can iterate through every square and determine how much of that square lies below the line.

This computation is correct because every square contributes independently.

The problem is choosing candidate heights. Heights are real numbers and coordinates may be as large as 10^9. Enumerating all possible heights is impossible.

Even checking every interesting y-coordinate and searching linearly would be far too expensive and would not provide the required precision.

Key Insight

For a square with bottom edge y and side length l, the area below height h is:

$$\begin{cases} 0 & h \le y\ l(h-y) & y < h < y+l\ l^2 & h \ge y+l \end{cases}$$

This function is continuous and monotonically increasing.

The total area below the line is the sum of these functions over all squares.

Therefore:

• areaBelow(h) is continuous.
• areaBelow(h) is monotonically increasing.

We need the smallest height where:

$$areaBelow(h) \ge \frac{totalArea}{2}$$

A monotonic continuous function immediately suggests binary search on the answer.

For each candidate height, we can compute the area below in O(n) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Impossible over continuous domain	O(1)	Cannot enumerate real-valued heights
Optimal	O(n log M)	O(1)	Binary search on height, where M is coordinate range

Here M is approximately 10^9.

Algorithm Walkthrough

1. Compute the total area of all squares.

For each square, add:

$$l^2$$

to totalArea. 2. Compute the target area.

Since we need equal area above and below:

$$target = \frac{totalArea}{2}$$ 3. Determine the binary search range.

The answer must lie between:

• smallest square bottom edge
• largest square top edge

4. Define a helper function belowArea(h).

For each square:

• If h <= y, contribution is 0.
• If h >= y + l, contribution is l².
• Otherwise contribution is:

$$l(h-y)$$ 5. Perform binary search.

Let mid = (left + right) / 2.

Compute belowArea(mid).

• If the area is at least target, the answer lies at mid or lower, so move right = mid.
• Otherwise move left = mid.

6. Repeat enough iterations.

About 60 iterations are sufficient to achieve much better than 10^{-5} precision. 7. Return right.

Because we always move the right boundary when the condition is satisfied, the binary search converges to the minimum valid height.

Why it works

For every square, the area below a horizontal line is a continuous non-decreasing function of the line height. Summing such functions preserves continuity and monotonicity.

Therefore the total area below the line forms a monotonic continuous function. There is a unique threshold where the area reaches half of the total area. Binary search correctly finds the smallest height whose accumulated area is at least half of the total area, which is exactly the required answer.

Python Solution

from typing import List

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        total_area = 0
        min_y = float("inf")
        max_y = 0

        for _, y, l in squares:
            total_area += l * l
            min_y = min(min_y, y)
            max_y = max(max_y, y + l)

        target = total_area / 2.0

        def area_below(height: float) -> float:
            area = 0.0

            for _, y, l in squares:
                top = y + l

                if height <= y:
                    continue

                if height >= top:
                    area += l * l
                else:
                    area += l * (height - y)

            return area

        left = float(min_y)
        right = float(max_y)

        for _ in range(60):
            mid = (left + right) / 2.0

            if area_below(mid) >= target:
                right = mid
            else:
                left = mid

        return right

The implementation begins by computing the total area and the search boundaries. The smallest square bottom edge provides a lower bound, while the largest square top edge provides an upper bound.

The helper function computes the accumulated area below a given height. Each square contributes independently. Depending on the relative position of the line, the contribution is either zero, the full square area, or a rectangular strip of area l * (height - y).

The binary search repeatedly evaluates the midpoint. If the area below already reaches half the total area, the answer may be smaller, so the search continues on the left half. Otherwise, the answer must be higher.

After 60 iterations, the interval becomes extremely small, providing more than enough precision for the required tolerance.

Go Solution

func separateSquares(squares [][]int) float64 {
	var totalArea int64 = 0

	minY := int64(1 << 60)
	var maxY int64 = 0

	for _, sq := range squares {
		y := int64(sq[1])
		l := int64(sq[2])

		totalArea += l * l

		if y < minY {
			minY = y
		}

		if y+l > maxY {
			maxY = y + l
		}
	}

	target := float64(totalArea) / 2.0

	areaBelow := func(height float64) float64 {
		area := 0.0

		for _, sq := range squares {
			y := float64(sq[1])
			l := float64(sq[2])
			top := y + l

			if height <= y {
				continue
			}

			if height >= top {
				area += l * l
			} else {
				area += l * (height - y)
			}
		}

		return area
	}

	left := float64(minY)
	right := float64(maxY)

	for i := 0; i < 60; i++ {
		mid := (left + right) / 2.0

		if areaBelow(mid) >= target {
			right = mid
		} else {
			left = mid
		}
	}

	return right
}

The Go implementation follows the same algorithm. The primary difference is the use of int64 for total area calculations to safely handle values up to 10^12. Floating point calculations are performed with float64, which provides sufficient precision for the required error tolerance.

Worked Examples

Example 1

Input:

[[0,0,1],[2,2,1]]

Total area:

Square	Area
(0,0,1)	1
(2,2,1)	1

Total:

2

Target:

1

Search range:

[0, 3]

Evaluate at h = 1:

Square	Contribution Below
[0,0,1]	1
[2,2,1]	0

Total below:

1

This already equals the target. Any height in [1,2] works, but binary search converges to the smallest valid value:

1.00000

Example 2

Input:

[[0,0,2],[1,1,1]]

Total area:

Square	Area
side 2	4
side 1	1

Total:

5

Target:

2.5

For a height between 1 and 2:

First square contributes:

$$2(h-0)$$

Second square contributes:

$$h-1$$

Therefore:

$$areaBelow(h)=2h+(h-1)=3h-1$$

Set equal to target:

$$3h-1=2.5$$

$$3h=3.5$$

$$h=\frac{7}{6}$$

$$h=1.1666667$$

Output:

1.16667

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log M)	Each binary search step scans all squares
Space	O(1)	Only a few variables are maintained

The binary search performs a constant number of iterations, approximately 60. Each iteration computes the area below the current height by scanning all n squares. Therefore the total complexity is O(60n), which simplifies to O(n log M). The algorithm uses only constant extra memory.

Test Cases

from math import isclose

sol = Solution()

# Example 1
assert isclose(
    sol.separateSquares([[0, 0, 1], [2, 2, 1]]),
    1.0,
    abs_tol=1e-5
)

# Example 2
assert isclose(
    sol.separateSquares([[0, 0, 2], [1, 1, 1]]),
    7.0 / 6.0,
    abs_tol=1e-5
)

# Single square, answer is its midpoint
assert isclose(
    sol.separateSquares([[0, 0, 10]]),
    5.0,
    abs_tol=1e-5
)

# Two identical overlapping squares
assert isclose(
    sol.separateSquares([[0, 0, 2], [0, 0, 2]]),
    1.0,
    abs_tol=1e-5
)

# Disjoint squares at different heights
assert isclose(
    sol.separateSquares([[0, 0, 1], [0, 10, 1]]),
    1.0,
    abs_tol=1e-5
)

# Large coordinates
assert isclose(
    sol.separateSquares([[0, 10**9, 10**6]]),
    10**9 + 5 * 10**5,
    abs_tol=1e-5
)

# Multiple squares sharing the same vertical span
assert isclose(
    sol.separateSquares([[0, 0, 4], [10, 0, 4], [20, 0, 4]]),
    2.0,
    abs_tol=1e-5
)

# Very small square
assert isclose(
    sol.separateSquares([[0, 0, 1]]),
    0.5,
    abs_tol=1e-5
)

Test Summary

Test	Why
Example 1	Verifies multiple valid answers and minimum valid height
Example 2	Verifies partial contributions from multiple squares
Single square	Tests midpoint behavior
Fully overlapping squares	Ensures overlap is counted multiple times
Widely separated squares	Tests gaps where area remains constant
Large coordinates	Verifies handling of large values
Same vertical span	Tests aggregated contributions
Unit square	Smallest non-trivial case

Edge Cases

Multiple Valid Heights

There may be an interval of heights where the area above and below are equal. Example 1 demonstrates this situation. A common mistake is returning any valid height rather than the smallest one. The binary search is designed to find the leftmost height satisfying areaBelow >= target, ensuring the minimum valid answer is returned.

Heavy Overlap Between Squares

Many geometric problems require computing unions of overlapping regions. Here, overlaps are counted multiple times. Treating the squares as a union would produce incorrect results. The implementation processes each square independently and simply sums their contributions, exactly matching the problem definition.

Very Large Coordinates and Areas

Coordinates and side lengths can be as large as 10^9, while the total area may reach 10^12. Using 32-bit integers would overflow. The Python solution naturally handles large integers, while the Go solution uses int64 for all area computations before converting to float64 for binary search calculations.

Heights Outside a Square's Vertical Range

When the line lies completely below or above a square, only zero or full area should be counted. Off-by-one style mistakes in these conditions can distort the monotonic function used by binary search. The implementation explicitly handles the three cases separately: completely below, completely above, and partially intersecting. This guarantees correct area computation for every square.