LeetCode 0836. Rectangle Overlap Solution in Java, C++, Python & More | Explanation + Code

Description

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

 

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false

 

Constraints:

• rec1.length == 4
• rec2.length == 4
• -109 <= rec1[i], rec2[i] <= 109
• rec1 and rec2 represent a valid rectangle with a non-zero area.

Solutions

Solution 1: Determine Non-Overlap Cases

Let the coordinates of rectangle rec1 be (x_1, y_1, x_2, y_2), and the coordinates of rectangle rec2 be (x_3, y_3, x_4, y_4).

The rectangles rec1 and rec2 do not overlap if any of the following conditions are met:

• y_3 ≥ y_2: rec2 is above rec1;
• y_4 ≤ y_1: rec2 is below rec1;
• x_3 ≥ x_2: rec2 is to the right of rec1;
• x_4 ≤ x_1: rec2 is to the left of rec1.

If none of the above conditions are met, the rectangles rec1 and rec2 overlap.

The time complexity is O(1), and the space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool: x1, y1, x2, y2 = rec1 x3, y3, x4, y4 = rec2 return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)(code-box)

class Solution { public boolean isRectangleOverlap(int[] rec1, int[] rec2) { int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3]; int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3]; return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1); } }(code-box)

class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) { int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3]; int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3]; return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1); } };(code-box)

func isRectangleOverlap(rec1 []int, rec2 []int) bool { x1, y1, x2, y2 := rec1[0], rec1[1], rec1[2], rec1[3] x3, y3, x4, y4 := rec2[0], rec2[1], rec2[2], rec2[3] return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1) }(code-box)

function isRectangleOverlap(rec1: number[], rec2: number[]): boolean { const [x1, y1, x2, y2] = rec1; const [x3, y3, x4, y4] = rec2; return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1); }(code-box)