Perfect Rectangle

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
17 upvotes
Asked in companies
AppleOracleSamsung

Problem statement

You are given N rectangles whose sides are aligned with the x-axis and the y-axis. Each rectangle is represented by 4 integers [ a, b, c ,d ]. Here, (a, b) are x and y coordinates of the bottom left corner, and (c, d) are x and y coordinates of the top right corner.

You need to find if they all together form a rectangular region cover.

For Example : 
If the given rectangle is [1, 1, 3, 2]. It means the bottom left corner is at [1, 1] and the top right corner is at [3, 2]. Hence, the top left corner is at [1, 2] and the bottom right corner is at [3, 1].

For the given figure is for N = 4, rectangle[0] = [1, 1, 4, 5], rectangle[1] = [4, 1, 6, 2], rectangle[3] = [4, 2, 6, 5], rectangle[4] = [6, 1, 8, 5].

alt text

As they all form a big rectangle [1, 1, 8, 5]. So, the answer is 1.

Note :

Two integers are used to represent Point - x and y coordinates.

Two points are used to represent a Rectangle - Bottom left corner and top right corner.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains integer ‘N’, which denotes the number of rectangles.

The next N lines contain four integers, a, b, c, and d which denote x coordinate of the bottom left corner, y coordinate of the bottom left corner, x coordinate of the top right corner, y coordinate of the top right corner of the rectangle
Output Format : 
For each test case, print 1 if it is all the given rectangles form a rectangular region cover otherwise print 0.

Print the output of each test case in a new line.
Constraints : 
1<= T <= 50
1 <= N <= 20000
0 <=  'rectangle[i][j]' <= 20000
rectangle[i].size = 4

Where 'rectangle[i][j]'(0 <= j < 4)  denote the coordinates of the corners of the rectangle

Time Limit: 1 sec
Sample Input 1 :
2
3
3 1 4 4
1 1 3 3
1 3 3 4
3
3 1 4 4
1 1 3 3
1 3 4 4
Sample Output 1 :
1
0
Explanation For Sample Input 1 :
In the first test case, three rectangles are given - the first rectangle starts at (3, 1) and ends at (4, 4), the second rectangle starts at (1, 1) and ends at (3, 3), and the third rectangle starts at (1, 3) and ends at (3, 4). When these rectangles are combined, a big rectangle is formed starting at (1, 1) and it ends at (4, 4). So, the answer is 1.

In the second test case, three rectangles are given - the first rectangle starts at (3, 1) and ends at (4, 4), the second rectangle starts at (1, 1) and ends at (3, 3), and the third rectangle starts at (1, 3) and ends at (4, 4). When these rectangles are combined, a big rectangle is formed starting at (1, 1) and ends at (4, 4) but the first and the third rectangles overlap into each other from (3, 3) to (4, 4). So, the answer is 0.
Sample Input 2 :
2
4
1 3 2 4
3 1 4 2
3 2 4 4
1 1 2 3
5
1 3 2 4
3 1 4 2
3 2 4 4
1 1 2 3
2 1 3 4
Sample Output 2 :
0
1
Hint

 If the sum of areas of all rectangles is equal to the bigger rectangle, then Can we form the rectangle? Is there any other corner case?

Approaches (1)
Greedy

The idea is to find the bottom left corner and top right corner of the big rectangle which encloses all the small rectangles. Then, add the areas of all the given rectangles. If areas are equal, it means it means there are no spaces or overlapping between the rectangles. There is a corner case, it may happen that area of a bigger rectangle is equal to areas of smaller rectangles but the number of corners may not be equal to 4. For example, N = 3, rectangle[0] = [0, 0, 1, 1], rectangle[1] = [0, 0, 1, 1]  and rectangle [2] = [2, 0, 3, 1]. Here, the bigger rectangle is [0, 0, 3, 1] and the sum of areas of all smaller rectangles is equal to the area of the bigger rectangle but here two rectangle[0] and rectangle[1] overlap and there is no rectangle in the region [1, 0, 2, 1]. For that, if we observe, we will get to know that all the corners of the big rectangle will appear once but all the corners which are not a corner of the big rectangle will appear twice. So, we will store the corners in a set. Whenever we encounter a corner that is already present in the set then erase the corner. Otherwise, insert the corner in the set. Then calculate the area of the bigger rectangle using the corners in the set. If the area of the bigger rectangle is equal to the sum of areas of all the smaller rectangles, it means it is possible to form a bigger rectangle by combining all the smaller rectangles.

At last, if there are four corners remaining in the set. Then, it forms a rectangle.

The steps are as follows:

  • Initialize totalArea = 0, which stores the sum of the area of all the given rectangles.
  • Initialize a set ‘corners’, which stores the corners of the big rectangle.
  • Iterate over the rectangles:
    • Find out all the four corners of the rectangle from two given corners(bottom left and top right).
    • Now, find the area of the current rectangle and add it into totalArea.
    • Now check if any of the points exist in the given set or not.
    • If any of the points exist in the given set, then erase it from the set as it appeared twice. Otherwise, insert it into the set.
  • If the size of the set ‘corners’ doesn’t contain four corners or the area of the bigger rectangle formed by the four corners present in the set is not equal to the sum of areas of all the rectangles, then return false.
  • Initialize desiredArea equals to the area of the bigger rectangle by using the four corners present in the set ‘corners’ and mathematical formula area = length * breadth.
  • If desiredArea is not equal to the totalArea, return false.
  • Otherwise, return true.
Time Complexity

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

 

We are iterating over the rectangles which is O(N) and inserting the corners into a Set which is O(log(N)). Hence, the overall time complexity is O(N*log(N)).

Space Complexity

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

 

We are using a set to store the corners which can grow up to the size of a given number of rectangles. Hence, the overall space complexity is O(N). 

Code Solution
(100% EXP penalty)
Perfect Rectangle
Full screen
Console