How to Determine if a Rectangle is Perfect

Today we will discuss a very interesting and challenging problem.

We know a rectangle has four vertices, but it can be defined by just two vertices' coordinates (for example, the bottom-left and top-right vertices).

Let's look at LeetCode Problem 391 "Perfect Rectangle". The problem provides an array rectangles, which contains several tuples (x1, y1, x2, y2), each representing the coordinates of the bottom-left and top-right corners of a rectangle.

391. Perfect Rectangle | LeetCode |  🔴

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

Example 1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.

Constraints:

• 1 <= rectangles.length <= 2 * 104
• rectangles[i].length == 4
• -105 <= xi, yi, ai, bi <= 105

In other words, the input rectangles array consists of many small rectangles, and the task is to output a boolean value to determine if these small rectangles can form a "perfect rectangle". The function signature is as follows:

boolean isRectangleCover(int[][] rectangles)

bool isRectangleCover(vector<vector<int>>& rectangles)

def isRectangleCover(rectangles: List[List[int]]) -> bool

func isRectangleCover(rectangles [][]int) bool {}

function isRectangleCover(rectangles) {}

The so-called "perfect rectangle" refers to the fact that the small rectangles in rectangles must form a large rectangle, and there should be no overlaps or gaps within the large rectangle.

This problem is rated as Hard, and it might be unsolvable without prior experience with similar problems.

The conventional approach would at least require representing the final formed shape and having a method to determine whether two rectangles overlap or if there are gaps, although it can be done, it seems exceptionally complex.

In fact, to determine whether the final shape formed is a perfect rectangle, it is necessary to consider both "area" and "vertices".

Let's first discuss what is meant by the "area" perspective.

Each element in the rectangles array is a tuple (x1, y1, x2, y2), representing the coordinates of the bottom-left and top-right vertices of a small rectangle.

If you assume that these small rectangles ultimately form a "perfect rectangle", would you be able to find the coordinates of the bottom-left vertex (X1, Y1) and the top-right vertex (X2, Y2) of this perfect rectangle?

This is simple, right? The bottom-left vertex (X1, Y1) is the bottom-left vertex of the smallest rectangle in the rectangles that is furthest to the bottom-left; the top-right vertex (X2, Y2) is the top-right vertex of the largest rectangle in the rectangles that is furthest to the top-right.

Note that we use lowercase letters to represent the coordinates of the small rectangles and uppercase letters to represent the coordinates of the final perfect rectangle. The code can be written as follows:

// The bottom-left vertex, initialized to positive infinity to record the minimum value
double X1 = Double.POSITIVE_INFINITY, Y1 = Double.POSITIVE_INFINITY;

// The top-right vertex, initialized to negative infinity to record the maximum value
double X2 = Double.NEGATIVE_INFINITY, Y2 = Double.NEGATIVE_INFINITY;

for(int[] rectangle : rectangles){
    int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];

    // Take the minimum value of the bottom-left vertex of the small rectangle
    X1 = Math.min(X1, x1);
    Y1 = Math.min(Y1, y1);

    // Take the maximum value of the top-right vertex of the small rectangle
    X2 = Math.max(X2, x2);
    Y2 = Math.max(Y2, y2);
}

// The bottom-left vertex, initialized to positive infinity to record the minimum value
int X1 = INT_MAX, Y1 = INT_MAX;
// The top-right vertex, initialized to negative infinity to record the maximum value
int X2 = INT_MIN, Y2 = INT_MIN;

for(auto &rectangle : rectangles) {
    int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
    // Take the minimum value of the bottom-left vertex of the small rectangle
    X1 = min(X1, x1); Y1 = min(Y1, y1);
    // Take the maximum value of the top-right vertex of the small rectangle
    X2 = max(X2, x2); Y2 = max(Y2, y2);
}

# The bottom-left vertex, initialized to positive infinity to record the minimum value
X1, Y1 = inf, inf
# The top-right vertex, initialized to negative infinity to record the maximum value
X2, Y2 = -inf, -inf

for x1, y1, x2, y2 in rectangles:
    # Take the minimum value of the bottom-left vertex of the small rectangle
    X1, Y1 = min(X1, x1), min(Y1, y1)
    # Take the maximum value of the top-right vertex of the small rectangle
    X2, Y2 = max(X2, x2), max(Y2, y2)

// The bottom-left vertex, initialized to positive infinity to record the minimum value
var X1, Y1 float64 = math.MaxFloat64, math.MaxFloat64

// The top-right vertex, initialized to negative infinity to record the maximum value
var X2, Y2 float64 = math.SmallestNonzeroFloat64, math.SmallestNonzeroFloat64

for _, rectangle := range rectangles {
    x1, y1, x2, y2 := rectangle[0], rectangle[1], rectangle[2], rectangle[3]
    // Take the minimum value of the bottom-left vertex of the small rectangle
    X1, Y1 = math.Min(X1, x1), math.Min(Y1, y1)
    // Take the maximum value of the top-right vertex of the small rectangle
    X2, Y2 = math.Max(X2, x2), math.Max(Y2, y2)
}

// The bottom-left vertex, initialized to positive infinity to record the minimum value
var X1 = Number.POSITIVE_INFINITY, Y1 = Number.POSITIVE_INFINITY;
// The top-right vertex, initialized to negative infinity to record the maximum value
var X2 = Number.NEGATIVE_INFINITY, Y2 = Number.NEGATIVE_INFINITY;

for (let i = 0; i < rectangles.length; i++) {
    let rectangle = rectangles[i];
    // Take the minimum value of the bottom-left vertex of the small rectangle
    X1 = Math.min(X1, rectangle[0]);
    Y1 = Math.min(Y1, rectangle[1]);
    // Take the maximum value of the top-right vertex of the small rectangle
    X2 = Math.max(X2, rectangle[2]);
    Y2 = Math.max(Y2, rectangle[3]);
}

This way, you can determine the coordinates of the bottom-left corner (X1, Y1) and the top-right corner (X2, Y2) of the perfect rectangle.

The calculated coordinates X1, Y1, X2, Y2 are the 'theoretical coordinates' of the perfect rectangle. If the sum of the areas of all small rectangles does not equal the theoretical area of this perfect rectangle, it indicates that the final shape must have gaps or overlaps, and thus it is not a perfect rectangle.

The code can be further improved:

boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
    // record the sum of the areas of all small rectangles
    int actualArea = 0;
    for (int[] rect : rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // calculate the theoretical coordinates of the perfect rectangle
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1);
    }

    // calculate the theoretical area of the perfect rectangle
    int expectedArea = (X2 - X1) * (Y2 - Y1);
    // the areas should be the same
    if (actualArea != expectedArea) {
        return false;
    }

    return true;
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
    int X1 = numeric_limits<int>::max(), Y1 = numeric_limits<int>::max();
    int X2 = numeric_limits<int>::min(), Y2 = numeric_limits<int>::min();
    // record the sum of the areas of all small rectangles
    int actualArea = 0;
    for (vector<int>& rect : rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // calculate the theoretical coordinates of the perfect rectangle
        X1 = min(X1, x1);
        Y1 = min(Y1, y1);
        X2 = max(X2, x2);
        Y2 = max(Y2, y2);
        // accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1);
    }

    // calculate the theoretical area of the perfect rectangle
    int expectedArea = (X2 - X1) * (Y2 - Y1);
    // the areas should be the same
    if (actualArea != expectedArea) {
        return false;
    }

    return true;
}

def isRectangleCover(rectangles):
    X1, Y1 = float('inf'), float('inf')
    X2, Y2 = float('-inf'), float('-inf')
    # record the sum of the areas of all small rectangles
    actualArea = 0
    for rect in rectangles:
        x1, y1, x2, y2 = rect
        # calculate the theoretical coordinates of the perfect rectangle
        X1 = min(X1, x1)
        Y1 = min(Y1, y1)
        X2 = max(X2, x2)
        Y2 = max(Y2, y2)
        # accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1)

    # calculate the theoretical area of the perfect rectangle
    expectedArea = (X2 - X1) * (Y2 - Y1)
    # the areas should be the same
    if actualArea != expectedArea:
        return False

    return True

func isRectangleCover(rectangles [][]int) bool {
    X1, Y1, X2, Y2 := math.MaxInt64, math.MaxInt64, math.MinInt64, math.MinInt64
    // record the sum of the areas of all small rectangles
    actualArea := 0
    for _, rect := range rectangles {
        x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
        // calculate the theoretical coordinates of the perfect rectangle
        X1 = min(X1, x1)
        Y1 = min(Y1, y1)
        X2 = max(X2, x2)
        Y2 = max(Y2, y2)
        // accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1)
    }

    // calculate the theoretical area of the perfect rectangle
    expectedArea := (X2 - X1) * (Y2 - Y1)
    // the areas should be the same
    if actualArea != expectedArea {
        return false
    }

    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

var isRectangleCover = function(rectangles) {
    var X1 = Number.MAX_VALUE, Y1 = Number.MAX_VALUE;
    var X2 = Number.MIN_VALUE, Y2 = Number.MIN_VALUE;
    // record the sum of the areas of all small rectangles
    var actualArea = 0;
    for (var rect of rectangles) {
        var x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // calculate the theoretical coordinates of the perfect rectangle
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // accumulate the area of all small rectangles
        actualArea += (x2 - x1) * (y2 - y1);
    }

    // calculate the theoretical area of the perfect rectangle
    var expectedArea = (X2 - X1) * (Y2 - Y1);
    // the areas should be the same
    if (actualArea !== expectedArea) {
        return false;
    }

    return true;
}

This way, the dimension of "area" is completed. The idea is actually not difficult. It's just about assuming that the final shape formed is a perfect rectangle and then comparing whether the areas are equal. If they are not equal, it means that the final shape must have gaps or overlaps and is not a perfect rectangle.

However, conversely, if the areas are the same, can it prove that the final shape is a perfect rectangle and definitely has no gaps or overlaps?

Certainly not. Here's a simple example: imagine a perfect rectangle, and then I cut out a small rectangle from the middle and move it down by one unit. The total area of the small rectangles hasn't changed, but the original perfect rectangle now has a gap and an overlap, and it's no longer a perfect rectangle.

In summary, even if the areas are the same, it cannot fully guarantee that there are no gaps or overlaps. Therefore, we need to use the dimension of "vertices" to help judge.

Remember a puzzle from elementary school? You're given a rectangle and asked how many vertices are left after making one cut. The answer is: if you cut along the diagonal, you're left with 3 vertices; if you cut horizontally or vertically, you have 4 vertices left; if you only cut off a small corner, you end up with 5 vertices.

Coming back to this problem, our next analysis has a bit of that puzzle flavor.

Clearly, a perfect rectangle must have exactly four vertices. By definition, a rectangle should have four vertices. If there are gaps or overlaps, it will not have exactly four vertices. For example, the two cases in the problem statement have more than four vertices:

As long as we can calculate how many vertices are formed by the small rectangles in rectangles, we can determine if the final shape is a perfect rectangle.

So, how are vertices formed? We can easily identify where the vertices are, but the challenge is how to make the computer, or the algorithm, recognize whether a certain point is a vertex. This is the crux of the problem.

Consider the four scenarios in the following diagram:

In the diagram, where the red dots are marked, when is it a vertex and when is it not? Clearly, in scenarios one and three, the points are vertices, whereas in scenarios two and four, they are not.

In other words, if a point is simultaneously a vertex of 2 or 4 small rectangles, it is not a vertex in the final shape; if a point is simultaneously a vertex of 1 or 3 small rectangles, it is a vertex in the final shape.

Note that 2 and 4 are even numbers, while 1 and 3 are odd numbers. To calculate the number of vertices in the final shape, we need to filter out those points that appear an odd number of times. The code can be written as follows:

boolean isRectangleCover(int[][] rectangles) {
    int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
    int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;

    int actualArea = 0;
    // Hash set to record the vertices of the final figure
    Set<String> points = new HashSet<>();
    for (int[] rect : rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);

        actualArea += (x2 - x1) * (y2 - y1);
        // First calculate the coordinates of each point of the small
        // rectangle, represented by a string, for easy storage in the
        String p1 = x1 + "," + y1;
        String p2 = x1 + "," + y2;
        String p3 = x2 + "," + y1;
        String p4 = x2 + "," + y2;
        // For each point, if it exists in the set, remove it;
        // if it does not exist in the set, add it;
        // The remaining points in the set are those that appear an odd number of times
        for (String p : new String[]{p1, p2, p3, p4}) {
            if (points.contains(p)) {
                points.remove(p);
            } else {
                points.add(p);
            }
        }
    }

    int expectedArea = (X2 - X1) * (Y2 - Y1);
    if (actualArea != expectedArea) {
        return false;
    }

    // Check the number of vertices
    if (points.size() != 4 || 
        !points.contains(X1 + "," + Y1) || 
        !points.contains(X1 + "," + Y2) || 
        !points.contains(X2 + "," + Y1) || 
        !points.contains(X2 + "," + Y2)) {
        return false;
    }

    return true;
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
    int X1 = INT_MAX, Y1 = INT_MAX;
    int X2 = INT_MIN, Y2 = INT_MIN;

    int actualArea = 0;
    // Hash set to record the vertices of the final shape
    unordered_set<string> points;

    for (auto &rect : rectangles) {
        int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        X1 = min(X1, x1);
        Y1 = min(Y1, y1);
        X2 = max(X2, x2);
        Y2 = max(Y2, y2);

        actualArea += (x2 - x1) * (y2 - y1);
        // First calculate the coordinates of each point of the small
        // rectangle, represented by a string, for easy storage in the
        string p1 = to_string(x1) + "," + to_string(y1);
        string p2 = to_string(x1) + "," + to_string(y2);
        string p3 = to_string(x2) + "," + to_string(y1);
        string p4 = to_string(x2) + "," + to_string(y2);

        vector<string> pointArr = {p1, p2, p3, p4};
        // For each point, if it exists in the set, remove it;
        // if it does not exist in the set, add it;
        // The remaining points in the set are those that appear an odd number of times
        for (auto &p : pointArr) {
            if (points.count(p)) {
                points.erase(p);
            } else {
                points.insert(p);
            }
        }
    }

    int expectedArea = (X2 - X1) * (Y2 - Y1);
    if (actualArea != expectedArea) {
        return false;
    }

    // Check the number of vertices
    if (points.size() != 4 || 
        !points.count(to_string(X1) + "," + to_string(Y1)) || 
        !points.count(to_string(X1) + "," + to_string(Y2)) || 
        !points.count(to_string(X2) + "," + to_string(Y1)) || 
        !points.count(to_string(X2) + "," + to_string(Y2))) {
        return false;
    }

    return true;
}

def isRectangleCover(rectangles):
    X1, Y1, X2, Y2 = float('inf'), float('inf'), float('-inf'), float('-inf')

    actualArea = 0
    # Hash set to record the vertices of the final shape
    points = set()
    for rect in rectangles:
        x1, y1, x2, y2 = rect
        X1 = min(X1, x1)
        Y1 = min(Y1, y1)
        X2 = max(X2, x2)
        Y2 = max(Y2, y2)

        actualArea += (x2 - x1) * (y2 - y1)
        # First calculate the coordinates of each point of the small
        # rectangle, represented by a string for easy storage in the
        p1 = str(x1) + "," + str(y1)
        p2 = str(x1) + "," + str(y2)
        p3 = str(x2) + "," + str(y1)
        p4 = str(x2) + "," + str(y2)

        pointArr = [p1, p2, p3, p4]
        # For each point, if it exists in the set, remove it;
        for p in pointArr:
            if p in points:
                points.remove(p)
            else:
                points.add(p)
        # If it does not exist in the set, add it;
        # The remaining points in the set are those that appear an odd number of times
        
    expectedArea = (X2 - X1) * (Y2 - Y1)
    if actualArea != expectedArea:
        return False

    # Check the number of vertices
    if len(points) != 4 or \
        str(X1) + "," + str(Y1) not in points or \
        str(X1) + "," + str(Y2) not in points or \
        str(X2) + "," + str(Y1) not in points or \
        str(X2) + "," + str(Y2) not in points:
        return False

    return True

