Separate Squares II

김견지·2025년 4월 18일

CodingTest CodingTest Solution Segment Tree leetcode python

LeetCode

목록 보기

12/13

🔗 submission url

🧩 Problem: Separate Squares II

LeetCode link

Description

You are given a 2D integer arraysquares. Eachsquares[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 theminimumy-coordinate value of a horizontal line such that the total area covered by squares above the lineequalsthe total area covered by squares below the line.Answers within10-5of the actual answer will be accepted.Note: Squaresmayoverlap. Overlapping areas should be countedonly oncein this version.

Examples

Example 1:

Input: squares = [[0,0,1],[2,2,1]]
Output: 1.00000
Explanation: Any horizontal line betweeny = 1andy = 2results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.

Example 2:

Input: squares = [[0,0,2],[1,1,1]]
Output: 1.00000
Explanation: Since the blue square overlaps with the red square, it will not be counted again. Thus, the liney = 1splits the squares into two equal parts.

Constraints

1 <= squares.length <= 5 * 10^4
squares[i] = [xi, yi, li]
squares[i].length == 3
0 <= xi, yi<= 10^9
1 <= li<= 10^9
The total area of all the squares will not exceed 10^15.

My Solution

⏱ Runtime: 7471 ms
🧠 Memory: 74.4 MB

Code

from copy import deepcopy

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        y_grid = []
        diffs = {}
        for x, y, l in squares:
            y_grid += [y, y + l]
            if y not in diffs.keys():
                diffs[y] = []
            if y + l not in diffs.keys():
                diffs[y + l] = []

            diffs[y].append([True, x, x + l])
            diffs[y + l].append([False, x, x + l])

        y_grid = list(set(y_grid))
        y_grid.sort()
        num_grid = len(y_grid) - 1

        area = [0] * (num_grid + 1)
        x_ranges = [0] * num_grid
        xs = [[]] * num_grid
        for i in range(num_grid):
            for diff in diffs[y_grid[i]]:
                if diff[0]:
                    xs[i].append(diff[1:])
                else:
                    xs[i].remove(diff[1:])
            x_ranges[i] = self.unify_xs(deepcopy(xs[i]))
            area[i + 1] = area[i] + (y_grid[i + 1] - y_grid[i]) * x_ranges[i]

        target_area = area[-1] / 2
        for i in range(num_grid):
            if area[i + 1] >= target_area:
                return y_grid[i + 1] - ((area[i + 1] - target_area) / x_ranges[i])

    def unify_xs(self, lines):
        lines.sort(key=lambda x : x[0])
        if len(lines) == 0:
            return 0

        line = lines[0]
        total = 0
        if len(lines) > 1:
            for x1, x2 in lines[1:]:
                if line[1] < x1:
                    total += line[1] - line[0]
                    line = [x1, x2]
                else:
                    line[1] = max(line[1], x2)
        total += line[1] - line[0]
        return total

Approach

Almost same as "Separate Squares 1" (Check link below)
https://velog.io/@kyeonji/Separate-Squares-I

But I saved all ranges of x that is in i-th y grid.
And add them up with line sweep.

🔁 Feedback

Algorithm

line sweep
The line sweep algorithm is a technique that processes events in sorted order along one dimension—typically using a moving line—to efficiently detect and handle geometric relationships or intervals. (ChatGPT)

If there's lines like below,

You can process the event from the left.
For example if you want to calculate the range that covered by lines,

    def line_sweep(self, lines):
        lines.sort(key=lambda x : x[0])  # ESSENTIAL!
        
        line = lines[0]  # Initial line
        total = 0
        for x1, x2 in lines[1:]:
            if line[1] < x1:  # Not overlapped
                total += line[1] - line[0]  # "Process"
                line = [x1, x2]  # Set new line
            else:  # Overlapped
                line[1] = max(line[1], x2)  # Extend line
        total += line[1] - line[0]  # Just a last process
        return total