Separate squares i

Array Binary Search

58.0% acceptance

Feb 25, 2026

671

121

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn separate_squares(squares: Vec<Vec<i32>>) -> f64 {
    // Binary search on y. Area below y = sum over each square of area of intersection with [0,y].
    // For square [xi, yi, li]: area below y = li * max(0, min(y, yi+li) - yi) if y > yi, else 0.
    // Total area = sum li^2. Half = total/2.
    let total: f64 = squares.iter().map(|s| (s[2] as f64).powi(2)).sum();
    let half = total / 2.0;
    let area_below = |y: f64| -> f64 {
      squares.iter().map(|s| {
        let yi = s[1] as f64; let li = s[2] as f64;
        let top = yi + li;
        if y <= yi { 0.0 } else { li * (y.min(top) - yi) }
      }).sum::<f64>()
    };
    let mut lo = 0f64;
    let mut hi = 2e9f64;
    for _ in 0..100 {
      let mid = (lo + hi) / 2.0;
      if area_below(mid) < half { lo = mid; } else { hi = mid; }
    }
    lo
  }
}