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.
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.
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.
β± Runtime: 424 ms
π§ Memory: 52.3 MB
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]]
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
# sort list with lambda
squares.sort(key = lambda x :x[1]) # sort with y
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 treen-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)