What is the time complexity of Rectangle Area?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Rectangle Area?

This problem uses Math, Geometry. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Rectangle Area?

Insight 1: The core challenge is correctly identifying and calculating the overlapping area between the two rectangles. Insight 2: To find the overlap, we need to find the intersection of the x-ranges and y-ranges of the two rectangles.

Which companies ask LeetCode 223. Rectangle Area in interviews?

This problem is frequently asked at Nvidia.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Rectangle Area - LeetCode 223 Solution

Rectangle Area - Complete Solution Guide

Rectangle Area is LeetCode problem 223, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to calculate the total area covered by two rectangles in a 2D plane. We are given the coordinates of the bottom-left and top-right corners of each rectangle. The goal is to find the combined area, taking into account any overlapping region, so we don't count it twice. Input consists of eight integers representing the x and y coordinates of the two rectangles: (ax1, ay1, ax2, ay2) and (bx1, by1, bx2, by2). The output is a single integer representing the total area.

Solution Approach

The solution calculates the area of each rectangle separately. Then, it determines the overlapping area, if any exists. The total area is computed by summing the individual areas and subtracting the overlapping area to avoid double-counting. The overlap is calculated by finding the intersection of the x and y projections of the rectangles.

Step-by-Step Algorithm

Step 1: Calculate the area of the first rectangle (area1) as (ax2 - ax1) * (ay2 - ay1).
Step 2: Calculate the area of the second rectangle (area2) as (bx2 - bx1) * (by2 - by1).
Step 3: Determine the x-coordinate of the left edge of the overlapping rectangle by taking the maximum of ax1 and bx1.
Step 4: Determine the x-coordinate of the right edge of the overlapping rectangle by taking the minimum of ax2 and bx2.
Step 5: Determine the y-coordinate of the bottom edge of the overlapping rectangle by taking the maximum of ay1 and by1.
Step 6: Determine the y-coordinate of the top edge of the overlapping rectangle by taking the minimum of ay2 and by2.
Step 7: Calculate the width of the overlapping rectangle as the difference between the right and left x-coordinates. If the width is negative (meaning no overlap in the x-dimension), set it to 0.
Step 8: Calculate the height of the overlapping rectangle as the difference between the top and bottom y-coordinates. If the height is negative (meaning no overlap in the y-dimension), set it to 0.
Step 9: Calculate the area of the overlapping rectangle as the product of its width and height.
Step 10: Return the total area as area1 + area2 - overlap_area.

Key Insights

Insight 1: The core challenge is correctly identifying and calculating the overlapping area between the two rectangles.
Insight 2: To find the overlap, we need to find the intersection of the x-ranges and y-ranges of the two rectangles.
Insight 3: We must handle the case where there is no overlap; in this case, the overlap area should be zero.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Math, Geometry.

Companies

Asked at: Nvidia.

Rectangle Area | LeetCode 223

Medium

Math Geometry

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

Solution Code

Available in:

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);

        int overlap_width = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int overlap_height = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        
        int overlap_area = overlap_width * overlap_height;

        return area1 + area2 - overlap_area;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 223: Rectangle Area - Detailed explanation and solution approaches.

Topics

Math Geometry

Companies

Nvidia

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:223

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Calculate the area of the first rectangle (area1) as (ax2 - ax1) * (ay2 - ay1).
2
Step 2: Calculate the area of the second rectangle (area2) as (bx2 - bx1) * (by2 - by1).
3
Step 3: Determine the x-coordinate of the left edge of the overlapping rectangle by taking the maximum of ax1 and bx1.
4
Step 4: Determine the x-coordinate of the right edge of the overlapping rectangle by taking the minimum of ax2 and bx2.
5
Step 5: Determine the y-coordinate of the bottom edge of the overlapping rectangle by taking the maximum of ay1 and by1.
6
Step 6: Determine the y-coordinate of the top edge of the overlapping rectangle by taking the minimum of ay2 and by2.
7
Step 7: Calculate the width of the overlapping rectangle as the difference between the right and left x-coordinates. If the width is negative (meaning no overlap in the x-dimension), set it to 0.
8
Step 8: Calculate the height of the overlapping rectangle as the difference between the top and bottom y-coordinates. If the height is negative (meaning no overlap in the y-dimension), set it to 0.
9
Step 9: Calculate the area of the overlapping rectangle as the product of its width and height.
10
Step 10: Return the total area as area1 + area2 - overlap_area.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The solution involves a fixed number of arithmetic operations and variable assignments, regardless of the input values. Therefore, the time complexity is constant, O(1). Similarly, the solution uses a fixed amount of memory to store variables, resulting in a constant space complexity of O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach (Checking for Overlap Pixel by Pixel)

Conceptually, we could iterate through all possible pixels within the bounding box of the two rectangles, keeping track of which pixels are covered. This is highly inefficient.

Time: O(W*H), where W and H are the width and height of the bounding box containing both rectangles.Space: O(1), if we only count area instead of storing pixel data. However, if we stored a grid representing the space, the space complexity would be O(W*H).

Trade-offs: This approach is extremely inefficient and impractical. It is highly discouraged due to its poor performance. Only use this if the rectangle coordinates are very small.

✨

Key Insights

1Insight 1: The core challenge is correctly identifying and calculating the overlapping area between the two rectangles.
2Insight 2: To find the overlap, we need to find the intersection of the x-ranges and y-ranges of the two rectangles.
3Insight 3: We must handle the case where there is no overlap; in this case, the overlap area should be zero.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: No overlap between the rectangles. The solution correctly handles this by ensuring that the overlap width and height are zero when there is no overlap due to the `max(0, ...)` calls.
Edge case 2: One rectangle is completely contained within the other. The solution correctly calculates the overlap area in this scenario.
Edge case 3: Rectangles are identical. The overlap area will be the area of one rectangle, which is then subtracted from the sum of the two areas (which are identical), resulting in just the area of one rectangle being counted.
Edge case 4: Large integer values approaching the maximum or minimum possible int values could lead to integer overflow. The problem constraints state values up to 10^4, so intermediate calculations (like subtraction or multiplication) might still overflow. However the problem doesn't explicitly test for this and generally interview environments don't require extreme overflow handling unless it's explicitly the focus of the question.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the rectangles do not overlap, resulting in incorrect overlap area calculations.

✗Common mistake 2: Incorrectly calculating the overlap width or height by swapping the min and max functions or by performing subtractions in the wrong order.

✗Common mistake 3: Integer overflow in intermediate calculations, especially when dealing with large coordinates. This can be mitigated by using larger integer data types if the constraints allowed it.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Collision detection in game development. Determining if two rectangular game objects are overlapping on the screen.

🏦Real-world scenario 2: UI layout management. Calculating the total area occupied by multiple rectangular UI elements on a screen or canvas.

🎮Real-world scenario 3: Geographic Information Systems (GIS). Finding the overlapping area between two rectangular regions or properties.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Rectangle Area"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether geometry techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?