func isRectangleCover(rectangles [][]int) bool {
    X1, Y1 := math.MaxInt32, math.MaxInt32
    X2, Y2 := math.MinInt32, math.MinInt32
  
    var actualArea int
    // hash set to record the vertices of the final shape
    points := map[string]bool{}

    for _, rect := range rectangles{
        x1 := rect[0]
        y1 := rect[1]
        x2 := rect[2]
        y2 := rect[3]

        X1 = int(math.Min(float64(X1), float64(x1)))
        Y1 = int(math.Min(float64(Y1), float64(y1)))
        X2 = int(math.Max(float64(X2), float64(x2)))
        Y2 = int(math.Max(float64(Y2), float64(y2)))

        // calculate the area of the small rectangle
        actualArea += (x2 - x1) * (y2 - y1)

        // first calculate the coordinates of each point of the small
        // rectangle, represent them as strings for easy storage in the
        p1 := fmt.Sprintf("%d,%d", x1, y1)
        p2 := fmt.Sprintf("%d,%d", x1, y2)
        p3 := fmt.Sprintf("%d,%d", x2, y1)
        p4 := fmt.Sprintf("%d,%d", x2, y2)

        pointArr := []string{p1, p2, p3, p4}
        // for each point, if it exists in the set, remove it;
        // if it does not exist in the set, add it;
        // the remaining points in the set are those that appear an odd number of times
        for _, p := range pointArr{
            if _, exists := points[p]; exists{
                delete(points, p)
            } else {
                points[p] = true
            }
        }
    }

    expectedArea := (X2 - X1) * (Y2 - Y1)
    if actualArea != expectedArea {
        return false
    }

    // check the number of vertices
    if len(points) != 4 {
        return false
    }

    if _, ex := points[fmt.Sprintf("%d,%d", X1, Y1)];!ex{
        return false
    }

    if _, ex := points[fmt.Sprintf("%d,%d", X1, Y2)];!ex{
        return false
    }

    if _, ex := points[fmt.Sprintf("%d,%d", X2, Y1)];!ex{
        return false
    }

    if _, ex := points[fmt.Sprintf("%d,%d", X2, Y2)];!ex{
        return false
    }

    return true
}

var isRectangleCover = function(rectangles) {
    var X1 = Number.MAX_VALUE, Y1 = Number.MAX_VALUE;
    var X2 = Number.MIN_VALUE, Y2 = Number.MIN_VALUE;

    var actualArea = 0;
    // Hash set to record the vertices of the final shape
    var points = new Set();
    for (var rect of rectangles) {
        var x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);

        actualArea += (x2 - x1) * (y2 - y1);

        // First calculate the coordinates of each point of the small
        // rectangle, represented as a string for easy storage in the
        var p1 = x1 + "," + y1;
        var p2 = x1 + "," + y2;
        var p3 = x2 + "," + y1;
        var p4 = x2 + "," + y2;

        // For each point, if it exists in the set, delete it;
        // If it does not exist in the set, add it;
        // The remaining points in the set are those that appear an odd number of times
        for (var p of [p1, p2, p3, p4]) {
            if (points.has(p)) {
                points.delete(p);
            } else {
                points.add(p);
            }
        }
    }

    var expectedArea = (X2 - X1) * (Y2 - Y1);
    if (actualArea != expectedArea) {
        return false;
    }

    // Check the number of vertices
    if (points.size != 4 || 
        !points.has(X1 + "," + Y1) || 
        !points.has(X1 + "," + Y2) || 
        !points.has(X2 + "," + Y1) || 
        !points.has(X2 + "," + Y2)) {
        return false;
    }

    return true;
};

In this code, we use a points set to record the vertex coordinates of the final shape formed by the smaller rectangles in rectangles. The key logic lies in how to add coordinates to points:

If a vertex p exists in the points set, remove it; if it does not exist in the points set, insert it.

This simple logic ensures that the points set ultimately retains only those vertices that appear once or three times, while those appearing twice or four times are eliminated.

The first thought is that the points set should finally have only 4 vertices, right? If len(points) != 4, it indicates that the final shape formed is definitely not a perfect rectangle.

However, if len(points) == 4, does it guarantee that the final shape is a perfect rectangle? Not necessarily, because the problem does not state that there are no overlapping smaller rectangles in rectangles, as shown in the following example:

Here, two rectangles overlap, and according to our algorithm logic, their vertices are eliminated, leaving four vertices. Looking at the area, the theoretical coordinates of the perfect rectangle are the red points in the image, and the calculated theoretical area matches the actual area. However, clearly, this situation does not meet the problem's requirement for a perfect rectangle.

