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
38
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]);

      // Four points of 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.count(to_string(x1) + " " + to_string(y1)) ||
        !corners.count(to_string(x1) + " " + to_string(y2)) ||
        !corners.count(to_string(x2) + " " + to_string(y1)) ||
        !corners.count(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
37
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]);

      // Four points of 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);
  }
}