Scale Engineer

Rectangle Area

Med
#0211Time: O((ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1)) - Proportional to the areas of both rectanglesSpace: O((ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1)) - Need to store all points in the set1 company
Patterns
MathGeometry
Companies
Nvidia

Prompt

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:

Rectangle Area 
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:

  • -104 <= ax1 <= ax2 <= 104
  • -104 <= ay1 <= ay2 <= 104
  • -104 <= bx1 <= bx2 <= 104
  • -104 <= by1 <= by2 <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

Create a grid representation and count all points covered by either rectangle

Algorithm

  1. Create an empty set to store unique points
  2. For each point in the first rectangle:
    • Add point coordinates to set
  3. For each point in the second rectangle:
    • Add point coordinates to set
  4. Return size of the set

Walkthrough

In this approach, we create a grid representation of the plane and mark all points that are covered by either rectangle. We then count all marked points to get the total area.

public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {    Set<String> points = new HashSet<>();        // Add points from first rectangle    for (int x = ax1; x < ax2; x++) {        for (int y = ay1; y < ay2; y++) {            points.add(x + "," + y);        }    }        // Add points from second rectangle    for (int x = bx1; x < bx2; x++) {        for (int y = by1; y < by2; y++) {            points.add(x + "," + y);        }    }        return points.size();}

This approach is highly inefficient and would only work for small coordinate values. It also doesn't handle floating point coordinates.

Complexity

Time

O((ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1)) - Proportional to the areas of both rectangles

Space

O((ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1)) - Need to store all points in the set

Trade-offs

Pros

  • Simple to understand

  • Handles complex overlapping cases automatically

Cons

  • Extremely inefficient for large coordinates

  • Memory intensive

  • Doesn't work with floating point coordinates

  • Will fail for the given constraints due to memory limits

Solutions

public class Solution {    public int ComputeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {        int a = (ax2 - ax1) * (ay2 - ay1);        int b = (bx2 - bx1) * (by2 - by1);        int width = Math.Min(ax2, bx2) - Math.Max(ax1, bx1);        int height = Math.Min(ay2, by2) - Math.Max(ay1, by1);        return a + b - Math.Max(height, 0) * Math.Max(width, 0);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem