While submitting this question i found that someone already made up this question in python, here is my java implementation of the Perfect-Rectangle-Challange
challenge:
Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).
Return true if all the rectangles together form an exact cover of a rectangular region.
(for more details follow the link above)
Note: my implementation requires at least Java 11
entry class Solution (given from leetcode):
/**
* https://leetcode.com/problems/perfect-rectangle/
*/
public class Solution {
//Assesment: given method within given class from leetcode - this interface may not be modified
public boolean isRectangleCover(int[][] input) {
InputProvider inputProvider = new InputProvider();
inputProvider.handle(input);
ArrayDeque<Rectangle> rectangles = inputProvider.getRectangles();
PerfectRectangleChecker perfectRectangleChecker = new PerfectRectangleChecker(inputProvider.getBounds());
return perfectRectangleChecker.check(rectangles);
}
class Point
public class Point {
public final int x;
public final int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
class Rectangle
public class Rectangle {
public final Point[] points;
public final int area;
public Rectangle(int x0, int y0, int x1, int y1) {
points = new Point[4];
points[0] = new Point(x0,y0);
points[1] = new Point(x1,y0);
points[2] = new Point(x0,y1);
points[3] = new Point(x1,y1);
area = (x1-x0)*(y1-y0);
}
public Rectangle(int[] input) {
this(input[0],input[1],input[2],input[3]);
}
}
class InputProvider
public class InputProvider {
private final ArrayDeque<Rectangle> rectangles = new ArrayDeque<>();
private int boundsX0 = Integer.MAX_VALUE;
private int boundsY0 = Integer.MAX_VALUE;
private int boundsX1 = Integer.MIN_VALUE;
private int boundsY1 = Integer.MIN_VALUE;
public void handle(int[][] input) {
Arrays.stream(input).forEach(this::processInput);
}
public void processInput(int[] input){
rectangles.add(new Rectangle(input));
updateBounds(input);
}
public ArrayDeque<Rectangle> getRectangles() {
return rectangles;
}
public Rectangle getBounds() {
return new Rectangle(boundsX0, boundsY0, boundsX1, boundsY1);
}
private void updateBounds(int[] input) {
boundsX0 = Math.min(input[0], boundsX0);
boundsY0 = Math.min(input[1], boundsY0);
boundsX1 = Math.max(input[2], boundsX1);
boundsY1 = Math.max(input[3], boundsY1);
}
}
class PerfectRectangleChecker
public class PerfectRectangleChecker {
private final HashSet<Point> disjunctiveCorners = new HashSet<>();
private final Rectangle bounds;
private int area;
public PerfectRectangleChecker(Rectangle bounds) {
this.bounds = bounds;
}
public boolean check(ArrayDeque<Rectangle> rectangles) {
for (Rectangle r : rectangles) {
processRectangles(r);
}
if (isAreaMismatching()){
return false;
}
if (boundsMismatchDisjunctivePoints()){
return false;
}
if(disjunctiveCornersMismatchAmount()){
return false;
}
//not simplified return statement to emphasize the three checks performed
return true;
}
private boolean disjunctiveCornersMismatchAmount() {
return disjunctiveCorners.size() != 4;
}
private boolean boundsMismatchDisjunctivePoints() {
return Arrays.stream(bounds.points).anyMatch(Predicate.not(disjunctiveCorners::contains));
}
private boolean isAreaMismatching() {
return area != bounds.area;
}
private void processRectangles(Rectangle r) {
area = area + r.area;
Arrays.stream(r.points).forEach(this::processDisjunctiveCorners);
}
private void processDisjunctiveCorners(Point p) {
if (disjunctiveCorners.contains(p)) {
disjunctiveCorners.remove(p);
} else {
disjunctiveCorners.add(p);
}
}
}
Tests:
public class SolutionTest {
final static int[][] VALID_DATA = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
final static int[][] INVAILD_DATA = {{0,0,1,1},{0,0,2,1},{1,0,2,1},{0,2,2,3}};
@Test
public void testValidInput() {
Solution solution = new Solution();
Assert.assertTrue( solution.isRectangleCover(VALID_DATA) );
}
@Test
public void testInvalidInput() {
Solution solution = new Solution();
Assert.assertFalse(solution.isRectangleCover(INVAILD_DATA) );
}
//more test after more data is provided
}
