Problem
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
}
Solution
Some minor changes could be applied to the code, for example the following lines :
ArrayDeque<Rectangle> rectangles = inputProvider.getRectangles();
public ArrayDeque<Rectangle> getRectangles() { ... }
private final HashSet<Point> disjunctiveCorners = new HashSet<>();
public boolean check(ArrayDeque<Rectangle> rectangles) { ... }
The could be rewritten using the Deque interface and the Set interface :
Deque<Rectangle> rectangles = inputProvider.getRectangles();
public Deque<Rectangle> getRectangles() { ... }
private Set<Point> disjunctiveCorners = new HashSet<>();
public boolean check(Deque<Rectangle> rectangles) { ... }
I see no other things I would change in your code, one reflection about the algorithm : it seems me that to see if all the rectangles together form an exact cover of a rectangular region you could add the areas of the rectangles and check if the total area is equal to the rectangle having the most sw corner and the most ne corner between all rectangles. In case of one gap between two rectangles the total area would be minor than the perfect rectangle area, in case of intersection the total area would be greater.
Following this idea I rewrote the algorithm in this way :
public class Solution {
private static int calculateArea(int[] rectangle) {
return (rectangle[2] - rectangle[0]) * (rectangle[3] -rectangle[1]);
}
public static boolean isRectangleCover(int[][] rectangles) {
int x0 = Integer.MAX_VALUE;
int y0 = Integer.MAX_VALUE;
int x1 = Integer.MIN_VALUE;
int y1 = Integer.MIN_VALUE;
int totalArea = 0;
for (int[] rectangle : rectangles) {
x0 = Math.min(rectangle[0], x0);
y0 = Math.min(rectangle[1], y0);
x1 = Math.max(rectangle[2], x1);
y1 = Math.max(rectangle[3], y1);
totalArea += calculateArea(rectangle);
}
return totalArea == calculateArea(new int[]{x0, y0, x1, y1});
}
}
I have updated the test class with cases from leetcode:
public class SolutionTest {
//[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
@Test
public void test1() {
int[][] rectangles = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
assertTrue(Solution.isRectangleCover(rectangles));
}
//[[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
@Test
public void test2() {
int[][] rectangles = {{1, 1, 2, 3}, {1, 3, 2, 4}, {3, 1, 4, 2}, {3, 2, 4, 4}};
assertFalse(Solution.isRectangleCover(rectangles));
}
//[[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
@Test
public void test3() {
int[][] rectangles = {{1, 1, 3, 3}, {3, 1, 4, 2}, {1, 3, 2, 4}, {3, 2, 4, 4}};
assertFalse(Solution.isRectangleCover(rectangles));
}
//[[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
@Test
public void test4() {
int[][] rectangles = {{1, 1, 3, 3}, {3, 1, 4, 2}, {1, 3, 2, 4}, {2, 2, 4, 4}};
assertFalse(Solution.isRectangleCover(rectangles));
}
}
Update :
Thanks to Martin’s comments I saw that the above solution works just for the cases available on the leetcode site without login, so the additional test cases fail. To pass all the test cases it is necessary to use the property that in a perfect rectangle the vertices are present in just one rectangle, while the others are shared by 2 or 4 rectangles.
If a vertex (x, y) is equal to a List<Integer> with two elements it is possible to define a custom Comparator that orders by x and then y like below and a specific TreeSet:
Comparator<List<Integer>> comp = (l1, l2) -> {
int diff = l1.get(0) - l2.get(0);
if (diff == 0) {
return l1.get(1) - l2.get(1);
}
return diff;
};
SortedSet<List<Integer>> set = new TreeSet<>(comp);
int totalArea = 0;
Once defined it, it is possible calculate the sum of all rectangle areas and creating the set with the vertices that are owned just by one rectangle :
for (int[] rectangle : rectangles) {
totalArea += calculateArea(rectangle);
int x0 = rectangle[0];
int y0 = rectangle[1];
int x1 = rectangle[2];
int y1 = rectangle[3];
List<List<Integer>> list = List.of(List.of(x0, y0),
List.of(x0, y1),
List.of(x1, y0),
List.of(x1, y1));
for (List<Integer> pointRep : list) {
if (set.contains(pointRep)) {
set.remove(pointRep);
} else {
set.add(pointRep);
}
}
}
Because the set is ordered, if the cardinality is 4 it is possible to compare the total area with the perfect rectangle and check the result :
if (set.size() != 4) { return false; }
int[] sw = set.first().stream().mapToInt(i->i).toArray();
int[] ne = set.last().stream().mapToInt(i->i).toArray();
return totalArea == calculateArea(new int[] {sw[0], sw[1], ne[0], ne[1] });
Combining all the code lines together below my updated solution :
class Solution {
public static boolean isRectangleCover(int[][] rectangles) {
Comparator<List<Integer>> comp = (l1, l2) -> {
int diff = l1.get(0) - l2.get(0);
if (diff == 0) {
return l1.get(1) - l2.get(1);
}
return diff;
};
SortedSet<List<Integer>> set = new TreeSet<>(comp);
int totalArea = 0;
for (int[] rectangle : rectangles) {
totalArea += calculateArea(rectangle);
int x0 = rectangle[0];
int y0 = rectangle[1];
int x1 = rectangle[2];
int y1 = rectangle[3];
List<List<Integer>> list = List.of(List.of(x0, y0),
List.of(x0, y1),
List.of(x1, y0),
List.of(x1, y1));
for (List<Integer> pointRep : list) {
if (set.contains(pointRep)) {
set.remove(pointRep);
} else {
set.add(pointRep);
}
}
}
if (set.size() != 4) { return false; }
int[] sw = set.first().stream().mapToInt(i->i).toArray();
int[] ne = set.last().stream().mapToInt(i->i).toArray();
return totalArea == calculateArea(new int[] {sw[0], sw[1], ne[0], ne[1] });
}
private static int calculateArea(int[] rectangle) {
return (rectangle[2] - rectangle[0]) * (rectangle[3] -rectangle[1]);
}
}