223. Rectangle Area

Hello, reader 👋🏽 ! Welcome to day 47 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 223. Rectangle Area.

🤔 Problem Statement

• Given the coordinates of two rectanges, return the total area occupied by these rectangles.
• The coordinates given for each rectangle are x1, x2, y1, and y2 for bottom left, bottom right, top left and top right respectively.
• E.g.:
  • ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 => 45
  • ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2 => 16

💬 Thought Process - (Sum of Area - Overlapping Area)

• This problem would have been straightforward if the two rectangles never overlapped because the total area would have been the sum of area of both rectangles given by: ((ax2 - ax1) * (ay2 - ay1)) + ((bx2 - bx1) * (by2 - by1)).
• But since the rectangles can overlap, if we simply return the sum of areas of both the rectangles, we will be taking into account the overlapped area twice.
• Hence, the forumla boils down to ((ax2 - ax1) * (ay2 - ay1)) + ((bx2 - bx1) * (by2 - by1)) - overlappedArea.

• Now the next question is how do we find the overlapping area?

  • By intuition the rectangles are not overlapping when either ax2 <= bx1 or ax1 >= bx2 or ay1 >= by2 or by2 <= by1.
  • The image below represents the 4 scenarios when rectangles don't overlap.

• Now to find the overlapping area in an overlapping scenario, refer to the image below:

• Now look at the coordinates of the orange and purple rectangles. On careful observation, we can figure out that the maximum of ax1 and bx1 are the coordinates that mark the left x coordinate - x1.
• Similarly the maximum of ay1 and by1 mark the bottom y coordinate- y1.
• For the right x coordinate, it's the minimum value of ax2 and bx2 that mark the end x coordinate - x2.
• And similarly, for the top y coordinate, the minimum of ay2 and by2 can be considered - y2.
• Once the 4 points have been decided: x1 = max(ax1, bx1), x2 = min(ax2, bx2), y1= max(ay1, by1), and y2 = min(ay2, by2), We can easily use them to calculate the overlapped area: (x2 - x1) * (y2 - y1).

👩🏽‍💻 Solution - (Sum of Area - Overlapping Area)

• Below is the code for the binary search approach.

  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);
  
        if(ax2 <= bx1 || ax1 >= bx2 || ay2 <= by1 || ay1 >= by2) {
            return area1 + area2;
        }
  
        int left = Math.max(ax1, bx1);
        int right = Math.min(ax2, bx2);
        int xOverlap = right - left;
  
        int bottom = Math.max(ay1, by1);
        int top = Math.min(ay2, by2);
        int yOverlap = top - bottom;
  
        int overlapArea = yOverlap * xOverlap;
  
        return area1 + area2 - overlapArea;
    }
  }
  

  Time Complexity: O(1)
    - n = the maximum number
  Space Complexity: O(1)
  

You can find the link to the GitHub repo for this question here: 223. Rectangle Area.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!