Separate Squares I

김견지·2025λ…„ 4μ›” 13일
0

LeetCode

λͺ©λ‘ 보기
10/13
post-thumbnail

πŸ”— submission url

🧩 Problem: Separate Squares I

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 of the squares above the lineequalsthe total area of the squares below the line.Answers within10-5of the actual answer will be accepted.Note: Squaresmayoverlap. Overlapping areas should be countedmultiple times.

Examples

Example 1:

Input: squares = [[0,0,1],[2,2,1]]
Output: 1.00000
Explanation: Any horizontal line betweeny = 1andy = 2will have 1 square unit above it and 1 square unit below it. The lowest option is 1.

Example 2:

Input: squares = [[0,0,2],[1,1,1]]
Output: 1.16667
Explanation: The areas are:Below the line:7/6 2 (Red) + 1/6 (Blue) = 15/6 = 2.5.Above the line:5/6 2 (Red) + 5/6 (Blue) = 15/6 = 2.5.Since the areas above and below the line are equal, the output is7/6 = 1.16667.

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^12.


My Solution

⏱ Runtime: 424 ms
🧠 Memory: 52.3 MB

Code

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        # Make Grid with Y values
        diffs = {}
        ys = []
        target_area = 0
        for x, y, l in squares:
            ys += [y, y + l]
            if y not in diffs.keys():
                diffs[y] = 0  # init
            if y + l not in diffs.keys():
                diffs[y + l] = 0  # init
            diffs[y] += l
            diffs[y + l] -= l
            target_area += l * l

        ys = list(set(ys))
        ys.sort()
        num_grid = len(ys) - 1
        # tree = [0] * num_grid
        target_area /= 2
        area = 0
        diff = diffs[ys[0]]
        print(diffs)
        for i in range(num_grid):
            # for j in range(i, len(tree)):  -> wrong solution (time out)
            #     tree[j] += diffs[ys[i]]
            area += diff * (ys[i + 1] - ys[i])
            if area >= target_area:
                return ys[i + 1] - ((area - target_area) / diff)  # refinement
            diff += diffs[ys[i + 1]]

            
                   

Approach

At first, I thought process below
1. Sperated y grids
2. Check boxes in i-th y grid
3. If sum of area >= target_area, calculate adjusted y with difference between area and target_area

But this approach exceeded time limit.
Reason: Used double for loop for phase 2

So, I looked up for better solution.
While getting y grids, I could save x values at each y grid.
My second approach is below.
1. Sperated y grids while saving x values at each y grid. Used dict to save x values to get values easily later.
2. Get x and updated all the grids from i to the end. -> This is the codes I commented out.
3. If sum of area >= target_area, calculate adjusted y with difference between area and target_area

Again, time out. Because it wasted time while I update all the grids.
My third approach.
1. Sperated y grids while saving x values at each y grid. Used dict to save x values to get values easily later.
2. Get x and just added (or subtracted) differece.
3. If sum of area >= target_area, calculate adjusted y with difference between area and target_area

FINALLY SUCCEED LOL

Python Grammar

# sort list with lambda
squares.sort(key = lambda x :x[1]) # sort with y
	

πŸ” Feedback

Algorithm

Segment Tree
A data structure that can compute the sum of an array in O(log N) time.
You have to implement 3 big functions
1. build(data, node, start, end) : build tree
2. update(index, value, node, start, end) : update index-th element to value
3. query(l, r, node, start, end) : get sum from l to r

Key point

  • node, start, end is needed to specify tree
  • leaf node get value from data directly
  • otherwise (for parents node), n-th = (2n+1)-th + (2n+2)-th

My code

class MySegmentTree:
    def __init__(self, data):
        self.N = len(data)
        self.tree = [0] * (4 * self.N)  # size of tree can't exceed 4N
        self.build(data, 0, 0, self.N - 1)
    
    def build(self, data, node, start, end):
        """Builds the segment tree recursively.

        Args:
            data (List[int]): Original array.
            node (int): Current node index in the segment tree.
            start (int): Start index of the current segment.
            end (int): End index of the current segment.
        """
        if start == end:  # leaf node
            self.tree[node] = data[start]
            return

        mid = (start + end) // 2
        self.build(data, 2 * node + 1, start, mid)
        self.build(data, 2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def update(self, index, value, node, start, end):
        """Updates a single element in the segment tree.

        Args:
            index (int): The index of the element to update.
            value (int): The new value to set.
            node (int): Current node index.
            start (int): Start of the segment.
            end (int): End of the segment.
        """
        if start == end:  # leaf node
            self.tree[node] = value  # update that node
        else:
            mid = (start + end) // 2
            if index <= mid:
                self.update(index, value, 2 * node + 1, start, mid)  # update left
            else:
                self.update(index, value, 2 * node + 2, mid + 1, end)  # update right
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]  # update parent node

    def query(self, l, r, node, start, end):
        """Returns the sum of elements in the range [l, r].

        Args:
            l (int): Left boundary of the query.
            r (int): Right boundary of the query.
            node (int): Current node index (default: 0).
            start (int): Start of the segment (default: 0).
            end (int): End of the segment (default: None, treated as N - 1).

        Returns:
            int: The sum of the elements in the range [l, r].
        """
        # Totally overlapped
        if l <= start and end <= r:
            return self.tree[node]
        
        # Not overlapped
        if end < l or r < start:
            return 0
        
        mid = (start + end) // 2
        return self.query(l, r, 2 * node + 1, start, mid) + self.query(l, r, 2 * node + 2, mid + 1, end)

πŸ’¬ Review & Thoghts

  • How can I use Segment Tree BTW again?
  • Be careful to not to use double loop. Think of the way seperating loops and saving events.
profile
ML Engineer / Autonomous driving

0개의 λŒ“κΈ€