3453. Separate Squares I LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3453. Separate Squares I LeetCode Solution with the best time and space complexity. The solution to Separate Squares I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Separate Squares I solution in C++
Separate Squares I solution in Java
Separate Squares I solution in Python
Additional Resources

3453. Separate Squares I LeetCode Solution image

Problem Statement of Separate Squares I

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:

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:

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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

3453. Separate Squares I LeetCode Solution in C++

class Solution {
 public:
  double separateSquares(vector<vector<int>>& squares) {
    const double halfArea = accumulate(squares.begin(), squares.end(), 0.0,
                                       [](double sum, vector<int>& square) {
      return sum + static_cast<long>(square[2]) * square[2];
    }) / 2;
    vector<tuple<int, bool, int>> events;

    for (const vector<int>& square : squares) {
      const int y = square[1];
      const int l = square[2];
      events.push_back({y, true, l});       // start of square
      events.push_back({y + l, false, l});  // end of square
    }

    ranges::sort(events);

    double area = 0;
    int width = 0;
    int prevY = 0;

    for (const auto& [y, isStart, l] : events) {
      double areaGain = width * static_cast<long>(y - prevY);
      if (area + areaGain >= halfArea)
        return prevY + (halfArea - area) / width;
      area += areaGain;
      width += isStart ? l : -l;
      prevY = y;
    }

    throw;
  }
};
/* code provided by PROGIEZ */

3453. Separate Squares I LeetCode Solution in Java

class Solution {
  public double separateSquares(int[][] squares) {
    final double halfArea =
        Arrays.stream(squares).mapToDouble(square -> Math.pow(square[2], 2)).sum() / 2;
    List<int[]> events = new ArrayList<>();

    for (int[] square : squares) {
      final int y = square[1];
      final int l = square[2];
      events.add(new int[] {y, 1, l});     // start of square
      events.add(new int[] {y + l, 0, l}); // end of square
    }

    events.sort(Comparator.comparingInt(a -> a[0]));

    double area = 0;
    int width = 0;
    int prevY = 0;

    for (int[] event : events) {
      final int y = event[0];
      final int l = event[2];
      final double areaGain = width * (long) (y - prevY);
      if (area + areaGain >= halfArea)
        return prevY + (halfArea - area) / width;
      area += areaGain;
      width += (event[1] == 1) ? l : -l;
      prevY = y;
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

3453. Separate Squares I LeetCode Solution in Python

class Solution:
  def separateSquares(self, squares: list[list[int]]) -> float:
    halfArea = sum((l**2 for _, _, l in squares)) / 2
    events = sorted([(y, True, l) for _, y, l in squares] +
                    [(y + l, False, l) for _, y, l in squares])
    area = 0
    width = 0
    prevY = 0

    for y, isStart, l in events:
      areaGain = width * (y - prevY)
      if area + areaGain >= halfArea:
        return prevY + (halfArea - area) / width
      area += areaGain
      width += l if isStart else -l
      prevY = y
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents