3454. Separate Squares II LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3454. Separate Squares II LeetCode Solution with the best time and space complexity. The solution to Separate Squares II 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 II solution in C++
Separate Squares II solution in Java
Separate Squares II solution in Python
Additional Resources

3454. Separate Squares II LeetCode Solution image

Problem Statement of Separate Squares II

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 covered by squares above the line equals the total area covered by squares below the line.
Answers within 10-5 of the actual answer will be accepted.
Note: Squares may overlap. Overlapping areas should be counted only once in this version.

Example 1:

Input: squares = [[0,0,1],[2,2,1]]
Output: 1.00000
Explanation:

Any horizontal line between y = 1 and y = 2 results in an equal split, with 1 square unit above and 1 square unit below. The minimum y-value is 1.

Example 2:

Input: squares = [[0,0,2],[1,1,1]]
Output: 1.00000
Explanation:

Since the blue square overlaps with the red square, it will not be counted again. Thus, the line y = 1 splits the squares into two equal parts.

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 1015.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

3454. Separate Squares II LeetCode Solution in C++

class SegmentTree {
 public:
  explicit SegmentTree(const vector<int>& xs)
      : xs(xs), n(xs.size() - 1), coveredCount(4 * n), coveredWidth(4 * n) {}

  // Adds val to the range [i, j].
  void add(int i, int j, int val) {
    add(0, 0, n - 1, i, j, val);
  }

  // Returns the covered width of xs[0..n - 1].
  int getCoveredWidth() const {
    return coveredWidth[0];
  }

 private:
  const int n;  // the number of segments (|xs| - 1)
  vector<int> xs;
  vector<int> coveredCount;
  vector<int> coveredWidth;

  void add(int treeIndex, int lo, int hi, int i, int j, int val) {
    if (j <= xs[lo] || xs[hi + 1] <= i)
      return;
    if (i <= xs[lo] && xs[hi + 1] <= j) {
      coveredCount[treeIndex] += val;
    } else {
      const int mid = (lo + hi) / 2;
      add(2 * treeIndex + 1, lo, mid, i, j, val);
      add(2 * treeIndex + 2, mid + 1, hi, i, j, val);
    }
    if (coveredCount[treeIndex] > 0) {
      coveredWidth[treeIndex] = xs[hi + 1] - xs[lo];
    } else if (lo == hi) {
      coveredWidth[treeIndex] = 0;
    } else {
      coveredWidth[treeIndex] =
          coveredWidth[2 * treeIndex + 1] + coveredWidth[2 * treeIndex + 2];
    }
  }
};

class Solution {
 public:
  double separateSquares(vector<vector<int>>& squares) {
    vector<tuple<int, int, int, int>> events;  // (y, delta, xl, xr)
    set<int> xs;

    for (const vector<int>& square : squares) {
      const int x = square[0];
      const int y = square[1];
      const int l = square[2];
      events.emplace_back(y, 1, x, x + l);
      events.emplace_back(y + l, -1, x, x + l);
      xs.insert(x);
      xs.insert(x + l);
    }

    ranges::sort(events);

    const double halfArea = getArea(events, xs) / 2.0;
    long area = 0;
    int prevY = 0;
    SegmentTree tree({xs.begin(), xs.end()});

    for (const auto& [y, delta, xl, xr] : events) {
      const int coveredWidth = tree.getCoveredWidth();
      const long areaGain = coveredWidth * static_cast<long>(y - prevY);
      if (area + areaGain >= halfArea)
        return prevY + (halfArea - area) / coveredWidth;
      area += areaGain;
      tree.add(xl, xr, delta);
      prevY = y;
    }

    throw;
  }

 private:
  // Returns the total area of the rectangles.
  long getArea(const vector<tuple<int, int, int, int>>& events,
               const set<int>& xs) {
    long totalArea = 0;
    int prevY = 0;
    SegmentTree tree({xs.begin(), xs.end()});
    for (const auto& [y, delta, xl, xr] : events) {
      totalArea += tree.getCoveredWidth() * static_cast<long>(y - prevY);
      tree.add(xl, xr, delta);
      prevY = y;
    }
    return totalArea;
  }
};
/* code provided by PROGIEZ */

3454. Separate Squares II LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3454. Separate Squares II LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

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

Table of Contents