We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Separate Squares I

Number: 3763

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a collection of axis‐aligned squares defined by their bottom‐left point (x, y) and side length l, find the minimum y-coordinate H for a horizontal line such that the sum of the parts of the squares above the line equals the sum of the parts below the line. Note that if a square is cut by the line, the area on each side is computed, and overlapping areas (if any) are counted multiple times.

Key Insights

  • The area contributed by each square is a function of H which is 0 when H is below the square and equals the full area when H is above the top edge.
  • If the line cuts through a square (i.e. H lies between y and y+l), the area below is (H-y)*l.
  • The total area of all squares is T; the goal is to achieve exactly T/2 area below the line.
  • The function F(H) (total area below the line) is continuous and monotonically non-decreasing, which makes it ideal for using binary search.
  • Calculate F(H) for a given H by iterating over all squares and summing their individual contributions.

Space and Time Complexity

Time Complexity: O(N log R) where N is the number of squares and R is the range of possible y values. Space Complexity: O(1) aside from input storage.

Solution

We first compute the total area T of all squares as the sum of l^2 for each square. The problem reduces to finding the smallest H such that the cumulative below-line area F(H) equals T/2. F(H) is computed for each square: • If H is below a square (H <= y), its contribution is 0. • If H is above a square (H >= y+l), its contribution is l^2. • Otherwise, the square is intersected and its below contribution is (H - y) * l. Binary search is then used over the potential y range (starting from the smallest y among squares to the largest y+l) until the binary search error is within 10^-6.

We use binary search because F(H) is monotonic with respect to H. All provided languages include similar implementations with detailed inline comments that explain every step.

Code Solutions

# Python solution for Separate Squares I
def find_separator_line(squares):
    # Calculate total area of all squares and also determine the valid search range for y
    total_area = 0
    min_y = float('inf')
    max_y = float('-inf')
    
    # Preprocess to calculate total area and search boundaries
    for x, y, l in squares:
        total_area += l * l
        min_y = min(min_y, y)
        max_y = max(max_y, y + l)
    
    target = total_area / 2.0
    
    # Function to compute total below area for a given horizontal line y = H
    def area_below(H):
        area = 0
        for x, y, l in squares:
            # If line H is below this square, contribution is 0.
            if H <= y:
                continue
            # If line H is above the top edge, add full square area.
            elif H >= y + l:
                area += l * l
            # Otherwise, square is partly below
            else:
                area += (H - y) * l
        return area
    
    # Binary search over the y-coordinate range
    low, high = min_y, max_y
    while high - low > 1e-6:
        mid = (low + high) / 2
        if area_below(mid) < target:
            low = mid
        else:
            high = mid
    return low

# Example usage: 
squares1 = [[0,0,1],[2,2,1]]
print(find_separator_line(squares1))  # Expected output: near 1.0

squares2 = [[0,0,2],[1,1,1]]
print(find_separator_line(squares2))  # Expected output: near 1.16667
← Back to All Questions