836 LeetCode problem solution

LeetCode problem link: 836. Rectangle Overlap

LeetCode 836 problem description

This is Easy level problem.

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.

LeetCode 836 problem: solution explanation

This is very easy problem.
For solving this problem we use the Interval Overlap pattern (basic case of Interval Intersection).

LeetCode 836 uses the Interval Overlap pattern, which is the basic operation behind the broader Interval Intersection pattern. Instead of processing two sorted lists of intervals with Two Pointers, we only need to check whether two rectangles overlap. Each rectangle can be viewed as an interval on the X-axis and another interval on the Y-axis. We check for a positive overlap on both axes using max(start1, start2) < min(end1, end2). If both checks are true, the rectangles have a positive intersection area.

In detail:

Two rectangles overlap only if they overlap on both the X-axis and the Y-axis.
For the X-axis, the left boundary of the intersection is the larger of the two left edges.
The right boundary is the smaller of the two right edges.
There is a positive overlap on the X-axis only if the left boundary is strictly smaller than the right boundary.
We apply the same logic to the Y-axis using the bottom and top edges.
The comparison must use < instead of <= because touching at an edge or corner does not create a positive area.
If both axis checks are true, the rectangles overlap; otherwise, they do not.
The solution runs in O(1) time and uses O(1) space.

Time complexity: O(1)
Space complexity: O(1)

LeetCode 836 C++ solution

class Solution {
public:
  bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
    return max(rec1[0], rec2[0]) < min(rec1[2], rec2[2]) &&
      max(rec1[1], rec2[1]) < min(rec1[3], rec2[3]);
  }
};

LeetCode 836 Java solution

class Solution {
  public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    return Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]) &&
      Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);
  }
}

LeetCode 836 JavaScript solution

var isRectangleOverlap = function(rec1, rec2) {
  return Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]) &&
    Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);
};

LeetCode 836 TypeScript solution

function isRectangleOverlap(rec1: number[], rec2: number[]): boolean {
  return Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]) &&
    Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);
};

LeetCode 836 Python solution

class Solution:
  def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
    return max(rec1[0], rec2[0]) < min(rec1[2], rec2[2]) and \
      max(rec1[1], rec2[1]) < min(rec1[3], rec2[3])