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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Separate Squares II

Difficulty: Hard

Problem Description

You are given a 2D integer array squares. Each squares[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 the minimum y-coordinate value of a horizontal line such that the total area covered by squares above the line equals the total area covered by squares below the line. Answers within 10^-5 of the actual answer will be accepted. Note: Squares may overlap. Overlapping areas should be counted only once.

Key Insights

  • The total area of all squares can be calculated by summing the areas of individual squares.
  • To find the correct horizontal line, a binary search can be performed over possible y-coordinates.
  • A sweep line approach can be used to calculate the area covered by squares above and below the current line.
  • The solution requires an efficient method to compute the area while handling overlapping squares.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting and binary search operations. Space Complexity: O(n) - for storing active segments during the sweep line process.

Solution

To solve the problem, we will:

  1. Calculate the total area of all squares.
  2. Use binary search to find the minimum y-coordinate where the areas above and below are equal.
  3. Implement a sweep line algorithm to efficiently compute the area covered by the squares at each potential y-coordinate. This involves keeping track of active segments and their contributions to the area.

Code Solutions

def separate_squares(squares):
    events = []
    total_area = 0
    
    for x, y, l in squares:
        total_area += l * l
        events.append((y, x, x + l, 1))    # Start of square
        events.append((y + l, x, x + l, -1))  # End of square

    events.sort()
    
    def calculate_area(y_line):
        active_intervals = []
        last_x = -1
        area = 0
        
        for event in events:
            current_y, x1, x2, type = event
            
            if current_y > y_line:
                break
            
            if type == 1:
                active_intervals.append((x1, x2))
            else:
                active_intervals.remove((x1, x2))
                
            # Calculate area covered by active intervals
            current_x = 0
            for x_start, x_end in sorted(active_intervals):
                if x_start > current_x:
                    area += current_x - last_x
                    current_x = x_start
                current_x = max(current_x, x_end)
                last_x = current_x
                
            area += current_x - last_x
            
        return area

    low, high = 0, max(y + l for x, y, l in squares)
    while low < high:
        mid = (low + high) / 2
        area_above = calculate_area(mid)
        if area_above == total_area / 2:
            return mid
        elif area_above < total_area / 2:
            low = mid + 1e-5
        else:
            high = mid
            
    return low
← Back to All Questions