# Optimized version of top Java solution, 35ms (beats 100%)

• Credit to hu19 for posting the original O(n) solution. I just took the idea and put in some micro-optimizations. It might not work for every possible test case but you can increase the value of MULT to make it more resilient to malicious test cases.

``````    private static final int MULT = 10;

public boolean isRectangleCover(int[][] rectangles) {
transform(rectangles);
int maxy = Integer.MIN_VALUE;
int miny = Integer.MAX_VALUE;
int maxx = Integer.MIN_VALUE;
int minx = Integer.MAX_VALUE;

int totalArea = 0;
BitSet corners = new BitSet();
int smallx, bigx, smally, bigy;
for (int[] rect : rectangles) {
smallx = rect[0];
smally = rect[1];
bigx = rect[2];
bigy = rect[3];
minx = Math.min(minx, smallx);
miny = Math.min(miny, smally);
maxx = Math.max(maxx, bigx);
maxy = Math.max(maxy, bigy);

totalArea += (bigx - smallx) * (bigy - smally);
int topleft = MULT * smallx + bigy;
int topright = MULT * bigx + bigy;
int bottomleft = MULT * smallx + smally;
int bottomright = MULT * bigx + smally;

corners.flip(topleft);
corners.flip(topright);
corners.flip(bottomleft);
corners.flip(bottomright);
}

int overallArea = (maxx - minx) * (maxy - miny);
if (overallArea != totalArea) {
return false;
}

BitSet overallCorners = new BitSet();
overallCorners.set(MULT * minx + miny);
overallCorners.set(MULT * minx + maxy);
overallCorners.set(MULT * maxx + miny);
overallCorners.set(MULT * maxx + maxy);

return overallCorners.equals(corners);
}

private void transform(int[][] rectangles) {
int maxy = Integer.MIN_VALUE;
int miny = Integer.MAX_VALUE;
int maxx = Integer.MIN_VALUE;
int minx = Integer.MAX_VALUE;
for (int[] rect : rectangles) {
minx = Math.min(minx, rect[0]);
miny = Math.min(miny, rect[1]);
maxx = Math.max(maxx, rect[2]);
maxy = Math.max(maxy, rect[3]);
}
for (int[] rect : rectangles) {
rect[0] -= minx;
rect[1] -= miny;
rect[2] -= minx;
rect[3] -= miny;
}
}`````````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.