Saturday, October 8, 2022
HomeWordPress DevelopmentLeetCode - Rectangle Space - DEV Neighborhood 👩‍💻👨‍💻

LeetCode – Rectangle Space – DEV Neighborhood 👩‍💻👨‍💻




Downside assertion

Given the coordinates of two rectilinear rectangles in a 2D airplane, return the entire space coated by the 2 rectangles.

The primary rectangle is outlined by its bottom-left nook (ax1, ay1) and its top-right nook (ax2, ay2).

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

Downside assertion taken from: https://leetcode.com/issues/rectangle-area

Instance 1:

Container

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

Exit fullscreen mode

Instance 2:

Enter: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16
Enter fullscreen mode

Exit fullscreen mode

Constraints:

- -10^4 <= ax1 <= ax2 <= 10^4
- -10^4 <= ay1 <= ay2 <= 10^4
- -10^4 <= bx1 <= bx2 <= 10^4
- -10^4 <= by1 <= by2 <= 10^4
Enter fullscreen mode

Exit fullscreen mode



Clarification

The answer to this downside is simple. We have to use the college mathematical idea to get the world of two rectangles.

space = Space of rectangle 1 + Space of rectangle 2 - Space of intersecting portion
Enter fullscreen mode

Exit fullscreen mode

To calculate the world of intersecting half, we have to compute under 4 coordinates:

maxCommonX = max(ax1, bx1)
maxCommonY = max(ay1, by1)

minCommonX = min(ax2, bx2)
minCommonY = min(ay2, by2)

commonArea = (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
Enter fullscreen mode

Exit fullscreen mode

Let’s verify the algorithm.

// compute the world of rectangles utilizing L * H
- set area1 = (ax2 - ax1) * (ay2 - ay1)
  set area2 = (bx2 - by1) * (by2 - by1)

// if the rectangles don't intersect, return area1 + area2
- if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1
  - return area1 + area2

- set maxCommonX = max(ax1, bx1)
  set maxCommonY = max(ay1, by1)

- set minCommonX = min(ax2, bx2)
  set minCommonY = min(ay2, by2)

- return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY);
Enter fullscreen mode

Exit fullscreen mode

Let’s verify our algorithm in C++, Golang, and Javascript.



C++ answer

class Resolution {
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(bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1) {
            return area1 + area2;
        }

        int maxCommonX = max(ax1, bx1);
        int maxCommonY = max(ay1, by1);

        int minCommonX = min(ax2, bx2);
        int minCommonY = min(ay2, by2);

        return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY);
    }
};
Enter fullscreen mode

Exit fullscreen mode



Golang answer

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    area1 := (ax2 - ax1) * (ay2 - ay1)
    area2 := (bx2 - bx1) * (by2 - by1)

    if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1 {
        return area1 + area2;
    }

    maxCommonX := max(ax1, bx1)
    maxCommonY := max(ay1, by1)

    minCommonX := min(ax2, bx2)
    minCommonY := min(ay2, by2)

    return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}
Enter fullscreen mode

Exit fullscreen mode



Javascript answer

var computeArea = operate(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
    let area1 = (ax2 - ax1) * (ay2 - ay1);
    let area2 = (bx2 - bx1) * (by2 - by1);

    if(bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1) {
       return area1 + area2;
    }

    let maxCommonX = Math.max(ax1, bx1);
    let maxCommonY = Math.max(ay1, by1);

    let minCommonX = Math.min(ax2, bx2);
    let minCommonY = Math.min(ay2, by2);

    return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY) ;
};
Enter fullscreen mode

Exit fullscreen mode

Let’s dry-run our algorithm for Instance 1.

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

Step 1: area1 = (ax2 - ax1) * (ay2 - ay1)
              = (3 - -3) * (4 - 0)
              = 6 * 4
              = 24

        area2 = (bx2 - bx1) * (by2 - by1)
              = (9 - 0) * (2 - -1)
              = 9 * 3
              = 27

Step 2: if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1
           0 >= 3 || 9 <= -3 || -1 >= 4 || 2 <= 0
           false

Step 3: maxCommonX = max(ax1, bx1)
                   = max(-3, 0)
                   = 0

        maxCommonY = max(ay1, by1)
                   = max(0, -1)
                   = 0

Step 4: minCommonX = min(ax2, bx2)
                   = min(3, 9)
                   = 3

        minCommonY = min(ay2, by2)
                   = min(4, 2)
                   = 2

Step 5: return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
               24 + 27 - (3 - 0) * (2 - 0)
               51 - 3*2
               51 - 6
               45

We return the reply as 45.
Enter fullscreen mode

Exit fullscreen mode

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments