Golang solution (35ms) - Beats 100% of 'Go' submissions


  • 1

    Summary

    To get the "total area covered by the two rectangles" we need to calculate three things.

    1. Area of rectangle 1 area1
    2. Area of rectangle 2 area2
    3. Area of the overlap/intersection xOverlap * yOverlap

    (1) and (2) are straight forward. (3) is where the core of the problem lies.

    Computing the Intersection (Overlapping Area)

    In order to compute the area of intersection, we further break the problem down into two components.

    1. Do they overlap horizontally along the x-axis?
    2. Do they overlap vertically along the y-axis?

    If both of these statements are true then we have an overlap. Both of these can be verified by implementing a function which checks whether if two parallel lines L1 and L2 overlap or not. There are four different cases as follows. Note: Lines are shown as (start, end)

    1. L1 and L2 overlap partially. e.g. L1 = (2, 6), L2 = (3, 8). Overlap = (3, 6)
    2. L1 encloses L2. e.g. L1 = (2, 8), L2 = (4, 6). Overlap = (4, 6)
    3. L1 and L2 touch at a single point. e.g L1 = (2, 5), L2 = (5, 8). Overlap = (5, 5)
    4. L1 and L2 do NOT overlap at all. e.g. L1 = (1, 4), L2 = (5, 9)

    Between L1 and L2 we will define higherStartPoint as the starting point of either L1 and L2 with the higher value. lowerEndPoint is the ending point of either L1 and L2 with the lower value. If you look at the examples given above, you will realize that for L1 and L2 to overlap [#1 and #2 above] lowerEndPoint should be greater than higherStartPoint. #3 non-overlapping, because the length of the overlapped line is zero.

    After getting the overlapping line on both the x-axis and y-axis we finally get the the area of the intersecting rectangle.

    The total overall area is then calculated by the following:
    Area of rectangle 1 + Area of rectangle 2 - Area of intersecting rectangle

    func computeArea(A, B, C, D, E, F, G, H int) int {
        area1 := (C - A) * (D - B)
        area2 := (G - E) * (H - F)
        xOverlap := overlap(A, C, E, G)
        yOverlap := overlap(B, D, F, H)
        return area1 + area2 - (xOverlap * yOverlap)
    }
    
    func overlap(s1, e1, s2, e2 int) int {
        higherStartPoint := max(s1, s2)
        lowerEndPoint := min(e1, e2)
        if lowerEndPoint <= higherStartPoint {
            return 0
        }
        return lowerEndPoint - higherStartPoint
    }
    
    func max(x, y int) int {if x > y { return x }; return y}
    func min(x, y int) int {if x < y { return x }; return y}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.