Leetcode 836. Rectangle Overlap

Problem Explanation

Given two rectangles, you are asked to determine if they overlap. A rectangle is represented by its bottom-left coordinates and its top-right coordinates in the form of rec = [x1, y1, x2, y2]. Two rectangles are considered to overlap if the area of their intersection is positive. This means that rectangles that only touch at the corner or edges do not overlap.

For example, given two rectangles rec1 = [0,0,2,2] and rec2 = [1,1,3,3] the output would be true because they overlap. However if you are given the rectangles rec1 = [0,0,1,1] and rec2 = [1,0,2,1] the output would be false because they do not overlap but only touch at an edge.

Solution Approach

The solution uses a simple condition check approach. Two rectangles overlap if one rectangle's left edge, i.e. (x1), is to the left of the other rectangle's right edge, x2 and the rectangle's right edge, i.e. x2, is to the right of the other rectangle's left edge, x1. Similarly, one rectangle's bottom edge, y1, must be below the other's top edge, y2, and the rectangle's top edge, y2, must be above the other's bottom edge, y1. If all these conditions are met, the rectangles overlap.

Solution in Python

1
2python
3class Solution:
4    def isRectangleOverlap(self, rec1, rec2):
5        return rec1[0] < rec2[2] and rec2[0] < rec1[2] and rec1[1] < rec2[3] and rec2[1] < rec1[3]

Solution in Java

1
2java
3class Solution {
4    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3];
6    }
7}

Solution in JavaScript

1
2javascript
3class Solution {
4    isRectangleOverlap(rec1, rec2) {
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3];
6    }
7};

Solution in C++

1
2c++
3class Solution {
4public:
5    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
6        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3];
7    }
8};

Solution in C#

1
2csharp
3public class Solution {
4    public bool IsRectangleOverlap(int[] rec1, int[] rec2) {
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3];
6    }
7}

Solution in Ruby

1
2ruby
3class Solution
4    def isRectangleOverlap(rec1, rec2)
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3]
6    end
7end

Solution in Swift

1
2swift
3class Solution {
4    func isRectangleOverlap(_ rec1: [Int], _ rec2: [Int]) -> Bool {
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3]
6    }
7}

Solution in Kotlin

1
2kotlin
3class Solution {
4    fun isRectangleOverlap(rec1: IntArray, rec2: IntArray): Boolean {
5        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3]
6    }
7}

Conclusion

The problem of determining whether two rectangles overlap can be solved by checking if each edge of one rectangle lies beyond the corresponding edge of the other rectangle. The solution is efficient and straightforward in any programming language including Python, JavaScript, Java, C++, C#, Ruby, Swift, and Kotlin. The key takeaway from this problem is that oftentimes, complex-sounding problems can be boiled down to simple condition checks, emphasizing the importance of understanding the problem deeply before diving into code.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