Rectangle Overlap - Leetcode Solution

Rectangle Overlap is a problem on LeetCode where we are given two rectangles in a plane, each defined by two sets of coordinates, (x1, y1), (x2, y2) representing the bottom-left and top-right corners respectively. Our task is to determine if the two rectangles overlap or not.

To solve this problem, we need to first understand what it means for two rectangles to overlap. Two rectangles overlap if and only if their x and y ranges intersect. The x range for a rectangle is (x1, x2) while the y range is (y1, y2).

Thus, to determine if the two rectangles overlap, we need to check if their x and y ranges intersect.

The first step is to find the x and y ranges of the two rectangles. We can do this by computing the minimum and maximum values for x and y for both rectangles.

Code to find x and y ranges for each rectangle:

int x1 = Math.min(rec1[0], rec1[2]);
int y1 = Math.min(rec1[1], rec1[3]);
int x2 = Math.max(rec1[0], rec1[2]);
int y2 = Math.max(rec1[1], rec1[3]);

int x3 = Math.min(rec2[0], rec2[2]);
int y3 = Math.min(rec2[1], rec2[3]);
int x4 = Math.max(rec2[0], rec2[2]);
int y4 = Math.max(rec2[1], rec2[3]);

Next, we need to check if the x and y ranges intersect. If they do, the rectangles overlap, and we return true. Otherwise, they do not overlap and we return false.

Code to check for intersection:

if (x1 >= x4 || x2 <= x3 || y1 >= y4 || y2 <= y3) {
    return false;
} else {
    return true;
}

The condition to check for intersection is that one rectangle's x range is entirely to the left of the other rectangle's x range (x1 >= x4 or x2 <= x3) or one rectangle's y range is entirely above or below the other rectangle's y range (y1 >= y4 or y2 <= y3). In either case, the rectangles do not intersect.

The complete code for the Rectangle Overlap problem is as follows:

public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    int x1 = Math.min(rec1[0], rec1[2]);
    int y1 = Math.min(rec1[1], rec1[3]);
    int x2 = Math.max(rec1[0], rec1[2]);
    int y2 = Math.max(rec1[1], rec1[3]);

    int x3 = Math.min(rec2[0], rec2[2]);
    int y3 = Math.min(rec2[1], rec2[3]);
    int x4 = Math.max(rec2[0], rec2[2]);
    int y4 = Math.max(rec2[1], rec2[3]);

    if (x1 >= x4 || x2 <= x3 || y1 >= y4 || y2 <= y3) {
        return false;
    } else {
        return true;
    }
}

This solution has a time complexity of O(1), as we are performing a constant number of operations on the input coordinates.

1