LeetCode 3454 - Separate Squares II

This problem asks us to find the smallest horizontal line y = H that divides the union area of a collection of axis-aligned squares into two equal halves.

leetcodehardarraybinary-searchsegment-treesweep-line

LeetCode Problem 3454

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Segment Tree, Sweep Line

Solution

LeetCode 3454 - Separate Squares II

Problem Understanding

This problem asks us to find the smallest horizontal line y = H that divides the union area of a collection of axis-aligned squares into two equal halves.

Each square is represented as:

  • (xi, yi) = bottom-left corner
  • li = side length

Therefore, a square covers:

  • x-range: [xi, xi + li)
  • y-range: [yi, yi + li)

The key difference between this problem and the easier version is that overlapping regions are counted only once. We are not summing individual square areas. Instead, we must consider the area of the geometric union of all squares.

For a chosen horizontal line y = H:

  • Area below the line consists of the portion of the union with y < H
  • Area above the line consists of the portion of the union with y > H

We must find the minimum value of H such that these two areas are equal.

The constraints are large:

  • Up to 5 × 10^4 squares
  • Coordinates up to 10^9
  • Total area can reach 10^15

A geometric grid simulation is impossible. Even storing all covered cells would be infeasible.

The important observation is that the union area changes only at square boundaries. This suggests using a sweep-line algorithm combined with coordinate compression and segment tree techniques.

Several edge cases require careful handling:

  • Many squares may overlap heavily.
  • Multiple squares may start or end at the same y-coordinate.
  • The answer may lie strictly inside an interval between sweep events.
  • The equal-area condition may hold for an entire range of y-values, and we must return the minimum valid y-coordinate.
  • Coordinates are extremely large, so floating point calculations should be postponed until the final step. Here’s a fully detailed technical solution guide for LeetCode 3454 following your requested format.

Problem Understanding

The problem asks us to find a horizontal line y = L that splits a collection of squares on a 2D plane such that the total area above the line equals the total area below the line. Each square is given as [xi, yi, li], where (xi, yi) is the bottom-left corner and li is the side length. Squares may overlap, and overlapping areas must be counted only once when calculating the total covered area.

The input is a list of up to 5 * 10^4 squares, each with coordinates up to 10^9 and side lengths up to 10^9. The total area covered by all squares does not exceed 10^15. This tells us that brute-force approaches that iterate over every potential y line or every integer coordinate are not feasible due to the huge coordinate range.

Edge cases to be aware of include squares that are completely disjoint, squares that fully overlap, and very large squares that dominate the covered area. The problem guarantees at least one valid line exists since the total area can always be split.

The output is the minimum y-coordinate satisfying the area equality, accurate within 1e-5.

Approaches

Brute Force

A naive idea is to define a function:

$$F(H)=\text{union area below }H$$

and repeatedly compute it for different values of H.

To evaluate F(H), we could clip every square at height H, compute the union area of the resulting rectangles, and compare it against half of the total union area.

Computing a rectangle union area already requires a sweep-line algorithm with coordinate compression. Doing this separately for every binary-search step would be extremely expensive.

If one union-area computation costs O(n log n), then performing it dozens of times becomes prohibitively expensive for n = 5 × 10^4.

Key Insight

Instead of repeatedly recomputing union areas, we can compute the entire area distribution as a function of y in one sweep.

Consider sweeping upward along the y-axis.

At any height interval:

$$[y_i, y_{i+1})$$

the set of active squares does not change.

Therefore the union width along the x-axis is constant throughout that interval.

Let:

$$W$$

be the union width of active x-intervals.

Then the area accumulated over that vertical strip is:

$$W \cdot (y_{i+1}-y_i)$$

This means the cumulative area function is piecewise linear.

We can:

  1. Compute the total union area.
  2. Compute cumulative area strip by strip.
  3. Find the strip containing half the total area.
  4. Solve a simple linear equation inside that strip.

This requires only a single sweep-line pass.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(log C × n log n) or worse O(n) Recomputes union area many times
Optimal O(n log n) O(n) Single sweep line with segment tree

Algorithm Walkthrough

Step 1: Create sweep events

For every square:

  • Add an entering event at y = yi
  • Add a leaving event at y = yi + li

Each event contributes the x-interval:

$$[x_i,;x_i+l_i)$$

and a delta:

  • +1 when entering
  • -1 when leaving

These events describe when an interval becomes active or inactive during the vertical sweep.

Step 2: Coordinate compress x-values

The segment tree only needs interval boundaries.

Collect all:

  • xi
  • xi + li

Sort and deduplicate them.