Therefore, it is not only necessary to ensure that len(points) == 4, but also to ensure that the remaining points in points are exactly the four theoretical coordinates of a perfect rectangle. Let's take a look at the code:

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
        int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        
        Set<String> points = new HashSet<>();
        int actualArea = 0;
        for (int[] rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            // calculate the theoretical vertex coordinates of the perfect rectangle
            X1 = Math.min(X1, x1);
            Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2);
            Y2 = Math.max(Y2, y2);
            // accumulate the area of small rectangles
            actualArea += (x2 - x1) * (y2 - y1);
            // record the vertices of the final formed shape
            String p1 = x1 + "," + y1;
            String p2 = x1 + "," + y2;
            String p3 = x2 + "," + y1;
            String p4 = x2 + "," + y2;
            for (String p : new String[]{p1, p2, p3, p4}) {
                if (points.contains(p)) {
                    points.remove(p);
                } else {
                    points.add(p);
                }
            }
        }
        // determine if the areas are the same
        int expectedArea = (X2 - X1) * (Y2 - Y1);
        if (actualArea != expectedArea) {
            return false;
        }
        // determine if the number of vertices left is 4
        if (points.size() != 4) {
            return false;
        }
        // determine if the 4 vertices left are the vertices of the perfect rectangle
        if (!points.contains(X1 + "," + Y1)) return false;
        if (!points.contains(X1 + "," + Y2)) return false;
        if (!points.contains(X2 + "," + Y1)) return false;
        if (!points.contains(X2 + "," + Y2)) return false;
        // both the area and the vertices match, indicating the rectangle meets the requirements
        return true;
    }
}

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int X1 = INT_MAX, Y1 = INT_MAX;
        int X2 = INT_MIN, Y2 = INT_MIN;
        
        set<string> points;
        long actualArea = 0;
        
        for (auto & rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            // calculate the theoretical vertex coordinates of the perfect rectangle
            X1 = min(X1, x1);
            Y1 = min(Y1, y1);
            X2 = max(X2, x2);
            Y2 = max(Y2, y2);
            // accumulate the area of small rectangles
            actualArea += long(x2 - x1) * (y2 - y1);
            // record the vertices of the final formed shape
            string p1 = to_string(x1) + "," + to_string(y1);
            string p2 = to_string(x1) + "," + to_string(y2);
            string p3 = to_string(x2) + "," + to_string(y1);
            string p4 = to_string(x2) + "," + to_string(y2);
            for (string p : {p1, p2, p3, p4}) {
                if (points.count(p)) {
                    points.erase(p);
                } else {
                    points.insert(p);
                }
            }
        }
        // determine if the areas are the same
        long expectedArea = long(X2 - X1) * (Y2 - Y1);
        if (actualArea != expectedArea) {
            return false;
        }
        // determine if the number of vertices left is 4
        if (points.size() != 4) {
            return false;
        }
        // determine if the 4 vertices left are the vertices of the perfect rectangle
        if (!points.count(to_string(X1) + "," + to_string(Y1))) return false;
        if (!points.count(to_string(X1) + "," + to_string(Y2))) return false;
        if (!points.count(to_string(X2) + "," + to_string(Y1))) return false;
        if (!points.count(to_string(X2) + "," + to_string(Y2))) return false;
        // both area and vertices match, indicating the rectangle meets the requirements
        return true;
    }
};

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        X1, Y1 = float('inf'), float('inf')
        X2, Y2 = float('-inf'), float('-inf')

        points = set()
        actualArea = 0
        for rect in rectangles:
            x1, y1, x2, y2 = rect
            # calculate the theoretical vertex coordinates of the perfect rectangle
            X1 = min(X1, x1)
            Y1 = min(Y1, y1)
            X2 = max(X2, x2)
            Y2 = max(Y2, y2)
            # accumulate the area of small rectangles
            actualArea += (x2 - x1) * (y2 - y1)
            # record the vertices in the final formed shape
            p1 = str(x1) + "," + str(y1)
            p2 = str(x1) + "," + str(y2)
            p3 = str(x2) + "," + str(y1)
            p4 = str(x2) + "," + str(y2)
            for p in [p1, p2, p3, p4]:
                if p in points:
                    points.remove(p)
                else:
                    points.add(p)

        # determine if the areas are the same
        expectedArea = (X2 - X1) * (Y2 - Y1)
        if actualArea != expectedArea:
            return False
        # determine if the number of vertices left is 4
        if len(points) != 4:
            return False
        # determine if the 4 vertices left are the vertices of the perfect rectangle
        if not str(X1) + "," + str(Y1) in points: return False
        if not str(X1) + "," + str(Y2) in points: return False
        if not str(X2) + "," + str(Y1) in points: return False
        if not str(X2) + "," + str(Y2) in points: return False
        # both area and vertices correspond, indicating the rectangle meets the requirements
        return True

