Rectangle Area

Ninja

0/200

Average time to solve is 55m

Contributed by

20 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

Sample Output 1 :

6
8

Explanation :

Test Case 1

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.

Test Case 2

There is no overlapping for the two rectangles hence the area is 

4 + 4 = 8 units

Sample Input 2 :

Sample output 2 :

12
16

Hint 1

Hint 2

As Rectangle points range to 10^9 , think of using coordinate compression with brute force.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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)

Space Complexity

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.

(100% EXP penalty)

Rectangle Area

Console