Skip to content

3453. Separate Squares I 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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(event -> event[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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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