algoadvance

Leetcode 223. Rectangle Area

Problem Statement

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

Each rectangle is defined by its bottom-left and top-right coordinates as follows:

Clarifying Questions

  1. Are the coordinates always integers? Yes, the coordinates are given as integers.

  2. Can the rectangles overlap? Yes, the rectangles can overlap.

  3. What should be returned if there is no overlap? The sum of the areas of both rectangles should be returned if there is no overlap.

  4. Can the rectangles be degenerate (i.e., form lines or points)? Yes, but they will not contribute any positive area in such cases.

Strategy

We need to follow these steps to solve the problem:

  1. Compute the area of both rectangles independently:
    • Area of Rectangle 1: (C - A) * (D - B)
    • Area of Rectangle 2: (G - E) * (H - F)
  2. Calculate the overlap area:
    • The overlap area is determined by the overlapping horizontal and vertical ranges between the two rectangles.
    • Horizontal overlap width: max(0, min(C, G) - max(A, E))
    • Vertical overlap height: max(0, min(D, H) - max(B, F))
    • Overlap area: Overlap width * Overlap height
  3. Sum the areas of the two rectangles and subtract the overlap area to get the total area.

Code

public class RectangleArea {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        // Calculate the area of the first rectangle
        int area1 = (C - A) * (D - B);
        
        // Calculate the area of the second rectangle
        int area2 = (G - E) * (H - F);
        
        // Calculate the overlapping area
        int overlapWidth = Math.max(0, Math.min(C, G) - Math.max(A, E));
        int overlapHeight = Math.max(0, Math.min(D, H) - Math.max(B, F));
        int overlapArea = overlapWidth * overlapHeight;
        
        // Total area is the sum of the individual areas minus the overlapping part
        return area1 + area2 - overlapArea;
    }
}

Time Complexity

The time complexity of this solution is O(1) because all operations involved (min, max, and arithmetic) are performed in constant time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI