Jobs

Interviews

Discussions

Rectangle Overlap

Easy

Google

5 views

Topics:

Arrays

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.

For example:

rec1 = [0,0,2,2], rec2 = [1,1,3,3] should return true
rec1 = [0,0,1,1], rec2 = [1,0,2,1] should return false
rec1 = [0,0,1,1], rec2 = [2,2,3,3] should return false

Write a function to determine whether the two rectangles overlap, given their coordinates.

Rectangle Overlap

Easy

Google

5 views

Topics:

Arrays

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.

For example:

rec1 = [0,0,2,2], rec2 = [1,1,3,3] should return true
rec1 = [0,0,1,1], rec2 = [1,0,2,1] should return false
rec1 = [0,0,1,1], rec2 = [2,2,3,3] should return false

Write a function to determine whether the two rectangles overlap, given their coordinates.

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.

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

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

Space Complexity

Optimal Solution

Approach

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

Space Complexity

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.