Skip to content

391. Perfect Rectangle 👍

  • Time: $O(n)$
  • 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
35
36
37
class Solution {
 public:
  bool isRectangleCover(vector<vector<int>>& rectangles) {
    int area = 0;
    int x1 = INT_MAX;
    int y1 = INT_MAX;
    int x2 = INT_MIN;
    int y2 = INT_MIN;
    unordered_set<string> corners;

    for (const vector<int>& r : rectangles) {
      area += (r[2] - r[0]) * (r[3] - r[1]);
      x1 = min(x1, r[0]);
      y1 = min(y1, r[1]);
      x2 = max(x2, r[2]);
      y2 = max(y2, r[3]);

      // the four points of the current rectangle
      const vector<string> points{to_string(r[0]) + " " + to_string(r[1]),
                                  to_string(r[0]) + " " + to_string(r[3]),
                                  to_string(r[2]) + " " + to_string(r[1]),
                                  to_string(r[2]) + " " + to_string(r[3])};
      for (const string& point : points)
        if (!corners.insert(point).second)
          corners.erase(point);
    }

    if (corners.size() != 4)
      return false;
    if (!corners.contains(to_string(x1) + " " + to_string(y1)) ||
        !corners.contains(to_string(x1) + " " + to_string(y2)) ||
        !corners.contains(to_string(x2) + " " + to_string(y1)) ||
        !corners.contains(to_string(x2) + " " + to_string(y2)))
      return false;
    return area == (x2 - x1) * (y2 - y1);
  }
};

 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
35
36
class Solution {
  public boolean isRectangleCover(int[][] rectangles) {
    int area = 0;
    int x1 = Integer.MAX_VALUE;
    int y1 = Integer.MAX_VALUE;
    int x2 = Integer.MIN_VALUE;
    int y2 = Integer.MIN_VALUE;
    Set<String> corners = new HashSet<>();

    for (int[] r : rectangles) {
      area += (r[2] - r[0]) * (r[3] - r[1]);
      x1 = Math.min(x1, r[0]);
      y1 = Math.min(y1, r[1]);
      x2 = Math.max(x2, r[2]);
      y2 = Math.max(y2, r[3]);

      // the four points of the current rectangle
      String[] points = new String[] {r[0] + " " + r[1], //
                                      r[0] + " " + r[3], //
                                      r[2] + " " + r[1], //
                                      r[2] + " " + r[3]};
      for (final String point : points)
        if (!corners.add(point))
          corners.remove(point);
    }

    if (corners.size() != 4)
      return false;
    if (!corners.contains(x1 + " " + y1) || //
        !corners.contains(x1 + " " + y2) || //
        !corners.contains(x2 + " " + y1) || //
        !corners.contains(x2 + " " + y2))
      return false;
    return area == (x2 - x1) * (y2 - y1);
  }
}

 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
class Solution:
  def isRectangleCover(self, rectangles: list[list[int]]) -> bool:
    area = 0
    x1 = math.inf
    y1 = math.inf
    x2 = -math.inf
    y2 = -math.inf
    corners: set[tuple[int, int]] = set()

    for x, y, a, b in rectangles:
      area += (a - x) * (b - y)
      x1 = min(x1, x)
      y1 = min(y1, y)
      x2 = max(x2, a)
      y2 = max(y2, b)

      # the four points of the current rectangle
      for point in [(x, y), (x, b), (a, y), (a, b)]:
        if point in corners:
          corners.remove(point)
        else:
          corners.add(point)

    if len(corners) != 4:
      return False
    if ((x1, y1) not in corners or
        (x1, y2) not in corners or
        (x2, y1) not in corners or
            (x2, y2) not in corners):
      return False
    return area == (x2 - x1) * (y2 - y1)