Rectangle Area
You are given a list of rectangles where each rectangle is represented by an array of four integers (i.e. Rectangle[i]=[x1, y1, x2, y2], where x1, y1 represents the bottom left point of the rectangle and x2.y2 represents the top right point of the rectangle, you have to find the total area covered by all the rectangles in the plane.

Example :

Rectangles = [[0, 0, 2, 2], [1, 0, 2, 3],[1, 0, 3, 1]], For the given three rectangles, you can observe that the first rectangle occupies an area of 4 units and the second rectangle has an area of 3 units, but we have to keep one thing also in mind that they have an area of 3 units common overlapping among them, so we cannot include it again, so the final area which comes out for all the rectangles is 6 units. Total Area = 6 units

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. The first line of each test case contains an integer N representing the size of the Array of rectangles. The next N lines consist of 4 integers representing the bottom left and top right coordinate points of each rectangle.

Output Format :

For each test case, return the area of all the rectangles. To avoid any overflows, return the answer Modulo 10^9+7. You do not need to take input or print anything. This already has been taken care of. Just implement the function.

Constraints :

1

Question

Rectangle Area

You are given a list of rectangles where each rectangle is represented by an array of four integers (i.e. Rectangle[i]=[x1, y1, x2, y2], where x1, y1 represents the bottom left point of the rectangle and x2.y2 represents the top right point of the rectangle, you have to find the total area covered by all the rectangles in the plane.

Example :

Rectangles = [[0, 0, 2, 2], [1, 0, 2, 3],[1, 0, 3, 1]], 

For the given three rectangles, you can observe that the first rectangle occupies an area of 4 units and the second rectangle has an area of 3 units, but we have to keep one thing also in mind that they have an area of 3 units common overlapping among them, so we cannot include it again, so the final area which comes out for all the rectangles is 6 units.

Total Area = 6 units

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer N representing the size of the Array of rectangles.

The next N lines consist of 4 integers representing the bottom left and top right coordinate points of each rectangle.

Output Format :

For each test case, return the area of all the rectangles. To avoid any overflows, return the answer Modulo 10^9+7.

You do not need to take input or print anything. This already has been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N <=200
0 <= x1, y1, x2 , y2 <= 10^9 where x1.y1 is the bottom left coordinate of rectangle and x2,y2 is top right corner of rectangle.

Time Limit  1 second.

Accepted Answer

Coordinate Compression

As we can have only 200 distinct rectangles with us so we don’t need to worry about point constraint, we can use the coordinate compression technique to map these points all The x-axis points and y-axis points as well.
Now these mapped coordinates can be used to form our grid. we can make a grid grid[x][y] = True for rx1 <= x < rx2 and ry1 <= y < ry2. Where rx1 , rx2, ry1, ry2 correspond to compressed coordinates.
Afterwards, each grid[rx][ry] represents the area (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), where if x got remapped to rx, then imapx(rx) = x ("inverse-map-x of remapped-x equals x"), and similarly for imapy.

Space Complexity: O(n^2)Explanation:

O(N^2) where N is the number of rectangles

For making our grid after compressing points it accounts for 2d array which takes O(N^2) Space.

Time Complexity: O(n^3)Explanation:

O(N^3) where N is the number of rectangles.

For filling the grid we have to iterate over all rectangles and another two nested loops going over all rectangular x points and y points which totally accounts for O(N^3)

Python (3.5)

'''
    Time complexity: O(N^3)
    Space complexity: O(N^2)

    where N is the number of rectangles
'''

def rectangleArea(n, rec):
    
    xValue = set()
    yValue = set()

    for i in range(n):
        xValue.add(rec[i][0])
        xValue.add(rec[i][2])
        yValue.add(rec[i][1])
        yValue.add(rec[i][3])

    imapx = []

    for i in xValue:
        imapx.append(i)

    imapy = []

    for i in yValue:
        imapy.append(i)

    imapx.sort()
    imapy.sort()

    mapx = dict()
    mapy = dict()

    for i in range(len(imapx)):
        mapx[imapx[i]] = i

    for i in range(len(imapy)):
        mapy[imapy[i]] = i

    grid = [[False]*len(mapy) for i in range(len(mapx))]

    for i in range(n):
        for x in range(mapx[rec[i][0]], mapx[rec[i][2]]):
            for y in range(mapy[rec[i][1]], mapy[rec[i][3]]):
                grid[x][y] = True

    ans = 0

    for x in range(len(grid)):
        for y in range(len(grid[i])):
            if grid[x][y]:
                ans += (imapx[x + 1] - imapx[x])*(imapy[y + 1] - imapy[y])

    ans %= 1000000007

    return ans

C++ (g++ 5.4)

/*
    Time complexity: O(N^3)
    Space complexity: O(N^2)

    where N is the number of rectangles

*/

#include 
#include 

int rectangleArea(int N, vector> &rectangles)
{
    
    unordered_set xValue;
    unordered_set yValue;
    for (vector rec : rectangles)
    {
        xValue.insert(rec[0]);
        xValue.insert(rec[2]);
        yValue.insert(rec[1]);
        yValue.insert(rec[3]);
    }

    vector imapx;
    for(auto it : xValue)
    {
        imapx.push_back(it);
    }

    vector imapy;
    for(auto it : yValue)
    {
        imapy.push_back(it);
    }


    sort(imapx.begin(), imapx.end());
    sort(imapy.begin(), imapy.end());

    unordered_map mapx;
    unordered_map mapy;

    for (int i = 0; i < imapx.size(); ++i)
    {
        mapx[imapx[i]] = i;
    }

    for (int i = 0; i < imapy.size(); ++i)
    {
        mapy[imapy[i]] = i;
    }

    vector> grid(mapx.size(),vector(mapy.size(),0));

    for (vector rec : rectangles)
    {
        for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
        {
            for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
            {
                grid[x][y] = true;
            }
        }
    }

    long long int ans = 0;

    for (int x = 0; x < grid.size(); ++x)
    {
        for (int y = 0; y < grid[0].size(); ++y)
        {
            if (grid[x][y])
            {
                ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);
            }
        }
    }

    ans %= 1000000007;
    return (int)ans;

}

Java (SE 1.8)

/*

    Time complexity: O(N^3)

    Space complexity: O(N^2)



    where N is the number of rectangles



*/



import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;



public class Solution {

    public static int rectangleArea(int n, int[][] rectangles) {



        HashSet xValue = new HashSet<>();



        HashSet yValue = new HashSet<>();



        for (int[] rec : rectangles) {

            xValue.add(rec[0]);

            xValue.add(rec[2]);

            yValue.add(rec[1]);

            yValue.add(rec[3]);

        }



        ArrayList imapx = new ArrayList<>();

        for (Integer it : xValue) {

            imapx.add(it);

        }



        ArrayList imapy = new ArrayList<>();



        for (Integer it : yValue) {

            imapy.add(it);

        }



        Collections.sort(imapx);

        Collections.sort(imapy);



        HashMap mapx = new HashMap<>();

        HashMap mapy = new HashMap<>();



        for (int i = 0; i < imapx.size(); ++i) {

            mapx.put(imapx.get(i), i);

        }



        for (int i = 0; i < imapy.size(); ++i) {

            mapy.put(imapy.get(i), i);

        }



        boolean[][] grid = new boolean[mapx.size()][mapy.size()];



        for (int[] rec : rectangles) {

            for (int x = mapx.get(rec[0]); x < mapx.get(rec[2]); ++x) {

                for (int y = mapy.get(rec[1]); y < mapy.get(rec[3]); ++y) {

                    grid[x][y] = true;

                }

            }

        }



        long ans = 0;



        for (int x = 0; x < grid.length; ++x) {

            for (int y = 0; y < grid[0].length; ++y) {

                if (grid[x][y]) {

                    ans += (long) (imapx.get(x + 1) - imapx.get(x)) * (imapy.get(y + 1) - imapy.get(y));

                }

            }

        }



        ans %= 1000000007;

        return (int) ans;

    }

}

Accepted Answer

Using segment trees

Make a segment tree that supports the following operations:
incrementing a range by 1
decrementing a range by 1
and the query is: how many non zero elements are active in the array,(that means how many y coordinates are active at this moment)
so for each event at coordinate x2 and the previous event is x1
add (x2-x1) * tree.query() to your union area
then update the tree according to this event

Space Complexity: O(n)Explanation:

O(N) where N is the number of rectangles.

It takes an Array of size 4*N to construct a Segment Tree recursively. So Space complexity is O(N).

Time Complexity: O(nlogn)Explanation:

O(N log(N)), where N is the number of rectangles.

Add x1,x2 and Remove x1,x2 query for a segment tree in this problem takes log N in segment Tree and For N rectangles we have to do these queries so the time complexity boils down to O(NlogN)