# Perfect Rectangle

This page explains Java solution to problem `Perfect Rectangle` using `Set` data structure.

## Problem Statement

Given `N` axis-aligned rectangles where `N > 0`, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a `bottom-left` point and a `top-right` point. For example, a unit square is represented as `[1,1,2,2]`. (coordinate of bottom-left point is `(1, 1)` and `top-right` point is `(2, 2)`).

Example 1:

Input:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]
Output: Return true.
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

Input:
rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]
Output: Return false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

Input:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]
Output: Return false
Explanation: Because there is a gap in the top center.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class PerfectRectangle {
public boolean isRectangleCover(int[][] rectangles) {
/**
Input rectangles array should satisfy below three criteria
1. the large rectangle area should be equal to the sum of all small input rectangles
2. count of all the points should be even
3. count of of all the four corner points should be one
*/
HashSet<String> points = new HashSet<>();
int x1 = Integer.MAX_VALUE;
int y1 = Integer.MAX_VALUE;
int x2 = Integer.MIN_VALUE;
int y2 = Integer.MIN_VALUE;

int area = 0;
for(int[] rectangle: rectangles) {
x1 = Math.min(x1, rectangle[0]);
y1 = Math.min(y1, rectangle[1]);
x2 = Math.max(x2, rectangle[2]);
y2 = Math.max(y2, rectangle[3]);

String point1 = rectangle[0] +" "+ rectangle[1];
String point2 = rectangle[2] +" "+ rectangle[3];
String point3 = rectangle[0] +" "+ rectangle[3];
String point4 = rectangle[2] +" "+ rectangle[1];

if(!points.add(point1)) points.remove(point1);
if(!points.add(point2)) points.remove(point2);
if(!points.add(point3)) points.remove(point3);
if(!points.add(point4)) points.remove(point4);

area += (rectangle[3] - rectangle[1]) * (rectangle[2] - rectangle[0]);
}

String point1 = x1 +" "+ y1;
String point2 = x2 +" "+ y2;
String point3 = x1 +" "+ y2;
String point4 = x2 +" "+ y1;

if(!points.contains(point1) || !points.contains(point2) || !points.contains(point3) || !points.contains(point4) || points.size() != 4) return false;

return area == (x2 - x1) * (y2 - y1);
}
}
``````

## Time Complexity

O(N) Where
N is total number of rectangle in an input array rectangles

## Space Complexity

O(N) Where
N is total number of rectangle in an input array rectangles