LeetCode Solutions Blog

Separate Squares II

Number: 3775

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of squares where each square is represented as [x, y, l] (with (x, y) being its bottom‐left coordinate and l the side length), find the minimum y-coordinate of a horizontal line that splits the union area of these squares (with overlapping portions counted only once) into two equal halves. Answers within 10⁻⁵ of the correct answer will be accepted.

Key Insights

The challenge is not only to compute the total union area of arbitrarily overlapping squares, but also to quickly determine how a horizontal line candidate divides this union into two parts.
A line sweep algorithm is effective to compute the union area of rectangles (squares) without overcounting overlapping areas.
For each candidate horizontal line, we consider only the parts of the squares that lie above that line (by adjusting the y-interval) and then compute their union area.
A binary search is used over possible y-values. At every step, we check if the union area for the part above the candidate line is at least half of the total union area.
A segment tree (or interval tree) is used to efficiently manage and merge intervals when calculating the union of 1D segments (the y intervals) during the sweep.

Space and Time Complexity

Time Complexity: O(n log n + m log m) where n is the number of squares and m is the number of events processed by the segment tree during the sweep. Space Complexity: O(n + m), due to storage of events and the segment tree data structure.

Solution

The solution converts each square to a rectangle [x, x+l, y, y+l]. First, the overall union area of all squares is calculated using a line sweep along the x-axis combined with a segment tree to efficiently maintain the active y-intervals (merging overlapping segments).

Then, for a given candidate horizontal line (candidateY), each square that intersects candidateY is “clipped” to the portion above the line. We compute the union area for these upper portions similarly.

A binary search is then applied over possible y-values to find the minimum candidateY for which the union area above the line is at least half of the total union area. The segment tree helps to quickly compute the union of adjusted rectangles at each binary search iteration.

Code Solutions

# Python solution with detailed comments

# SegmentTree used to efficiently compute total coverage in y-direction.
class SegmentTree:
    def __init__(self, coords):
        self.coords = coords  # Sorted unique y-coordinates.
        self.n = len(coords) - 1
        self.count = [0] * (self.n * 4)
        self.covered = [0] * (self.n * 4)
    
    # Update function adds delta to all segments in [ql, qr]
    def update(self, idx, l, r, ql, qr, delta):
        if ql > r or qr < l:
            return
        if ql <= l and r <= qr:
            self.count[idx] += delta
        else:
            mid = (l + r) // 2
            self.update(idx*2, l, mid, ql, qr, delta)
            self.update(idx*2+1, mid+1, r, ql, qr, delta)
        # If current node is covered at least once, the entire segment is covered.
        if self.count[idx] > 0:
            self.covered[idx] = self.coords[r+1] - self.coords[l]
        else:
            if l == r:
                self.covered[idx] = 0
            else:
                self.covered[idx] = self.covered[idx*2] + self.covered[idx*2+1]
    
    def query(self):
        return self.covered[1]

# Compute the union area from a list of rectangles (each as (x1, x2, y1, y2))
def union_area(rects):
    events = []
    y_coords = set()
    for x1, x2, y1, y2 in rects:
        events.append((x1, y1, y2, 1))   # entering event
        events.append((x2, y1, y2, -1))  # leaving event
        y_coords.add(y1)
        y_coords.add(y2)
    events.sort()
    sorted_y = sorted(list(y_coords))
    st = SegmentTree(sorted_y)
    prev_x = events[0][0]
    area = 0
    for x, y1, y2, typ in events:
        dx = x - prev_x
        area += dx * st.query()
        # Find the index range for y1, y2 in sorted_y.
        l = sorted_y.index(y1)
        r = sorted_y.index(y2) - 1
        st.update(1, 0, st.n-1, l, r, typ)
        prev_x = x
    return area

# Calculate union area of parts of squares above candidateY.
def area_above_line(squares, candidateY):
    rects = []
    for x, y, l in squares:
        top = y + l
        # Skip squares entirely below candidateY.
        if top <= candidateY:
            continue
        # Use candidateY as lower bound if square is partially cut.
        lower_bound = max(y, candidateY)
        rects.append((x, x+l, lower_bound, top))
    if not rects:
        return 0
    return union_area(rects)

def separate_squares(squares):
    # Convert each square to a rectangle.
    rects = [(x, x+l, y, y+l) for x, y, l in squares]
    total_area = union_area(rects)
    # Binary search over y-coordinate.
    lo = min(y for _, y, _ in squares)
    hi = max(y + l for _, y, l in squares)
    ans = hi
    # 40 iterations give sufficient precision.
    for _ in range(40):
        mid = (lo + hi) / 2
        above = area_above_line(squares, mid)
        # If the area above is at least half, move lo up.
        if above >= total_area / 2:
            ans = mid
            lo = mid
        else:
            hi = mid
    return ans

# Example usage:
if __name__ == "__main__":
    squares1 = [[0, 0, 1], [2, 2, 1]]
    print(separate_squares(squares1))  # Expected approx 1.00000

    squares2 = [[0, 0, 2], [1, 1, 1]]
    print(separate_squares(squares2))  # Expected approx 1.00000