Find horizontal cut balancing square areas
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a 2D table with top-left origin (0,
0), you are provided a finite set of n non-overlapping, axis-aligned square cakes. Each square i has real-valued top-left coordinates (x_i, y_i) and an integer side length s_i ≥ 1. Design an algorithm to find a horizontal cut y* (parallel to the x-axis) such that the total cake area strictly above the line equals the total area strictly below it. Specify the search interval, prove a solution exists, and argue monotonicity needed for your approach. Provide the time and space complexity in terms of n and precision ε, and discuss numerical stability and stopping criteria when coordinates are floats. If multiple y* exist, explain how you would return one. Finally, discuss how your method would change if
(a) squares could overlap, or
(b) shapes were axis-aligned rectangles instead of squares.
Quick Answer: This question evaluates computational geometry and algorithm design skills, focusing on area computation, monotonicity reasoning, existence proofs, root-finding under floating-point constraints, and considerations of numerical stability and complexity.
Part 1: Balanced Horizontal Cut in Non-Overlapping Squares
You are given n axis-aligned squares on a 2D plane with a top-left origin, so y increases downward. Each square is represented as [x, y, s], where (x, y) is the top-left corner and s is the side length. The squares do not overlap in area, though they may touch at edges. Find the smallest horizontal cut y* such that the total square area strictly above the line y = y* equals the total square area strictly below it. Because the line itself has zero area, points exactly on the line do not matter. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(squares) <= 200000
- Each square is [x, y, s] with x and y real-valued and s an integer
- 1 <= s <= 10^6
- Squares do not overlap in interior area
- 0 < eps <= 1e-3
Examples
Input: ([[0, 0, 2]],)
Expected Output: 1.0
Explanation: A 2x2 square has total area 4, so each side must contain area 2. The cut is halfway down the square at y = 1.0.
Input: ([[0, 0, 2], [3, 4, 2]],)
Expected Output: 2.0
Explanation: The first square contributes area 4 above y = 2, and the second square starts at y = 4. Any cut in [2, 4] balances the areas, so the smallest valid cut is 2.0.
Input: ([[0, 0, 1], [2, 0, 1], [0, 2, 2]],)
Expected Output: 2.5
Explanation: The two 1x1 squares contribute area 2 above y = 2. The total area is 6, so we need area 3 above the cut. That requires 1 more unit from the 2x2 square, which happens after going 0.5 units into it: y = 2.5.
Input: ([[5, -5, 5]],)
Expected Output: -2.5
Explanation: The square spans from y = -5 to y = 0. Its midpoint is y = -2.5, which splits its area equally.
Input: ([[0, 0, 2], [3, 0, 1]],)
Expected Output: 0.83333
Explanation: The total area is 5, so the target above-area is 2.5. From y = 0 to y = 1, the combined active width is 3, so the cut is at 2.5 / 3 = 0.83333 after rounding.
Solution
def solution(squares):
if isinstance(squares, tuple) and len(squares) == 1 and isinstance(squares[0], (list, tuple)):
squares = squares[0]
if isinstance(squares, (list, tuple)) and len(squares) == 3 and not isinstance(squares[0], (list, tuple)):
squares = [squares]
squares = list(squares)
if not squares:
return 0.0
events = {}
total_area = 0.0
for square in squares:
if len(square) != 3:
raise ValueError('Each square must be [x, y, s].')
_, y, s = square
top = float(y)
side = float(s)
bottom = top + side
events[top] = events.get(top, 0.0) + side
events[bottom] = events.get(bottom, 0.0) - side
total_area += side * side
target = total_area / 2.0
eps = 1e-12
sorted_events = sorted(events.items())
area_above = 0.0
active_width = 0.0
prev_y = sorted_events[0][0]
for y, delta in sorted_events:
if y > prev_y:
if abs(area_above - target) <= eps:
return round(prev_y, 5)
next_area = area_above + active_width * (y - prev_y)
if target <= next_area + eps:
if active_width == 0:
return round(prev_y, 5)
answer = prev_y + (target - area_above) / active_width
return round(answer, 5)
area_above = next_area
active_width += delta
prev_y = y
return round(prev_y, 5)
Time complexity: O(n log n). Space complexity: O(n).
Hints
- Let F(y) be the total area of all squares above the cut. What shape does F(y) have as y moves downward?
- A valid search interval is from the smallest square top to the largest square bottom.
Part 2: Balanced Horizontal Cut in Overlapping Squares Using Union Area
You are given n axis-aligned squares on a 2D plane with a top-left origin, so y increases downward. Each square is represented as [x, y, s]. Unlike Part 1, squares may overlap. The cake area is the area of the union of all squares, so overlapping regions count only once. Find the smallest horizontal cut y* such that the union area strictly above the line y = y* equals the union area strictly below it. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(squares) <= 20000
- Each square is [x, y, s] with x and y real-valued and s an integer
- 1 <= s <= 10^6
- Squares may overlap arbitrarily
- Coordinates have absolute value at most 10^9
Solution
def solution(squares):
if not squares:
return 0.0
xs = sorted({x for x, _, s in squares for x in (x, x + s)})
m = len(xs) - 1
if m <= 0:
return 0.0
x_to_i = {x: i for i, x in enumerate(xs)}
events = []
for x, y, s in squares:
l = x_to_i[x]
r = x_to_i[x + s]
events.append((y, 1, l, r))
events.append((y + s, -1, l, r))
events.sort()
count = [0] * (4 * m + 5)
covered = [0.0] * (4 * m + 5)
def pull(node, left, right):
if count[node] > 0:
covered[node] = xs[right] - xs[left]
elif left + 1 == right:
covered[node] = 0.0
else:
covered[node] = covered[node * 2] + covered[node * 2 + 1]
def update(node, left, right, ql, qr, delta):
if ql >= right or qr <= left:
return
if ql <= left and right <= qr:
count[node] += delta
pull(node, left, right)
return
mid = (left + right) // 2
update(node * 2, left, mid, ql, qr, delta)
update(node * 2 + 1, mid, right, ql, qr, delta)
pull(node, left, right)
strips = []
total_area = 0.0
prev_y = events[0][0]
i = 0
n_events = len(events)
while i < n_events:
y = events[i][0]
current_width = covered[1]
if y > prev_y:
dy = y - prev_y
strips.append((prev_y, y, current_width))
total_area += current_width * dy
while i < n_events and events[i][0] == y:
_, delta, l, r = events[i]
update(1, 0, m, l, r, delta)
i += 1
prev_y = y
half = total_area / 2.0
acc = 0.0
eps = 1e-12
for y0, y1, width in strips:
if abs(acc - half) <= eps:
return round(y0, 5)
area = width * (y1 - y0)
if width > 0 and acc + area >= half - eps:
return round(y0 + (half - acc) / width, 5)
acc += area
return round(prev_y, 5)
Time complexity: O(n log n). Space complexity: O(n).
Hints
- Sweep along y. Between two consecutive top/bottom edges, the set of active squares does not change, so the covered x-length is constant.
- To get union width quickly for active x-intervals, coordinate compression plus a segment tree is a standard approach.
Part 3: Balanced Horizontal Cut in Non-Overlapping Rectangles
You are given n axis-aligned rectangles on a 2D plane with a top-left origin, so y increases downward. Each rectangle is represented as [x, y, w, h], where (x, y) is the top-left corner, w is width, and h is height. Rectangles do not overlap in area, though they may touch at edges. Find the smallest horizontal cut y* such that the total rectangle area strictly above the line y = y* equals the total rectangle area strictly below it. Return y* rounded to 5 decimal places.
Constraints
- 1 <= len(rectangles) <= 200000
- Each rectangle is [x, y, w, h] with x and y real-valued
- w > 0 and h > 0
- Rectangles do not overlap in interior area
- Coordinates have absolute value at most 10^9
Solution
def solution(rectangles):
if not rectangles:
return 0.0
events = []
total_area = 0.0
for _, y, w, h in rectangles:
events.append((y, w))
events.append((y + h, -w))
total_area += w * h
events.sort()
strips = []
active_width = 0.0
prev_y = events[0][0]
i = 0
n_events = len(events)
while i < n_events:
y = events[i][0]
if y > prev_y:
strips.append((prev_y, y, active_width))
while i < n_events and events[i][0] == y:
active_width += events[i][1]
i += 1
prev_y = y
half = total_area / 2.0
acc = 0.0
eps = 1e-12
for y0, y1, width in strips:
if abs(acc - half) <= eps:
return round(y0, 5)
area = width * (y1 - y0)
if width > 0 and acc + area >= half - eps:
return round(y0 + (half - acc) / width, 5)
acc += area
return round(prev_y, 5)
Time complexity: O(n log n). Space complexity: O(n).
Hints
- Between consecutive rectangle top/bottom edges, the area gained per unit of y is constant.
- In each horizontal strip, that rate is the sum of widths of all rectangles crossing the strip.