Separate Squares II - Practice Coding Problems

Separate Squares II - Problem

You are given a 2D integer array squares where each squares[i] = [x_i, y_i, l_i] 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.

Note: Squares may overlap. Overlapping areas should be counted only once in this version.

Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Two Non-Overlapping Squares

$ Input: squares = [[0,0,4],[0,6,2]]

› Output: 4.0

💡 Note: Square 1: (0,0) to (4,4) with area 16. Square 2: (0,6) to (2,8) with area 4. Line at y=4 divides: below has area 16, above has area 4. Not balanced. Line at y=5 gives areas 16 and 4. Line at y=4 actually works when calculated correctly.

Example 2 — Single Square

$ Input: squares = [[1,1,6]]

› Output: 4.0

💡 Note: One square from (1,1) to (7,7) with area 36. The horizontal line at y=4 splits it into two parts: below (1,1)-(7,4) has area 18, above (1,4)-(7,7) has area 18. Perfect balance.

Example 3 — Overlapping Squares

$ Input: squares = [[0,0,4],[2,2,4]]

› Output: 3.0

💡 Note: Two overlapping squares. Total area when merged is less than sum due to overlap. Line at y=3 balances the areas above and below after accounting for overlaps.

Constraints

1 ≤ squares.length ≤ 10⁵
-10⁵ ≤ x_i, y_i ≤ 10⁵
1 ≤ l_i ≤ 10⁵

Visualization

Tap to expand

[0,0,4]Square 2
[2,6,3]Square 3
[4,1,5]Area Below LineArea Above LineFind y where: Area_Above = Area_BelowAccount for overlapping squares (count overlap area only once)Output: Minimum y-coordinate that achieves balance

Understanding the Visualization

Input Squares

2D array with [x, y, length] for each square

Find Balance Line

Horizontal line where area_above = area_below

Handle Overlaps

Merge overlapping regions correctly

Key Takeaway

🎯 Key Insight: The optimal y-coordinate must occur at a square boundary - test only critical points for efficiency

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is that the optimal y-coordinate must be at a square boundary. Use binary search on answer space or test all critical y-coordinates. Best approach is binary search with ternary search optimization. Time: O(n² log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Area Calculation	O(n³)	O(n)	Try all possible y-coordinates and calculate areas above/below for each
Binary Search on Answer Space	O(n² log n)	O(n)	Binary search on y-coordinate range to find the balance point

Brute Force with Area Calculation — Algorithm Steps

Collect all unique y-coordinates from square boundaries
For each y-coordinate, split squares into above/below regions
Calculate area in each region by merging overlapping rectangles
Find y where areas are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Y-Coordinates

Find all square boundaries

Test Each Line

Split squares and calculate areas

Find Balance

Return y where areas are equal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int compareRects(const void* a, const void* b) {
    int* rectA = (int*)a;
    int* rectB = (int*)b;
    return rectA[0] - rectB[0];
}

double calculateArea(int rectangles[][4], int count) {
    if (count == 0) return 0;
    
    qsort(rectangles, count, sizeof(int[4]), compareRects);
    
    int merged[1000][4];
    int mergedCount = 0;
    
    for (int i = 0; i < count; i++) {
        if (mergedCount == 0) {
            for (int j = 0; j < 4; j++) {
                merged[mergedCount][j] = rectangles[i][j];
            }
            mergedCount++;
        } else {
            int* last = merged[mergedCount - 1];
            if (rectangles[i][0] <= last[2] && rectangles[i][1] <= last[3] &&
                rectangles[i][2] >= last[0] && rectangles[i][3] >= last[1]) {
                last[0] = (last[0] < rectangles[i][0]) ? last[0] : rectangles[i][0];
                last[1] = (last[1] < rectangles[i][1]) ? last[1] : rectangles[i][1];
                last[2] = (last[2] > rectangles[i][2]) ? last[2] : rectangles[i][2];
                last[3] = (last[3] > rectangles[i][3]) ? last[3] : rectangles[i][3];
            } else {
                for (int j = 0; j < 4; j++) {
                    merged[mergedCount][j] = rectangles[i][j];
                }
                mergedCount++;
            }
        }
    }
    
    double totalArea = 0;
    for (int i = 0; i < mergedCount; i++) {
        totalArea += (merged[i][2] - merged[i][0]) * (merged[i][3] - merged[i][1]);
    }
    
    return totalArea;
}

double solution(int squares[][3], int n) {
    if (n == 0) return 0.0;
    
    int yCoords[2000];
    int yCount = 0;
    
    for (int i = 0; i < n; i++) {
        yCoords[yCount++] = squares[i][1];
        yCoords[yCount++] = squares[i][1] + squares[i][2];
    }
    
    // Remove duplicates and sort
    for (int i = 0; i < yCount - 1; i++) {
        for (int j = i + 1; j < yCount; j++) {
            if (yCoords[i] > yCoords[j]) {
                int temp = yCoords[i];
                yCoords[i] = yCoords[j];
                yCoords[j] = temp;
            }
        }
    }
    
    int uniqueY = 0;
    for (int i = 0; i < yCount; i++) {
        if (i == 0 || yCoords[i] != yCoords[i-1]) {
            yCoords[uniqueY++] = yCoords[i];
        }
    }
    
    for (int i = 0; i < uniqueY; i++) {
        int yLine = yCoords[i];
        int aboveRects[1000][4], belowRects[1000][4];
        int aboveCount = 0, belowCount = 0;
        
        for (int j = 0; j < n; j++) {
            int x = squares[j][0], y = squares[j][1], l = squares[j][2];
            int x1 = x, y1 = y, x2 = x + l, y2 = y + l;
            
            if (y2 <= yLine) {
                belowRects[belowCount][0] = x1;
                belowRects[belowCount][1] = y1;
                belowRects[belowCount][2] = x2;
                belowRects[belowCount][3] = y2;
                belowCount++;
            } else if (y1 >= yLine) {
                aboveRects[aboveCount][0] = x1;
                aboveRects[aboveCount][1] = y1;
                aboveRects[aboveCount][2] = x2;
                aboveRects[aboveCount][3] = y2;
                aboveCount++;
            } else {
                belowRects[belowCount][0] = x1;
                belowRects[belowCount][1] = y1;
                belowRects[belowCount][2] = x2;
                belowRects[belowCount][3] = yLine;
                belowCount++;
                
                aboveRects[aboveCount][0] = x1;
                aboveRects[aboveCount][1] = yLine;
                aboveRects[aboveCount][2] = x2;
                aboveRects[aboveCount][3] = y2;
                aboveCount++;
            }
        }
        
        double areaAbove = calculateArea(aboveRects, aboveCount);
        double areaBelow = calculateArea(belowRects, belowCount);
        
        if (fabs(areaAbove - areaBelow) < 1e-9) {
            return yLine;
        }
    }
    
    return 0.0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int squares[1000][3];
    int n = 0;
    
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            squares[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            squares[n][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            squares[n][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    double result = solution(squares, n);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n) y-coordinates × O(n²) area calculation per coordinate

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for split rectangles and merged areas

⚡ Linearithmic Space

12.8K Views

Medium Frequency

~45 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Area Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler