LeetCode 223 Rectangle Area in Java

In this post we will solve LeetCode 223 Rectangle Area in Java.

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).

Constraints:

o -10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4

Related Topics:

o Math
o Geometry

We are given the coordinates of two rectilinear rectangles in a 2D plane and are asked to return the total area covered by the two rectangles.

As previously mentioned in this post, we will solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Unless you have a preference like I do, my suggestion for you is to solve the problem using the online IDE provided by LeetCode.

Due to the fact that I will be using a Windows computer at home, I will also need to develop some test code to collect the input data, call the function of interest, and display results. Please note that the test scaffold IS NOT PART OF THE SOLUTION!

    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        
    }

The signature for the function of interest is somewhat complicated to look at. That said; it provides the bottom left and top right of the two rectangles used as arguments.

-3,0,3,4
0,-1,9,2
main <<< r1: [-3, 0, 3, 4]
main <<< r2: [0, -1, 9, 2]
<<< area1: 24
<<< area2: 27
<<< overlap: 6
main <<< computeArea0: 45
main <<<  computeArea: 45


-2,-2,2,2
-2,-2,2,2
main <<< r1: [-2, -2, 2, 2]
main <<< r2: [-2, -2, 2, 2]
<<< area1: 16
<<< area2: 16
<<< overlap: 16
main <<< computeArea0: 16
main <<<  computeArea: 16


-2,-2,2,2
-1,-1,1,1
main <<< r1: [-2, -2, 2, 2]
main <<< r2: [-1, -1, 1, 1]
<<< area1: 16
<<< area2: 4
<<< rectangles overlap
<<< overlap: 4
main <<< computeArea: 16


0,0,0,0
-1,-1,1,1
main <<< r1: [0, 0, 0, 0]
main <<< r2: [-1, -1, 1, 1]
<<< area1: 0
<<< area2: 4
<<< rectangles overlap
<<< overlap: 0
main <<< computeArea: 4


-2,-2,2,2
1,1,3,3
main <<< r1: [-2, -2, 2, 2]
main <<< r2: [1, 1, 3, 3]
<<< area1: 16
<<< area2: 4
<<< rectangles overlap
<<< overlap: 1
main <<< computeArea: 19

Test cases are separated by two blank lines.

The first two lines in each test case provide the coordinates for the two rectangles.

The test code appears to read the input lines, populate two int[] arrays and display them for us to verify that all is well before calling the function of interest. As a matter of fact we have two implementations of the function of interest.

The few lines that follow until the returned value is displayed are generated by the first function of interest. They are there to help us follow to some degree the correctness of the implementation of the function of interest.

    /**
     * Test scaffold.
     * !!! NOT PART OF SOLUTION !!!
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read coordinates for first rectangle ****
        int[] r1 = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** read coordinates for second rectangle ****
        int[] r2 = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< r1: " + Arrays.toString(r1));
        System.out.println("main <<< r2: " + Arrays.toString(r2));

        // **** call function of interest and display result ****
        System.out.println("main <<< computeArea0: " + computeArea0(r1[0], r1[1], r1[2], r1[3], r2[0], r2[1], r2[2], r2[3]));

        // **** call function of interest and display result ****
        System.out.println("main <<<  computeArea: " + computeArea(r1[0], r1[1], r1[2], r1[3], r2[0], r2[1], r2[2], r2[3]));
    }

The test scaffold seems to follow the description of the test cases.

During the degeneration of this post I added a third implementation. All three implementations are based on the same code with some minimum changes in order to compare the runtime and space performance. The third implementation did not make it to the post but you can find it in the associated GitHub repository.

One way to approach this problem is to split it into three parts. First compute the area of the first rectangle. Second, to compute the area of the second rectangle. Third we need to determine how much the rectangles overlap and delete from the sum of the two areas the overlap.

Besides some logical considerations the most important and possibly the hardest part is to compute the overlap area.

I first tried to compute the area using my own code. It worked with the test cases provided by LeetCode but failed in some of the abundant test cases during submission.

Since determining the overlap area seems like a common task, I did a search on the web and found a few items of interest. I decided to read the following two:

Total area of two overlapping rectangles
https://www.geeksforgeeks.org/total-area-two-overlapping-rectangles/

total area of intersecting rectangles
https://stackoverflow.com/questions/4549544/total-area-of-intersecting-rectangles

You might find both sites of interest for searches. As a matter of fact I typically put words for the search and append `GeeksForGeeks` or `stackoverflow`.

    /**
     * Given the coordinates of two rectilinear rectangles in a 2D plane,
     * return the total area covered by the two rectangles.
	 * 
	 * Runtime: O(1) - Space: O(1)
	 *
     * Runtime: 2 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 38.1 MB, less than 92.38% of Java online submissions.
     * 
     * 3080 / 3080 test cases passed.
     * Status: Accepted
     * Runtime: 2 ms
     * Memory Usage: 38.6 MB
     */
    static public int computeArea0(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        
        // **** initialization ****
        int area1   = Math.abs(ax2 - ax1) * Math.abs(ay2 - ay1);
        int area2   = Math.abs(bx2 - bx1) * Math.abs(by2 - by1);
        int overlap = 0;

        // ???? ????
        System.out.println("<<< area1: " + area1);
        System.out.println("<<< area2: " + area2);

        // **** check if rectangles are one above the other (do NOT overlap) ****
        if (ay1 >= by2 || by1 >= ay2)
            return area1 + area2;

        // ***** check if rectangles are side by side (do NOT overlap) ****
        if (ax2 <= bx1 || bx2 <= ax1)
            return area1 + area2;

        // **** compute overlap ****
        overlap =   Math.max(Math.min(ax2, bx2) - Math.max(ax1, bx1), 0) *
                    Math.max(Math.min(ay2, by2) - Math.max(ay1, by1), 0);

        // ???? ????
        System.out.println("<<< overlap: " + overlap);

        // **** return area ****
        return area1 + area2 - overlap;
    }

We start this implementation of the function of interest with an initialization section in which we compute the individual areas of both rectangles and define the `overlap` area which we need to compute.

It is important to determine if the rectangles overlap or not. In the first check we determine if one rectangle is above the other. In the following check we determine if one rectangle is left to the other. In both cases the rectangles do not overlap and the result is the sum of the two areas.

Now we need to compute the overlap area of the two rectangles.

Finally we return the sum of the areas minus the overlap.

Please take a look at the comments section of this function. Perhaps we could do better. If you do so, please let me know. I will update this post with a mention to your contribution.

    /**
     * Given the coordinates of two rectilinear rectangles in a 2D plane,
     * return the total area covered by the two rectangles.
     * 
	 * Runtime: O(1) - Space: O(1)
	 *
     * Runtime: 2 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 38.1 MB, less than 84.60% of Java online submissions.
     * 
     * 3080 / 3080 test cases passed.
     * Status: Accepted
     * Runtime: 2 ms
     * Memory Usage: 38.1 MB
     */
    static public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        
        // **** initialization ****        
        int area1   = (ax2 - ax1) * (ay2 - ay1);
        int area2   = (bx2 - bx1) * (by2 - by1);
        
        // **** rectangles do not overlap ****
        if ((ay1 >= by2 || by1 >= ay2) ||
            (ax2 <= bx1 || bx2 <= ax1))
            return area1 + area2;

        // **** rectangles overlap ****
        return area1 + area2 - 
                    Math.max(Math.min(ax2, bx2) - Math.max(ax1, bx1), 0) *
                    Math.max(Math.min(ay2, by2) - Math.max(ay1, by1), 0);
    }

This is another implementation of the function of interest. Note that it follows the same set of steps. The performance is shown in the comments section. It does not seem like much of an improvement. Perhaps this is due to the fact that there are thousands of test cases and the execution time might be somewhat related to it.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named RectangleArea.

Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.