Jobs

Interviews

Discussions

Rectangle Area

#486 Most AskedMedium

Rectangle Area #486 Most Asked

Medium

Microsoft

4 views

Topics:

Arrays

Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).

Example 1:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16

Constraints:

-10⁴ <= ax1 <= ax2 <= 10⁴
-10⁴ <= ay1 <= ay2 <= 10⁴
-10⁴ <= bx1 <= bx2 <= 10⁴
-10⁴ <= by1 <= by2 <= 10⁴

Try coding it in LeetCode

Rectangle Area

#486 Most AskedMedium

Rectangle Area #486 Most Asked

Medium

Microsoft

4 views

Topics:

Arrays

Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).

Example 1:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16

Constraints:

-10⁴ <= ax1 <= ax2 <= 10⁴
-10⁴ <= ay1 <= ay2 <= 10⁴
-10⁴ <= bx1 <= bx2 <= 10⁴
-10⁴ <= by1 <= by2 <= 10⁴

Try coding it in LeetCode

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 represented by integers or floating-point numbers?
Can the coordinates be negative, zero, or exceed the maximum integer value?
Is it guaranteed that the input coordinates represent valid rectangles (i.e., x1 < x2 and y1 < y2)?
If the rectangles do not overlap, should I return 0?
Should I consider the area of the intersection of the rectangles, or the total area covered by the rectangles?

Brute Force Solution

Approach

To find the total area covered by two rectangles, the brute force approach directly checks every single point in a large enough space. We determine if each point is inside either of the rectangles.

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

First, find the smallest and largest x and y coordinates among the corners of both rectangles. This will define a box large enough to contain both rectangles.
Imagine a grid covering this box. Check each point in this grid, one by one.
For each point, determine if it is inside the first rectangle.
If the point is not inside the first rectangle, check if it is inside the second rectangle.
If the point is inside either the first or second rectangle, count it as part of the total area.
After checking all points in the grid, the total count represents the approximate total area covered by the rectangles.

Code Implementation

def rectangle_area(rectangle_one, rectangle_two):
    x_one_rectangle_one, y_one_rectangle_one, x_two_rectangle_one, y_two_rectangle_one = rectangle_one
    x_one_rectangle_two, y_one_rectangle_two, x_two_rectangle_two, y_two_rectangle_two = rectangle_two

    # Find the bounds of a box containing both rectangles
    min_x = min(x_one_rectangle_one, x_one_rectangle_two, x_two_rectangle_one, x_two_rectangle_two)
    min_y = min(y_one_rectangle_one, y_one_rectangle_two, y_two_rectangle_one, y_two_rectangle_two)
    max_x = max(x_one_rectangle_one, x_one_rectangle_two, x_two_rectangle_one, x_two_rectangle_two)
    max_y = max(y_one_rectangle_one, y_one_rectangle_two, y_two_rectangle_one, y_two_rectangle_two)

    total_area = 0
    # Iterate over all possible points within the bounding box.
    for x_coordinate in range(min_x, max_x + 1):
        for y_coordinate in range(min_y, max_y + 1):

            # Check if the current point is inside rectangle one.
            if (x_one_rectangle_one <= x_coordinate <= x_two_rectangle_one) and \
               (y_one_rectangle_one <= y_coordinate <= y_two_rectangle_one):
                total_area += 1
            else:

                # Check if the current point is inside rectangle two.
                if (x_one_rectangle_two <= x_coordinate <= x_two_rectangle_two) and \
                   (y_one_rectangle_two <= y_coordinate <= y_two_rectangle_two):
                    total_area += 1

    return total_area

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through a grid whose size depends on the difference between the minimum and maximum x and y coordinates of the two rectangles. The size of this grid, let's say n x n, determines the input size. For each point (x, y) in this grid, the algorithm performs a constant number of checks to determine if it lies within either rectangle. Therefore, the algorithm's runtime is proportional to the number of points in the grid, which is n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The described brute force approach requires storing a few variables to hold the smallest and largest x and y coordinates and to iterate through the grid. The size of the grid is determined by these minimum and maximum coordinate values, but the algorithm doesn't explicitly store the grid or any data structure proportional to its size. The space used for the coordinate variables and loop counters remains constant regardless of the rectangle dimensions, thus the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the area covered by two rectangles, we don't need to calculate areas separately and then figure out the overlap. We calculate individual areas and then intelligently figure out the overlapping area (if any) to avoid double-counting.

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

