Back to Math And Geometry
Overlapping Rectangles
Overlapping Rectangles
š§© Problem Statement
Determine if two axis-aligned rectangles overlap.
Each rectangle is represented by its bottom-left (x1, y1) and top-right (x2, y2) coordinates.
š¹ 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
Explanation: They touch at the edge but typically "overlap" implies positive area. In some variations, touching is allowed, but usually strict overlap is required (area > 0). We will assume strict overlap.
š Approaches
1. Coordinate Check ($O(1)$)
- Concept: Two rectangles DO NOT overlap if one is completely to the left, right, top, or bottom of the other.
- Logic (Non-Overlap):
rec1is Left ofrec2:rec1.x2 <= rec2.x1rec1is Right ofrec2:rec1.x1 >= rec2.x2rec1is Belowrec2:rec1.y2 <= rec2.y1rec1is Aboverec2:rec1.y1 >= rec2.y2- Overlap Condition: The negation of the above.
- Formula:
!(Left || Right || Below || Above) - Simplified:
rec1.x1 < rec2.x2 && rec1.x2 > rec2.x1 && rec1.y1 < rec2.y2 && rec1.y2 > rec2.y1
ā³ Time & Space Complexity
- Time Complexity: $O(1)$.
- Space Complexity: $O(1)$.
š Code Implementations
C++
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
// Check if rec1 is completely left, right, top, or bottom of rec2
return !(rec1[2] <= rec2[0] || // left
rec1[3] <= rec2[1] || // bottom
rec1[0] >= rec2[2] || // right
rec1[1] >= rec2[3]); // top
}
};
Python
from typing import List
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
# rec1 = [x1, y1, x2, y2]
# Overlap if:
# rec1.x1 < rec2.x2 AND rec1.x2 > rec2.x1 AND
# rec1.y1 < rec2.y2 AND rec1.y2 > rec2.y1
return (rec1[0] < rec2[2] and rec1[2] > rec2[0] and
rec1[1] < rec2[3] and rec1[3] > rec2[1])
Java
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return (rec1[0] < rec2[2] && rec1[2] > rec2[0] &&
rec1[1] < rec2[3] && rec1[3] > rec2[1]);
}
}
š Real-World Analogy
Window Selection:
On a computer screen, a window is focused (interactable) if it's on top. If you try to drag a selection box, it selects icons only if the selection rectangle overlaps with the icon's bounding box.
šÆ Summary
ā Negation Logic: Easier to check when they don't overlap.
Solution Code
O(n) TimeO(1) Space
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// rec = [x1, y1, x2, y2]
bool isRectangleOverlap(vector<int> &rec1, vector<int> &rec2) {
// Standard strict overlap check
// width overlap && height overlap
// width overlap: max(x1, x1') < min(x2, x2')
return (max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])) &&
(max(rec1[1], rec2[1]) < min(rec1[3], rec2[3]));
}
};
int main() {
Solution sol;
vector<int> r1 = {0, 0, 2, 2};
vector<int> r2 = {1, 1, 3, 3};
cout << boolalpha
<< "Test Case 1 (Overlap): " << sol.isRectangleOverlap(r1, r2)
<< endl; // true
vector<int> r3 = {0, 0, 1, 1};
vector<int> r4 = {1, 0, 2, 1};
cout << "Test Case 2 (Touch): " << sol.isRectangleOverlap(r3, r4)
<< endl; // false
return 0;
}
SYSTEM STABLEUTF-8 ā¢ STATIC_RENDER