Separate Squares I - Practice Coding Problems

Separate Squares I - Problem

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 of the squares above the line equals the total area of the squares below the line.

Note: Squares may overlap. Overlapping areas should be counted multiple times. Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Case

$ Input: squares = [[1,1,3],[1,4,3],[3,1,1]]

› Output: 2.5

💡 Note: Square 1: bottom-left (1,1), area 9. Square 2: bottom-left (1,4), area 9. Square 3: bottom-left (3,1), area 1. At y=2.5: above line = 9+9+1=19, below line = 0. This is just an example - actual calculation considers partial intersections.

Example 2 — Single Square

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

› Output: 2.0

💡 Note: One square from (0,0) to (4,4) with area 16. The horizontal line at y=2 divides it exactly in half: 8 area above, 8 area below.

Example 3 — Non-overlapping

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

› Output: 1.0

💡 Note: Two separate squares, each with area 4. Line at y=1 divides each square in half, giving 4 area above and 4 area below.

Constraints

1 ≤ squares.length ≤ 10⁵
squares[i].length == 3
1 ≤ x_i, y_i, l_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Squares

Each square defined by bottom-left point and side length

Find Balance Line

Horizontal line dividing equal areas above and below

Output Y-Coordinate

Return the y-coordinate of the balance line

Key Takeaway

🎯 Key Insight: Use binary search on y-coordinates to efficiently find where total areas above and below the line are equal

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to find a horizontal line that balances total square areas above and below. The binary search approach is optimal, using O(n log(range)) time by efficiently narrowing down the y-coordinate range while calculating areas at each test point.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Y-Coordinates	O(n²)	O(n)	Try all possible y-coordinates and calculate areas above/below for each
Binary Search on Answer	O(n log(max_y))	O(1)	Binary search on the y-coordinate range to find the balance point efficiently

Brute Force - Try All Y-Coordinates — Algorithm Steps

Step 1: Collect all unique y-coordinates from square boundaries
Step 2: For each y-coordinate, calculate total area above and below
Step 3: Find the y where areas are closest to equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Y-Coordinates

Find all square boundaries

Test Each Y

Calculate areas above/below for each y

Find Balance

Select y where areas are most equal

Code -

solution.c — C

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

typedef struct {
    double areaAbove;
    double areaBelow;
} Areas;

Areas calculateAreas(int squares[][3], int n, double lineY) {
    Areas areas = {0.0, 0.0};
    
    for (int i = 0; i < n; i++) {
        int x = squares[i][0], y = squares[i][1], l = squares[i][2];
        double squareBottom = y;
        double squareTop = y + l;
        
        if (lineY <= squareBottom) {
            // Entire square above line
            areas.areaAbove += l * l;
        } else if (lineY >= squareTop) {
            // Entire square below line
            areas.areaBelow += l * l;
        } else {
            // Square intersected by line
            double heightBelow = lineY - squareBottom;
            double heightAbove = squareTop - lineY;
            areas.areaBelow += l * heightBelow;
            areas.areaAbove += l * heightAbove;
        }
    }
    
    return areas;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

double solution(int squares[][3], int n) {
    if (n == 0) {
        return 0.0;
    }
    
    // Collect all unique y-coordinates
    int yCoords[2000]; // Assuming reasonable input size
    int yCount = 0;
    
    for (int i = 0; i < n; i++) {
        int x = squares[i][0], y = squares[i][1], l = squares[i][2];
        
        // Add bottom coordinate if not exists
        int found = 0;
        for (int j = 0; j < yCount; j++) {
            if (yCoords[j] == y) {
                found = 1;
                break;
            }
        }
        if (!found) yCoords[yCount++] = y;
        
        // Add top coordinate if not exists
        found = 0;
        for (int j = 0; j < yCount; j++) {
            if (yCoords[j] == y + l) {
                found = 1;
                break;
            }
        }
        if (!found) yCoords[yCount++] = y + l;
    }
    
    qsort(yCoords, yCount, sizeof(int), compare);
    
    double bestY = yCoords[0];
    double minDiff = 1e9;
    
    for (int i = 0; i < yCount; i++) {
        Areas areas = calculateAreas(squares, n, yCoords[i]);
        double diff = fabs(areas.areaAbove - areas.areaBelow);
        if (diff < minDiff) {
            minDiff = diff;
            bestY = yCoords[i];
        }
    }
    
    // Try intermediate points for better precision
    for (int i = 0; i < yCount - 1; i++) {
        double midY = (yCoords[i] + yCoords[i + 1]) / 2.0;
        Areas areas = calculateAreas(squares, n, midY);
        double diff = fabs(areas.areaAbove - areas.areaBelow);
        if (diff < minDiff) {
            minDiff = diff;
            bestY = midY;
        }
    }
    
    return bestY;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x,y,l],[x,y,l],...]
    int squares[1000][3];
    int n = 0;
    
    char* ptr = line + 2; // Skip "[["
    while (*ptr && n < 1000) {
        sscanf(ptr, "%d,%d,%d", &squares[n][0], &squares[n][1], &squares[n][2]);
        n++;
        
        // Move to next square
        while (*ptr && *ptr != '[') ptr++;
        if (*ptr) ptr++; // Skip '['
    }
    
    double result = solution(squares, n);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n boundary points, we check all n squares

⚠ Quadratic Growth

Space Complexity

O(n)

Store unique y-coordinates from square boundaries

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 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 - Try All Y-Coordinates — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler