Separate Squares I
Source: leetcode
Difficulty: Medium
Tags: array, binary-search

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.


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


**Note**: Squares **may** overlap. Overlapping areas should be counted **multiple times**.


 


**Example 1:**



**Input:** squares \= \[\[0,0,1],\[2,2,1]]


**Output:** 1\.00000


**Explanation:**


![](https://assets.leetcode.com/uploads/2025/01/06/4062example1drawio.png)


Any horizontal line between `y = 1` and `y = 2` will have 1 square unit above it and 1 square unit below it. The lowest option is 1\.



**Example 2:**



**Input:** squares \= \[\[0,0,2],\[1,1,1]]


**Output:** 1\.16667


**Explanation:**


![](https://assets.leetcode.com/uploads/2025/01/15/4062example2drawio.png)


The areas are:


- Below the line: `7/6 * 2 (Red) + 1/6 (Blue) = 15/6 = 2.5`.
- Above the line: `5/6 * 2 (Red) + 5/6 (Blue) = 15/6 = 2.5`.


Since the areas above and below the line are equal, the output is `7/6 = 1.16667`.



 


**Constraints:**


- `1 <= squares.length <= 5 * 104`
- `squares[i] = [xi, yi, li]`
- `squares[i].length == 3`
- `0 <= xi, yi <= 109`
- `1 <= li <= 109`
- The total area of all the squares will not exceed `1012`.




C++ solution:
class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        long long total_area = 0;
        double max_y_high = 0.0;
        for (auto& sq : squares) {
            int yi = sq[1];
            int li = sq[2];
            total_area += static_cast<long long>(li) * li;
            max_y_high = std::max(max_y_high, static_cast<double>(yi + li));
        }
        double half_total = total_area / 2.0;
        double low = 0.0, high = max_y_high;
        for (int iter = 0; iter < 100; ++iter) {
            double mid = (low + high) / 2;
            double sum_above = 0.0;
            for (auto& sq : squares) {
                int yi = sq[1];
                int li = sq[2];
                double y_top = yi + li;
                if (mid <= yi) {
                    sum_above += static_cast<double>(li) * li;
                } else if (mid < y_top) {
                    sum_above += static_cast<double>(li) * (y_top - mid);
                }
            }
            if (sum_above > half_total) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    }
};

Go solution:
func separateSquares(squares [][]int) float64 {
	criticals := make([]float64, 0, 2*len(squares))
	for _, sq := range squares {
		yi := float64(sq[1])
		li := float64(sq[2])
		criticals = append(criticals, yi, yi+li)
	}
	sort.Float64s(criticals)
	j := 0
	for i := 1; i < len(criticals); i++ {
		if criticals[i] != criticals[j] {
			j++
			criticals[j] = criticals[i]
		}
	}
	criticals = criticals[:j+1]

	var maxY float64
	for _, sq := range squares {
		if y := float64(sq[1] + sq[2]); y > maxY {
			maxY = y
		}
	}

	low, high := 0.0, maxY
	epsilon := 1e-7
	for i := 0; i < 100; i++ {
		mid := (low + high) / 2
		diff := computeDiff(mid, squares)
		if diff > 0 {
			low = mid
		} else {
			high = mid
		}
	}
	candidate := low

	idx := sort.Search(len(criticals), func(i int) bool { return criticals[i] > candidate }) - 1
	if idx >= 0 {
		y := criticals[idx]
		if math.Abs(computeDiff(y, squares)) < epsilon {
			return y
		}
	}
	return candidate
}

func computeDiff(y float64, squares [][]int) float64 {
	var above, below float64
	for _, sq := range squares {
		yi := float64(sq[1])
		li := float64(sq[2])
		top := yi + li
		if y <= yi {
			above += li * li
		} else if y >= top {
			below += li * li
		} else {
			above += (top - y) * li
			below += (y - yi) * li
		}
	}
	return above - below
}

Java solution:
class Solution {
    public double separateSquares(int[][] squares) {
        double totalArea = 0.0;
        long maxYPlusLi = 0;
        for (int[] square : squares) {
            long yi = square[1];
            long li = square[2];
            totalArea += (double) li * li;
            long top = yi + li;
            if (top > maxYPlusLi) {
                maxYPlusLi = top;
            }
        }
        double target = totalArea / 2.0;
        double low = 0.0;
        double high = maxYPlusLi;
        for (int iter = 0; iter < 100; iter++) {
            double mid = (low + high) * 0.5;
            double sumAbove = 0.0;
            for (int[] square : squares) {
                long yi = square[1];
                long li = square[2];
                long top = yi + li;
                if (mid <= yi) {
                    sumAbove += (double) li * li;
                } else if (mid < top) {
                    sumAbove += (top - mid) * li;
                }
            }
            if (sumAbove > target) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

JavaScript solution:
var separateSquares = function(squares) {
    let total_area = squares.reduce((sum, [x, y, l]) => sum + l * l, 0);
    const target = total_area / 2;
    const events = [];
    for (const [x, yi, li] of squares) {
        const end = yi + li;
        events.push({ y: yi, type: 'start', li, yi });
        events.push({ y: end, type: 'end', li, yi });
    }
    events.sort((a, b) => {
        if (a.y !== b.y) return a.y - b.y;
        return a.type === 'end' ? -1 : 1;
    });
    let sum_full = 0, active_li = 0, active_yili = 0, prev_y = -Infinity;
    for (const event of events) {
        const curr_y = event.y;
        if (prev_y < curr_y) {
            const sum_prev = sum_full + active_li * prev_y - active_yili;
            const sum_curr = sum_full + active_li * curr_y - active_yili;
            if (sum_prev <= target && target <= sum_curr) {
                if (active_li === 0) {
                    if (sum_prev === target) return prev_y;
                } else {
                    const k = (target + active_yili - sum_full) / active_li;
                    if (k >= prev_y && k <= curr_y) return Math.max(prev_y, k);
                }
            }
        }
        if (event.type === 'start') {
            active_li += event.li;
            active_yili += event.yi * event.li;
        } else {
            active_li -= event.li;
            active_yili -= event.yi * event.li;
            sum_full += event.li * event.li;
        }
        prev_y = curr_y;
    }
    return prev_y;
};

Python solution:
class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        total_area = 0
        min_y = float('inf')
        max_y = -float('inf')
        for x, y, l in squares:
            total_area += l * l
            min_y = min(min_y, y)
            current_max = y + l
            max_y = max(max_y, current_max)
        
        target = total_area / 2
        
        low = min_y
        high = max_y
        
        # Perform binary search with sufficient iterations for precision
        for _ in range(100):
            mid = (low + high) / 2
            current_sum = 0.0
            for x, y, l in squares:
                if mid <= y:
                    contrib = 0.0
                elif mid >= y + l:
                    contrib = l * l
                else:
                    contrib = (mid - y) * l
                current_sum += contrib
            if current_sum < target:
                low = mid
            else:
                high = mid
        
        return (low + high) / 2

Ruby solution:
def separate_squares(squares)
  total_area = squares.sum { |x, y, l| l.to_f * l }
  target = total_area / 2.0

  events = []
  squares.each do |x, y_i, l|
    start_y = y_i.to_f
    end_y = (y_i + l).to_f
    events << [start_y, l.to_f]
    events << [end_y, -l.to_f]
  end

  events.sort!

  previous_y = 0.0
  current_area = 0.0
  active_sum = 0.0

  events.each do |current_y, delta|
    delta_y = current_y - previous_y
    area_in_interval = active_sum * delta_y

    if current_area + area_in_interval >= target - 1e-12
      if active_sum.zero?
        return previous_y
      else
        required = target - current_area
        y = previous_y + required / active_sum
        return y
      end
    end

    current_area += area_in_interval
    active_sum += delta
    previous_y = current_y
  end

  previous_y
end