The elementary x-segments are formed between consecutive compressed coordinates.

Coordinate compression reduces huge coordinates up to 10^9 into indices suitable for a segment tree.

Step 3: Build a segment tree

For every node store:

  • Coverage count
  • Covered length

If a node's coverage count is positive, the entire represented x-range is covered.

Otherwise, its covered length equals the sum of its children's covered lengths.

The root always contains the current union width along the x-axis.

Step 4: Sweep upward and record strips

Process y-values in ascending order.

Suppose the current union width is:

$$W$$

and the next event occurs at:

$$y_{next}$$

Then:

$$\text{strip area} = W \times (y_{next}-y)$$

Store:

  • lower y
  • upper y
  • width W
  • cumulative area before the strip

These strips completely describe the cumulative area function.

Step 5: Compute total union area

The total union area is simply the sum of all strip areas generated during the sweep.

Let:

$$A$$

be the total area.

The target area below the answer line is:

$$A/2$$

Step 6: Locate the target strip

Traverse the recorded strips.

For a strip:

$$[y_1,y_2)$$

with width:

$$W$$

the area inside the strip is:

$$W(y_2-y_1)$$

Find the first strip where the cumulative area reaches or exceeds:

$$A/2$$

Step 7: Solve inside the strip

Let:

  • prefix = area accumulated before this strip
  • need = A/2 - prefix

Inside the strip, area grows linearly:

$$\text{area gained} = W(H-y_1)$$

Set:

$$W(H-y_1)=need$$

and solve:

$$H = y_1+\frac{need}{W}$$

This is the smallest y-coordinate where cumulative area reaches half the total union area.

Why it works

Between consecutive sweep events, the active set of squares does not change. Therefore the union width along the x-axis is constant throughout that interval. The cumulative area function is thus piecewise linear and monotonic. The sweep computes every linear segment exactly. Since the target area is half the total union area, it must lie inside one of these segments. Solving the corresponding linear equation yields the unique smallest y-coordinate where the lower area equals half of the total union area. A naive approach would iterate over every potential horizontal line y between the lowest and highest points of the squares. For each y, compute the union of square areas above and below the line using a grid or interval union approach. This would yield a correct answer but is prohibitively slow, because iterating over all possible y values or performing union calculations for large coordinates is extremely inefficient. The time complexity could easily be O((max_y - min_y) * n log n), which is infeasible for max_y ~ 10^9.

Optimal Approach

The key insight is that the problem can be reduced to a sweep line over the y-axis combined with a segment tree or interval union for the x-axis. By sweeping from bottom to top, we can compute the cumulative area covered by squares up to a certain y-coordinate. Once we know the total area, we can use binary search on y to find the precise line where the area above equals the area below.

The steps are:

  1. Transform each square into events along the y-axis: a square contributes to the area starting from its bottom edge and stops at its top edge.
  2. Maintain active x-intervals for each y using a segment tree or sorted intervals to calculate the horizontal coverage at each y.
  3. Sweep the y-axis while accumulating the covered area.
  4. Use binary search to find the y-coordinate where the accumulated area reaches half of the total union area.

This reduces the problem from iterating over billions of coordinates to O(n log n) operations for sorting events and handling interval unions.

Approach Time Complexity Space Complexity Notes
Brute Force O(max_y * n log n) O(n) Iterate over all possible y-coordinates, compute union each time
Optimal O(n log n) O(n) Sweep line on y-axis + segment tree for union on x-axis, then binary search

Algorithm Walkthrough

  1. Generate Events: For each square [x, y, l], generate two events: start at y and end at y + l. Each event carries the x-interval [x, x + l].
  2. Sort Events: Sort events by y-coordinate. If two events share the same y, process start before end.
  3. Sweep Line: Initialize a segment tree or interval structure to track active x-intervals. For each event, update the active intervals and calculate the horizontal coverage. Multiply by the y-gap from the previous event to get the incremental area.
  4. Compute Total Area: Continue the sweep until all events are processed. This gives the total area covered by all squares.
  5. Binary Search: Use binary search over the y-axis range to find the y-coordinate where the accumulated area reaches half of the total area. For each mid-point, repeat the sweep logic restricted to [0, mid_y] to compute the lower area.
  6. Precision Handling: Stop the binary search when the difference is within 1e-6 to satisfy the 1e-5 requirement. Return the minimum y-coordinate that balances the areas.

Why it works: The sweep line ensures that the area covered is correctly calculated even with overlapping squares, because the interval union prevents double counting. Binary search is valid because the area function is monotonic in y - as y increases, the area below the line only increases.

Python Solution

from typing import List
from bisect import bisect_left

class SegmentTree:
    def __init__(self, xs):
        self.xs = xs
        self.n = len(xs) - 1
        self.cover = [0] * (self.n * 4)
        self.length = [0] * (self.n * 4)

    def update(self, node, left, right, ql, qr, delta):
        if ql >= right or qr <= left:
            return

        if ql <= left and right <= qr:
            self.cover[node] += delta
        else:
            mid = (left + right) // 2
            self.update(node * 2, left, mid, ql, qr, delta)
            self.update(node * 2 + 1, mid, right, ql, qr, delta)

        if self.cover[node] > 0:
            self.length[node] = self.xs[right] - self.xs[left]
        elif right - left == 1:
            self.length[node] = 0
        else:
            self.length[node] = (
                self.length[node * 2]
                + self.length[node * 2 + 1]
            )

    def covered_length(self):
        return self.length[1]

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        xs = []
        events = []

        for x, y, l in squares:
            x2 = x + l
            y2 = y + l

            xs.append(x)
            xs.append(x2)

            events.append((y, 1, x, x2))
            events.append((y2, -1, x, x2))

        xs = sorted(set(xs))

        events.sort()

        seg = SegmentTree(xs)

        strips = []

        prev_y = events[0][0]
        idx = 0
        m = len(events)

        total_area = 0

        while idx < m:
            y = events[idx][0]

            width = seg.covered_length()

            if y > prev_y:
                height = y - prev_y
                area = width * height

                strips.append(
                    (prev_y, y, width, total_area)
                )

                total_area += area

            while idx < m and events[idx][0] == y:
                _, delta, x1, x2 = events[idx]

                l = bisect_left(xs, x1)
                r = bisect_left(xs, x2)

                seg.update(1, 0, seg.n, l, r, delta)
                idx += 1

            prev_y = y

        target = total_area / 2.0

        for y1, y2, width, prefix in strips:
            strip_area = width * (y2 - y1)

            if prefix + strip_area >= target:
                need = target - prefix

                if width == 0:
                    return float(y1)

                return y1 + need / width

        return float(prev_y)

Implementation Explanation

The solution first converts every square into two sweep events. Entering events add an x-interval to the active set, while leaving events remove it.

All x-coordinates are compressed because coordinates may be as large as 10^9. The segment tree operates on compressed indices and maintains the total union width of active x-intervals.

During the sweep, the root of the segment tree always stores the current union width. Whenever the sweep moves from one y-coordinate to the next event y-coordinate, the active configuration remains unchanged, so the strip area is simply width multiplied by height.

Each strip is recorded together with the cumulative area before that strip. After the total union area is known, the algorithm searches for the strip containing the halfway point. Because area grows linearly within a strip, the exact answer is obtained using a simple division. import bisect

class Solution: def separateSquares(self, squares: List[List[int]]) -> float: events = [] xs = set() for x, y, l in squares: events.append((y, 1, x, x + l)) # start event events.append((y + l, -1, x, x + l)) # end event xs.add(x) xs.add(x + l)

    xs = sorted(xs)
    x_index = {x_val: i for i, x_val in enumerate(xs)}
    n = len(xs)
    
    count = [0] * (n - 1)
    
    def compute_area_up_to(y_limit: float) -> float:
        prev_y = 0
        area = 0
        active = [0] * (n - 1)
        for y, typ, x1, x2 in sorted(events):
            if y > y_limit:
                break
            dx = 0
            for i in range(n - 1):
                if active[i] > 0:
                    dx += xs[i + 1] - xs[i]
            area += dx * (y - prev_y)
            prev_y = y
            idx1, idx2 = x_index[x1], x_index[x2]
            for i in range(idx1, idx2):
                active[i] += typ
        dx = 0
        for i in range(n - 1):
            if active[i] > 0:
                dx += xs[i + 1] - xs[i]
        area += dx * (y_limit - prev_y)
        return area
    
    total_area = compute_area_up_to(float('inf'))
    low, high = 0, max(y + l for _, y, l in squares)
    for _ in range(100):
        mid = (low + high) / 2
        if compute_area_up_to(mid) < total_area / 2:
            low = mid
        else:
            high = mid
    return low


**Explanation**: This Python solution builds y-events for each square, compresses x-coordinates to efficiently track active intervals, and uses a sweep to calculate the area below any candidate y. Binary search finds the line splitting the area evenly.

## Go Solution

```go
package main

import (
	"sort"
)

type Event struct {
	y     int64
	delta int
	x1    int64
	x2    int64
}

type SegmentTree struct {
	xs     []int64
	cover  []int
	length []int64
	n      int
}

func NewSegmentTree(xs []int64) *SegmentTree {
	n := len(xs) - 1

	return &SegmentTree{
		xs:     xs,
		cover:  make([]int, n*4),
		length: make([]int64, n*4),
		n:      n,
	}
}

func (st *SegmentTree) update(node, left, right, ql, qr, delta int) {
	if ql >= right || qr <= left {
		return
	}

	if ql <= left && right <= qr {
		st.cover[node] += delta
	} else {
		mid := (left + right) / 2
		st.update(node*2, left, mid, ql, qr, delta)
		st.update(node*2+1, mid, right, ql, qr, delta)
	}

	if st.cover[node] > 0 {
		st.length[node] = st.xs[right] - st.xs[left]
	} else if right-left == 1 {
		st.length[node] = 0
	} else {
		st.length[node] =
			st.length[node*2] +
				st.length[node*2+1]
	}
}

func (st *SegmentTree) coveredLength() int64 {
	return st.length[1]
}

func separateSquares(squares [][]int) float64 {
	var xs []int64
	var events []Event

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

		x2 := x + l
		y2 := y + l

		xs = append(xs, x, x2)

		events = append(events, Event{y, 1, x, x2})
		events = append(events, Event{y2, -1, x, x2})
	}

	sort.Slice(xs, func(i, j int) bool {
		return xs[i] < xs[j]
	})

	compressed := make([]int64, 0)
	for _, x := range xs {
		if len(compressed) == 0 || compressed[len(compressed)-1] != x {
			compressed = append(compressed, x)
		}
	}
	xs = compressed

	sort.Slice(events, func(i, j int) bool {
		return events[i].y < events[j].y
	})

	st := NewSegmentTree(xs)

	type Strip struct {
		y1     int64
		y2     int64
		width  int64
		prefix int64
	}

	var strips []Strip

	prevY := events[0].y
	totalArea := int64(0)

	idx := 0

	for idx < len(events) {
		y := events[idx].y

		width := st.coveredLength()

		if y > prevY {
			area := width * (y - prevY)

			strips = append(strips, Strip{
				prevY,
				y,
				width,
				totalArea,
			})

			totalArea += area
		}

		for idx < len(events) && events[idx].y == y {
			ev := events[idx]

			l := sort.Search(len(xs), func(i int) bool {
				return xs[i] >= ev.x1
			})

			r := sort.Search(len(xs), func(i int) bool {
				return xs[i] >= ev.x2
			})

			st.update(1, 0, st.n, l, r, ev.delta)

			idx++
		}

		prevY = y
	}

	target := float64(totalArea) / 2.0

	for _, strip := range strips {
		stripArea :=
			float64(strip.width) *
				float64(strip.y2-strip.y1)

		if float64(strip.prefix)+stripArea >= target {
			need := target - float64(strip.prefix)

			if strip.width == 0 {
				return float64(strip.y1)
			}

			return float64(strip.y1) +
				need/float64(strip.width)
		}
	}

	return float64(prevY)
}

Go Specific Notes

The Go implementation mirrors the Python version closely. All geometric values are stored as int64 because coordinates and areas can exceed the range of 32-bit integers. The final answer is computed using float64. Coordinate compression uses sort.Search, which plays the same role as Python's bisect_left.

Worked Examples

Example 1

Input:

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

The squares do not overlap.

Events:

y Action
0 add [0,1)
1 remove [0,1)
2 add [2,3)
3 remove [2,3)

Sweep:

Strip Width Height Area Prefix Before
[0,1) 1 1 1 0
[1,2) 0 1 0 1
[2,3) 1 1 1 1

Total area:

2

Target:

1

The target is reached at the end of the first strip.

Answer:

0 + 1/1 = 1

Example 2

Input:

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

The second square is completely inside the first.

Union area:

4

Events:

y Active Union Width
0 2
1 2
2 0

Strips:

Strip Width Height Area
[0,1) 2 1 2
[1,2) 2 1 2

Total area:

4

Target:

2

The target is reached exactly at:

y = 1

Answer:

1.0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting events and segment tree updates
Space O(n) Coordinate compression, events, segment tree

The algorithm creates 2n sweep events and 2n compressed x-coordinates. Every event performs one segment-tree update in O(log n) time. Therefore the total complexity is O(n log n), which is efficient enough for n = 5 × 10^4.

Test Cases

sol = Solution()

assert abs(sol.separateSquares([[0, 0, 1], [2, 2, 1]]) - 1.0) < 1e-5
# two disjoint squares

assert abs(sol.separateSquares([[0, 0, 2], [1, 1, 1]]) - 1.0) < 1e-5
# nested overlap

assert abs(sol.separateSquares([[0, 0, 2]]) - 1.0) < 1e-5
# single square

assert abs(sol.separateSquares([[0, 0, 4], [0, 0, 4]]) - 2.0) < 1e-5
# identical overlapping squares

assert abs(sol.separateSquares([[0, 0, 2], [2, 0, 2]]) - 1.0) < 1e-5
# touching but non-overlapping

assert abs(sol.separateSquares([[0, 0, 10], [2, 2, 2]]) - 5.0) < 1e-5
# one square fully inside another

assert abs(sol.separateSquares([[0, 0, 1], [0, 2, 1]]) - 1.0) < 1e-5
# answer lies in a zero-area gap

assert abs(sol.separateSquares([[10**9, 10**9, 10**9]]) - 1.5e9) < 1e-5
# very large coordinates

assert abs(
    sol.separateSquares([
        [0, 0, 3],
        [1, 0, 3],
        [2, 0, 3]
    ]) - 1.5
) < 1e-5
# heavy horizontal overlap

Test Summary

Test Why
Two disjoint squares Basic non-overlapping behavior
Nested square Overlap counted only once
Single square Smallest valid input
Identical squares Complete overlap
Touching squares Shared boundary only
Contained square Union equals outer square
Vertical gap Minimum valid y in a flat region
Large coordinates Overflow safety
Heavy overlap Stress union-width computation

Edge Cases

Completely Overlapping Squares

Multiple squares may occupy exactly the same region. A naive solution that sums individual areas would overcount significantly. The segment tree stores coverage counts and only measures union length, so overlapping intervals contribute exactly once regardless of how many squares cover them.

Answer Inside a Gap With No Area

The cumulative area function can become flat when there are no active squares between two event heights. If half the area is reached at the start of such a gap, every y-value inside the gap satisfies the condition. The problem asks for the minimum valid y-coordinate, and the algorithm naturally returns the beginning of that strip because it finds the first location where cumulative area reaches the target.

Extremely Large Coordinates

Coordinates and side lengths can reach 10^9, producing areas up to 10^15. Using 32-bit integers would overflow. Both implementations use 64-bit integer arithmetic for coordinates, widths, heights, and areas. Floating point arithmetic is used only when computing the final answer.

Many Events Sharing the Same Y Coordinate

Several squares may start or end at the same height. Processing them one by one could incorrectly create zero-height strips. The sweep groups all events at the same y-coordinate together and updates the segment tree only after accounting for the area below that level, ensuring the active set is always correct for the next strip.

Heavy Overlap Along the X Axis

Large numbers of active squares may overlap horizontally. A simple interval list would require repeated merging and become too slow. The segment tree maintains the union width in O(log n) per update, regardless of how much overlap exists. "sort" )

func separateSquares(squares [][]int) float64 { type Event struct { y, typ, x1, x2 int }

events := []Event{}
xsSet := map[int]struct{}{}
for _, sq := range squares {
    x, y, l := sq[0], sq[1], sq[2]
    events = append(events, Event{y, 1, x, x + l})
    events = append(events, Event{y + l, -1, x, x + l})
    xsSet[x] = struct{}{}
    xsSet[x+l] = struct{}{}
}

xs := []int{}
for x := range xsSet {
    xs = append(xs, x)
}
sort.Ints(xs)
xIndex := map[int]int{}
for i, v := range xs {
    xIndex[v] = i
}
n := len(xs)

computeArea := func(yLimit float64) float64 {
    prevY := 0.0
    area := 0.0
    active := make([]int, n-1)
    sort.Slice(events, func(i, j int) bool {
        if events[i].y == events[j].y {
            return events[i].typ > events[j].typ
        }
        return events[i].y < events[j].y
    })
    for _, e := range events {
        if float64(e.y) > yLimit {
            break
        }
        dx := 0.0
        for i := 0; i < n-1; i++ {
            if active[i] > 0 {
                dx += float64(xs[i+1] - xs[i])
            }
        }
        area += dx * (float64(e.y) - prevY)
        prevY = float64(e.y)
        for i := xIndex[e.x1]; i < xIndex[e.x2]; i++ {
            active[i] += e.typ
        }
    }
    dx := 0.0
    for i := 0; i < n-1; i++ {
        if active[i] > 0 {
            dx += float64(xs[i+1] - xs[i])
        }
    }
    area += dx * (yLimit - prevY)
    return area
}

totalArea := compute