func isRectangleCover(rectangles [][]int) bool {
    X1, Y1 := math.MaxInt64, math.MaxInt64
    X2, Y2 := math.MinInt64, math.MinInt64
    points := make(map[string]bool)
    actualArea := 0
    for _, rect := range rectangles {
        x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
        // calculate the theoretical vertex coordinates of the perfect rectangle
        X1 = min(X1, x1)
        Y1 = min(Y1, y1)
        X2 = max(X2, x2)
        Y2 = max(Y2, y2)
        // accumulate the area of small rectangles
        actualArea += (x2 - x1) * (y2 - y1)
        // record the vertices of the final shape
        p1 := fmt.Sprintf("%d,%d", x1, y1)
        p2 := fmt.Sprintf("%d,%d", x1, y2)
        p3 := fmt.Sprintf("%d,%d", x2, y1)
        p4 := fmt.Sprintf("%d,%d", x2, y2)
        for _, p := range []string{p1, p2, p3, p4} {
            if _, exists := points[p]; exists {
                delete(points, p)
            } else {
                points[p] = true
            }
        }
    }
    // determine if the areas are the same
    expectedArea := (X2 - X1) * (Y2 - Y1)
    if actualArea != expectedArea {
        return false
    }

    // determine if the number of vertices left is 4
    if len(points) != 4 {
        return false
    }
    // determine if the 4 vertices left are the vertices of the perfect rectangle
    if _, ex := points[fmt.Sprintf("%d,%d", X1, Y1)]; !ex {
        return false
    }
    if _, ex := points[fmt.Sprintf("%d,%d", X1, Y2)]; !ex {
        return false
    }
    if _, ex := points[fmt.Sprintf("%d,%d", X2, Y1)]; !ex {
        return false
    }
    if _, ex := points[fmt.Sprintf("%d,%d", X2, Y2)]; !ex {
        return false
    }
    // both the area and the vertices correspond,
    // indicating that the rectangle meets the
    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

var isRectangleCover = function(rectangles) {
    let X1 = Number.MAX_VALUE, Y1 = Number.MAX_VALUE;
    let X2 = Number.MIN_VALUE, Y2 = Number.MIN_VALUE;
    let points = new Set();
    let actualArea = 0;
    for (let rect of rectangles) {
        let x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
        // calculate the theoretical vertex coordinates of the perfect rectangle
        X1 = Math.min(X1, x1);
        Y1 = Math.min(Y1, y1);
        X2 = Math.max(X2, x2);
        Y2 = Math.max(Y2, y2);
        // accumulate the area of small rectangles
        actualArea += (x2 - x1) * (y2 - y1);
        // record the vertices in the final formed shape
        let p1 = x1 + "," + y1;
        let p2 = x1 + "," + y2;
        let p3 = x2 + "," + y1;
        let p4 = x2 + "," + y2;
        for (let p of [p1, p2, p3, p4]) {
            if (points.has(p)) {
                points.delete(p);
            } else {
                points.add(p);
            }
        }
    }
    // determine if the areas are the same
    let expectedArea = (X2 - X1) * (Y2 - Y1);
    if (actualArea !== expectedArea) {
        return false;
    }
    // determine if the number of vertices left is 4
    if (points.size !== 4) {
        return false;
    }
    // determine if the 4 vertices left are the vertices of the perfect rectangle
    if (!points.has(X1 + "," + Y1)) return false;
    if (!points.has(X1 + "," + Y2)) return false;
    if (!points.has(X2 + "," + Y1)) return false;
    if (!points.has(X2 + "," + Y2)) return false;
    // both the area and the vertices correspond,
    // indicating that the rectangle meets the
    return true;
};

This is the final solution code, which judges from two dimensions: "area" and "vertices":

1. Judging the Area: Calculate a theoretical area using the theoretical coordinates of a perfect rectangle, and then compare it with the sum of the actual areas of the smaller rectangles in rectangles.

2. Judging the Vertices: The points set should contain only 4 vertices, and these remaining vertices must all be the theoretical vertices of the perfect rectangle.