Calculate the area of the first rectangle.
Calculate the area of the second rectangle.
Determine if the two rectangles overlap. This involves checking if they intersect horizontally and vertically.
If they don't overlap, the total area is just the sum of the two individual areas. You're done!
If they do overlap, calculate the area of the overlapping region.
To get the total area covered, add the areas of the two rectangles and then subtract the area of the overlap. This avoids counting the overlapping region twice.

Code Implementation

def calculate_total_area(
    rectangle_one_bottom_left_x,
    rectangle_one_bottom_left_y,
    rectangle_one_top_right_x,
    rectangle_one_top_right_y,
    rectangle_two_bottom_left_x,
    rectangle_two_bottom_left_y,
    rectangle_two_top_right_x,
    rectangle_two_top_right_y
):
    rectangle_one_area = (
        rectangle_one_top_right_x - rectangle_one_bottom_left_x
    ) * (rectangle_one_top_right_y - rectangle_one_bottom_left_y)
    rectangle_two_area = (
        rectangle_two_top_right_x - rectangle_two_bottom_left_x
    ) * (rectangle_two_top_right_y - rectangle_two_bottom_left_y)

    # Determine the overlap region boundaries
    overlap_left_x = max(
        rectangle_one_bottom_left_x, rectangle_two_bottom_left_x
    )
    overlap_right_x = min(
        rectangle_one_top_right_x, rectangle_two_top_right_x
    )
    overlap_bottom_y = max(
        rectangle_one_bottom_left_y, rectangle_two_bottom_left_y
    )
    overlap_top_y = min(
        rectangle_one_top_right_y, rectangle_two_top_right_y
    )

    # If no overlap, return sum of individual areas
    if overlap_left_x >= overlap_right_x or overlap_bottom_y >= overlap_top_y:
        return rectangle_one_area + rectangle_two_area

    # We have overlap, calculate area of overlap

    overlap_area = (
        overlap_right_x - overlap_left_x
    ) * (overlap_top_y - overlap_bottom_y)

    # Avoid double counting by subtracting overlap
    return rectangle_one_area + rectangle_two_area - overlap_area

Big(O) Analysis

Time Complexity

O(1) – The algorithm calculates the areas of two rectangles and checks for overlap using a fixed number of arithmetic and comparison operations. These operations are independent of the input size (the coordinates of the rectangles). Therefore, the time complexity remains constant regardless of the input, resulting in O(1) time complexity.

Space Complexity

O(1) – The provided steps describe calculating areas and checking for overlap using a few variables to store coordinates and areas. No additional data structures like arrays, hash maps, or recursion are involved. The amount of memory used for these variables remains constant regardless of the size of the input rectangles' coordinates. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or undefined input rectangles	Throw an IllegalArgumentException or return 0, based on the preferred error handling strategy and problem statement requirements.
Rectangles with zero width or height	Treat these as having an area of zero and handle calculations appropriately without causing errors.
Rectangles with negative coordinates	The problem description should clarify whether negative coordinates are allowed; If allowed, properly compute width/height using absolute difference.
Integer overflow when calculating area or sum of areas	Use a larger data type (e.g., long) for intermediate calculations to prevent overflow issues.
Rectangles with very large coordinates that could lead to overflow	Ensure all coordinate calculations use long data types to mitigate risk of integer overflow during area calculations.
Two rectangles are identical	The intersection area is equal to the area of either rectangle.
One rectangle is completely contained within the other	Intersection area is the area of the smaller rectangle.
Rectangles that do not overlap at all	The intersection area is zero in this case.

Null or undefined input rectangles

How to Handle:

Throw an IllegalArgumentException or return 0, based on the preferred error handling strategy and problem statement requirements.

Rectangles with zero width or height

How to Handle:

Treat these as having an area of zero and handle calculations appropriately without causing errors.

Rectangles with negative coordinates

How to Handle:

The problem description should clarify whether negative coordinates are allowed; If allowed, properly compute width/height using absolute difference.

Integer overflow when calculating area or sum of areas

How to Handle:

Use a larger data type (e.g., long) for intermediate calculations to prevent overflow issues.

Rectangles with very large coordinates that could lead to overflow

How to Handle:

Ensure all coordinate calculations use long data types to mitigate risk of integer overflow during area calculations.

Two rectangles are identical

How to Handle:

The intersection area is equal to the area of either rectangle.

One rectangle is completely contained within the other

How to Handle:

Intersection area is the area of the smaller rectangle.

Rectangles that do not overlap at all

How to Handle:

The intersection area is zero in this case.

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 represented by integers or floating-point numbers?
Can the coordinates be negative, zero, or exceed the maximum integer value?
Is it guaranteed that the input coordinates represent valid rectangles (i.e., x1 < x2 and y1 < y2)?
If the rectangles do not overlap, should I return 0?
Should I consider the area of the intersection of the rectangles, or the total area covered by the rectangles?

Brute Force Solution

Approach

To find the total area covered by two rectangles, the brute force approach directly checks every single point in a large enough space. We determine if each point is inside either of the rectangles.

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

First, find the smallest and largest x and y coordinates among the corners of both rectangles. This will define a box large enough to contain both rectangles.
Imagine a grid covering this box. Check each point in this grid, one by one.
For each point, determine if it is inside the first rectangle.
If the point is not inside the first rectangle, check if it is inside the second rectangle.
If the point is inside either the first or second rectangle, count it as part of the total area.
After checking all points in the grid, the total count represents the approximate total area covered by the rectangles.

Code Implementation

def rectangle_area(rectangle_one, rectangle_two):
    x_one_rectangle_one, y_one_rectangle_one, x_two_rectangle_one, y_two_rectangle_one = rectangle_one
    x_one_rectangle_two, y_one_rectangle_two, x_two_rectangle_two, y_two_rectangle_two = rectangle_two

    # Find the bounds of a box containing both rectangles
    min_x = min(x_one_rectangle_one, x_one_rectangle_two, x_two_rectangle_one, x_two_rectangle_two)
    min_y = min(y_one_rectangle_one, y_one_rectangle_two, y_two_rectangle_one, y_two_rectangle_two)
    max_x = max(x_one_rectangle_one, x_one_rectangle_two, x_two_rectangle_one, x_two_rectangle_two)
    max_y = max(y_one_rectangle_one, y_one_rectangle_two, y_two_rectangle_one, y_two_rectangle_two)

    total_area = 0
    # Iterate over all possible points within the bounding box.
    for x_coordinate in range(min_x, max_x + 1):
        for y_coordinate in range(min_y, max_y + 1):

            # Check if the current point is inside rectangle one.
            if (x_one_rectangle_one <= x_coordinate <= x_two_rectangle_one) and \
               (y_one_rectangle_one <= y_coordinate <= y_two_rectangle_one):
                total_area += 1
            else:

                # Check if the current point is inside rectangle two.
                if (x_one_rectangle_two <= x_coordinate <= x_two_rectangle_two) and \
                   (y_one_rectangle_two <= y_coordinate <= y_two_rectangle_two):
                    total_area += 1

    return total_area

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Calculate the area of the first rectangle.
Calculate the area of the second rectangle.
Determine if the two rectangles overlap. This involves checking if they intersect horizontally and vertically.
If they don't overlap, the total area is just the sum of the two individual areas. You're done!
If they do overlap, calculate the area of the overlapping region.
To get the total area covered, add the areas of the two rectangles and then subtract the area of the overlap. This avoids counting the overlapping region twice.

Code Implementation

def calculate_total_area(
    rectangle_one_bottom_left_x,
    rectangle_one_bottom_left_y,
    rectangle_one_top_right_x,
    rectangle_one_top_right_y,
    rectangle_two_bottom_left_x,
    rectangle_two_bottom_left_y,
    rectangle_two_top_right_x,
    rectangle_two_top_right_y
):
    rectangle_one_area = (
        rectangle_one_top_right_x - rectangle_one_bottom_left_x
    ) * (rectangle_one_top_right_y - rectangle_one_bottom_left_y)
    rectangle_two_area = (
        rectangle_two_top_right_x - rectangle_two_bottom_left_x
    ) * (rectangle_two_top_right_y - rectangle_two_bottom_left_y)

    # Determine the overlap region boundaries
    overlap_left_x = max(
        rectangle_one_bottom_left_x, rectangle_two_bottom_left_x
    )
    overlap_right_x = min(
        rectangle_one_top_right_x, rectangle_two_top_right_x
    )
    overlap_bottom_y = max(
        rectangle_one_bottom_left_y, rectangle_two_bottom_left_y
    )
    overlap_top_y = min(
        rectangle_one_top_right_y, rectangle_two_top_right_y
    )

    # If no overlap, return sum of individual areas
    if overlap_left_x >= overlap_right_x or overlap_bottom_y >= overlap_top_y:
        return rectangle_one_area + rectangle_two_area

    # We have overlap, calculate area of overlap

    overlap_area = (
        overlap_right_x - overlap_left_x
    ) * (overlap_top_y - overlap_bottom_y)

    # Avoid double counting by subtracting overlap
    return rectangle_one_area + rectangle_two_area - overlap_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input rectangles	Throw an IllegalArgumentException or return 0, based on the preferred error handling strategy and problem statement requirements.
Rectangles with zero width or height	Treat these as having an area of zero and handle calculations appropriately without causing errors.
Rectangles with negative coordinates	The problem description should clarify whether negative coordinates are allowed; If allowed, properly compute width/height using absolute difference.
Integer overflow when calculating area or sum of areas	Use a larger data type (e.g., long) for intermediate calculations to prevent overflow issues.
Rectangles with very large coordinates that could lead to overflow	Ensure all coordinate calculations use long data types to mitigate risk of integer overflow during area calculations.
Two rectangles are identical	The intersection area is equal to the area of either rectangle.
One rectangle is completely contained within the other	Intersection area is the area of the smaller rectangle.
Rectangles that do not overlap at all	The intersection area is zero in this case.

Null or undefined input rectangles

How to Handle:

Throw an IllegalArgumentException or return 0, based on the preferred error handling strategy and problem statement requirements.

Rectangles with zero width or height

How to Handle:

Treat these as having an area of zero and handle calculations appropriately without causing errors.

Rectangles with negative coordinates

How to Handle:

The problem description should clarify whether negative coordinates are allowed; If allowed, properly compute width/height using absolute difference.

Integer overflow when calculating area or sum of areas

How to Handle:

Use a larger data type (e.g., long) for intermediate calculations to prevent overflow issues.

Rectangles with very large coordinates that could lead to overflow

How to Handle:

Ensure all coordinate calculations use long data types to mitigate risk of integer overflow during area calculations.

Two rectangles are identical

How to Handle:

The intersection area is equal to the area of either rectangle.

One rectangle is completely contained within the other

How to Handle:

Intersection area is the area of the smaller rectangle.

Rectangles that do not overlap at all

How to Handle:

The intersection area is zero in this case.

0/1114 Microsoft questions completed

0/1114 completed