Rectangle Overlap

Easy

Amazon

2 views

Topics:

Arrays

Rectangle Overlap Problem

You are given two axis-aligned rectangles. Each rectangle is represented by a list of four integers: [x1, y1, x2, y2], where (x1, y1) is the coordinate of the bottom-left corner, and (x2, y2) is the coordinate of the top-right corner. The sides of the rectangles are parallel to the x and y axes.

Objective: Write a function that determines whether the two rectangles overlap. Two rectangles overlap if the area of their intersection is positive. Rectangles that only touch at a corner or edge are considered non-overlapping.

Examples:

Input: rec1 = [0, 0, 2, 2], rec2 = [1, 1, 3, 3] Output: true (The rectangles overlap as their intersection has a positive area.)
Input: rec1 = [0, 0, 1, 1], rec2 = [1, 0, 2, 1] Output: false (The rectangles touch along an edge but do not overlap.)
Input: rec1 = [0, 0, 1, 1], rec2 = [2, 2, 3, 3] Output: false (The rectangles are completely disjoint and do not overlap.)

Constraints:

Each rectangle is represented by a list of four integers.
The coordinates can be any integer.
You can assume that the input rectangles are valid (i.e., x1 < x2 and y1 < y2 for each rectangle).

Rectangle Overlap

Easy

Amazon

2 views

Topics:

Arrays

Rectangle Overlap Problem

You are given two axis-aligned rectangles. Each rectangle is represented by a list of four integers: [x1, y1, x2, y2], where (x1, y1) is the coordinate of the bottom-left corner, and (x2, y2) is the coordinate of the top-right corner. The sides of the rectangles are parallel to the x and y axes.

Objective: Write a function that determines whether the two rectangles overlap. Two rectangles overlap if the area of their intersection is positive. Rectangles that only touch at a corner or edge are considered non-overlapping.

Examples:

Input: rec1 = [0, 0, 2, 2], rec2 = [1, 1, 3, 3] Output: true (The rectangles overlap as their intersection has a positive area.)
Input: rec1 = [0, 0, 1, 1], rec2 = [1, 0, 2, 1] Output: false (The rectangles touch along an edge but do not overlap.)
Input: rec1 = [0, 0, 1, 1], rec2 = [2, 2, 3, 3] Output: false (The rectangles are completely disjoint and do not overlap.)

Constraints:

Each rectangle is represented by a list of four integers.
The coordinates can be any integer.
You can assume that the input rectangles are valid (i.e., x1 < x2 and y1 < y2 for each rectangle).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the rectangle coordinates integers? What is the range of possible values for the coordinates?
Is it possible for a rectangle to have zero area (e.g., x1 == x2 or y1 == y2)? If so, how should that be handled?
If the rectangles only touch at an edge or a corner, should that be considered an overlap?
Can I assume that x1 is always less than x2 and y1 is always less than y2 for both rectangles?
What should I return if either rec1 or rec2 is null or empty?

Brute Force Solution

Approach

To determine if two rectangles overlap using a brute force strategy, we essentially check all the ways they could possibly *not* overlap. If none of those non-overlapping scenarios are true, then the rectangles must overlap.

Here's how the algorithm would work step-by-step:

First, imagine the first rectangle is entirely to the left of the second rectangle. Check if this is true.
Next, consider if the first rectangle is entirely to the right of the second rectangle. Check if this is true.
Then, think about the first rectangle being completely above the second rectangle. Check if this is true.
Finally, picture the first rectangle being completely below the second rectangle. Check if this is true.
If none of the above scenarios are true - meaning the rectangles are NOT separated in any of those ways - we can conclude that the two rectangles must be overlapping.

Code Implementation

def is_rectangle_overlap(rectangle_one, rectangle_two):
    # Check if rectangle one is to the left of rectangle two
    if rectangle_one[2] <= rectangle_two[0]:
        return False

    # Check if rectangle one is to the right of rectangle two
    if rectangle_one[0] >= rectangle_two[2]:
        return False

    # Check if rectangle one is above rectangle two
    if rectangle_one[3] <= rectangle_two[1]:
        return False

    # Check if rectangle one is below rectangle two
    if rectangle_one[1] >= rectangle_two[3]:
        return False

    # If none of the above conditions are true, then the rectangles overlap
    return True

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves a fixed number of comparisons to determine if the rectangles overlap. The input size, which could be the coordinates of the rectangles, does not affect the number of operations performed. There are only four independent constant-time checks, therefore the time complexity remains constant regardless of the input values.

Space Complexity

O(1) – The algorithm checks a fixed number of conditions (whether the rectangles are to the left, right, above, or below each other). It only uses a constant number of variables to store boolean results of these checks and perform comparisons. The space used does not depend on the size or dimensions of the input rectangles. Therefore, the space complexity is constant.

Optimal Solution

Approach

The core idea is to determine when rectangles *don't* overlap, which is easier to check. If none of these non-overlap conditions are met, then the rectangles must overlap. This avoids complicated geometric calculations.

Here's how the algorithm would work step-by-step:

Imagine two rectangles: A and B.
First, check if rectangle A is completely to the left of rectangle B. If it is, they don't overlap.
Next, check if rectangle A is completely to the right of rectangle B. If it is, they don't overlap.
Then, check if rectangle A is completely above rectangle B. If it is, they don't overlap.
Finally, check if rectangle A is completely below rectangle B. If it is, they don't overlap.
If none of the above conditions are true, it means the rectangles must be overlapping. Return true in this case.

Code Implementation

def is_rectangle_overlap(rectangle_a, rectangle_b):
    # Check if rectangle A is to the left of rectangle B
    if rectangle_a[2] <= rectangle_b[0]:
        return False

    # Check if rectangle A is to the right of rectangle B
    if rectangle_a[0] >= rectangle_b[2]:
        return False

    # Check if rectangle A is above rectangle B
    if rectangle_a[3] <= rectangle_b[1]:
        return False

    # Check if rectangle A is below rectangle B
    if rectangle_a[1] >= rectangle_b[3]:
        return False

    # If none of the above conditions are true, rectangles overlap
    return True

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves a fixed number of comparisons (specifically, four comparisons) to determine if two rectangles overlap. These comparisons are independent of the size or characteristics of the rectangles themselves, and the operations don't scale with any input 'n'. Therefore, the time complexity is constant.

Space Complexity

O(1) – The provided plain English explanation does not explicitly describe the creation of any auxiliary data structures such as arrays, lists, or hash maps. The algorithm's operations only involve comparisons of the input rectangle coordinates. Therefore, the auxiliary space used is constant and independent of the input size N, where N is the number of coordinates defining the rectangles.

Edge Cases

Case	How to Handle
Null or empty input arrays (rec1 or rec2 is null or empty)	Return false immediately as an empty rectangle cannot overlap.
Invalid rectangle: x1 >= x2 or y1 >= y2 for either rectangle	Return false because it represents an invalid or degenerate rectangle with no area.
Rectangles are identical (same coordinates)	Return true as identical rectangles clearly overlap.
Rectangles share a side (touching, but not overlapping)	Return false as touching sides does not constitute overlap.
One rectangle is completely contained within the other	Return true as the inner rectangle is overlapping.
Negative coordinates for rectangles	The overlap condition should correctly handle negative coordinates since it considers relative positions.
Large coordinate values that could potentially cause integer overflow during calculations	Ensure calculations are performed using a data type large enough to accommodate the potential range of coordinate differences (e.g., long).
Extreme coordinate values (close to the maximum/minimum integer values)	The overlap condition will still work correctly assuming no overflow occurs in the calculation.