# Short Java solution with explanation (updated)

• If all rectangles can form an exact rectangular area, they should follow these conditions:

1. The sum of area of all small rectangles should equal to the area of large rectangle.
2. At any position except outer four corners, the amount of overlapping corners should be even (2, 4).
3. Corners that overlap at the same point should be different type (top-left, top-right, bottom-left, bottom-right).

So, I used

1. Four int variables to record the boundaries of large rectangle and then calculate the area.
2. A hashmap that maps corner with its type.
3. Four numbers (1, 2, 4, 8) to represent four types of corner. Then use bit manipulation to modify and check.

O(n) time complexity, O(n) space, 112 ms run time.
Special credit to @wu474purdue-edu

public class Solution {
Map<String, Integer> map = new HashMap<String, Integer>();
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles.length == 0 || rectangles[0].length == 0) return false;
int lx = Integer.MAX_VALUE, ly = lx, rx = Integer.MIN_VALUE, ry = rx, sum = 0;
for (int[] rec : rectangles) {
lx = Math.min(lx, rec[0]);
ly = Math.min(ly, rec[1]);
rx = Math.max(rx, rec[2]);
ry = Math.max(ry, rec[3]);
sum += (rec[2] - rec[0]) * (rec[3] - rec[1]);
//bottom-left
if (overlap(rec[0] + " " + rec[1], 1)) return false;
//top-left
if (overlap(rec[0] + " " + rec[3], 2)) return false;
//bottom-right
if (overlap(rec[2] + " " + rec[1], 4)) return false;
//top-right
if (overlap(rec[2] + " " + rec[3], 8)) return false;
}
int count = 0;
Iterator<Integer> iter = map.values().iterator();
while (iter.hasNext()) {
Integer i = iter.next();
if (i != 15 && i != 12 && i != 10 && i != 9 && i != 6 && i != 5 && i != 3) count++;
}
return count == 4 && sum == (rx - lx) * (ry - ly);
}

private boolean overlap(String corner, Integer type) {
Integer temp = map.get(corner);
if (temp == null) temp = type;
else if ((temp & type) != 0) return true;
else temp |= type;
map.put(corner, temp);
return false;
}
}

• It's wrong, fails for example [[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]].

Update: The code got changed and doesn't fail that case anymore. I guess the downvoter is incapable of reading the very next post confirming that this was indeed a working counterexample pointing out a flaw. (google's cache currently still shows this page at least 21 minutes after @mylzsd's reply and before the downvote).

• @StefanPochmann Thanks for pointing out. I updated the code, hopefully it works for all cases now.

• Nice solution! I read your code and found it also works if changing one line like the bold line below.

public class Solution {
Map<String, Integer> map = new HashMap<String, Integer>();
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles.length == 0 || rectangles[0].length == 0) return false;
int lx = Integer.MAX_VALUE, ly = lx, rx = Integer.MIN_VALUE, ry = rx, sum = 0;
for (int[] rec : rectangles) {
lx = Math.min(lx, rec[0]);
ly = Math.min(ly, rec[1]);
rx = Math.max(rx, rec[2]);
ry = Math.max(ry, rec[3]);
sum += (rec[2] - rec[0]) * (rec[3] - rec[1]);
//bottom-left
if (overlap(rec[0] + " " + rec[1], 1)) return false;
//top-left
if (overlap(rec[0] + " " + rec[3], 2)) return false;
//bottom-right
if (overlap(rec[2] + " " + rec[1], 4)) return false;
//top-right
if (overlap(rec[2] + " " + rec[3], 8)) return false;
}
int count = 0;
Iterator<Integer> iter = map.values().iterator();
while (iter.hasNext()) {
Integer i = iter.next();
**if (i == 8 || i == 4 || i == 2 || i == 1) count++;**
}
return count == 4 && sum == (rx - lx) * (ry - ly);
}

private boolean overlap(String corner, Integer type) {
Integer temp = map.get(corner);
if (temp == null) temp = type;
else if ((temp & type) != 0) return true;
else temp |= type;
map.put(corner, temp);
return false;
}
}

• Sorry the bold code above didn't display and the Below is C++ implementation.

class Solution {
private:
unordered_map<string, int> table;
bool overlap(string corner, int mask) {
if (table.find(corner) == table.end()) {
} else if ((table[corner] & mask) != 0) {
return true;
} else {
}
return false;
}
public:
bool isRectangleCover(vector<vector<int>>& rectangles) {
int tminx = INT_MAX, tminy = INT_MAX, tmaxx = INT_MIN, tmaxy = INT_MIN;
int area = 0;
for(vector<int> & v : rectangles) {
tminx = min(tminx, v[0]);
tminy = min(tminy, v[1]);
tmaxx = max(tmaxx, v[2]);
tmaxy = max(tmaxy, v[3]);

area += (v[2] - v[0]) * (v[3] - v[1]);
if(overlap(to_string(v[0]) + " " + to_string(v[1]), 1)) return false;
if(overlap(to_string(v[0]) + " " + to_string(v[3]), 2)) return false;
if(overlap(to_string(v[2]) + " " + to_string(v[1]), 4)) return false;
if(overlap(to_string(v[2]) + " " + to_string(v[3]), 8)) return false;
}
int count = 0;
for(auto ele : table) {
int val = ele.second;
if(val == 1 || val == 2 || val == 4 || val == 8) count++;
}
return count == 4 && area == (tmaxx - tminx) * (tmaxy - tminy);
}
};

• This post is deleted!

• I think this solution is very straight-forward, and we can build all process in our mind when we encounter in the interviews:
A python implementation but tweaks some position since the rectangles are marked as [bottom,left,top,right]

class Solution(object):
def __init__(self):
# ref:@mylzsd solution
self.mapping = {}

def overlap(self, key, ctype):
"""
only check same point overlap
do not check the example 3 overlap
example overlap can get rid of with area of sum
"""
tmp = self.mapping.get(key, 0)
if not tmp:
tmp = ctype
elif tmp & ctype:
return True
else:
tmp |= ctype
self.mapping[key] = tmp
return False

def isRectangleCover(self, rectangles):
"""
:type rectangles: List[List[int]]
:rtype: bool
"""
# The rectangle is [bottom,left,top,right]
if not len(rectangles) or not len(rectangles[0]):
return False
# record the max rectangle positions
lx = ly = (1 << 31)-1
rx = ry = -1 << 31
areasum = 0
for rect in rectangles:
lx,ly,rx,ry= min(lx, rect[1]),min(ly, rect[0]),max(rx, rect[3]),max(ry, rect[2])
areasum += (rect[2] - rect[0]) * (rect[3] - rect[1])
# bottom-left
if self.overlap(str(rect[0]) + '-' + str(rect[1]), 1): return False
# top-left
if self.overlap(str(rect[2]) + '-' + str(rect[1]), 2): return False
# top-right
if self.overlap(str(rect[2]) + '-' + str(rect[3]), 4): return False
# bottom-right
if self.overlap(str(rect[0]) + '-' + str(rect[3]), 8): return False
# record the final single point
cnt = 0
for val in self.mapping.values():
if val in [1, 2, 4, 8]:
cnt += 1
# check whether there are only four single point in [bottom-left,top-left,br,tr]
# and the sum of area is the same
return cnt == 4 and areasum == (rx - lx) * (ry - ly)

• @StefanPochmann Thanks Stefan, I've just added your test case.

• Really straight-forward solution. Thanks for sharing.

• @mylzsd
best solution, really clever for overlapping solution!

• A very nice solution. Thx!

• @mylzsd what if i change the condition

if (i != 15 && i != 12 && i != 10 && i != 9 && i != 6 && i != 5 && i != 3) count++;

TO

if (i==1 || i==2 || i==4 || i==8) count++;

does it same?

• @saddays 7, 11, 13, 14 should also be considered, these are cases that three corners overlap at the same point.

• corners
thanks for your replay ^_^

i think we don't need think of those cases. if it's a legal rectangle , the type=1,2,4,8 point must have one each.

your condition work because you count the point that type=7, 11, 13, 14 AND the point that type=1,2,4,8 , when former points(7,11,13,14) occur the latter points must more than 4, so the count>=5. when former points not exist, the count must equals 4. so just count type=1,2,4,8 may be OK.

PS. the condition i changed also pass the testcases;

• Really concise and easy to understand, thanks for sharing!

A tiny optimization: we could check the sum of area right after the for loop before check the corner counts, and return false right away if we find the area sum is not right. So we save the corner check for some cases. After this optimization the runtime is 93ms.

• Thanks for sharing this splendid method! It changes this problem into a point counting task.

• @mylzsd Nice solution. Would you mind sharing how did you come up with the algorithm? What characteristic of the problem gave you the hint of counting the corners? Thanks in advance.

• I think your codes will fail on this case [[0,0,1,1],[0,1,1,2],[0,2,1,3],[0,3,1,4],[0,4,1,5],[1,0,2,2],[1,1,2,3],[1,4,2,5],[2,0,3,1],[2,1,3,2],[2,2,3,3],[2,3,3,4],[2,4,3,5]]. I hope leetcode can add this case.

• I think your codes will fail on

Why don't you just test it?

• @coldknight I believe my solution covered this kind of cases.
Also @saddays , only considering 1, 2, 4, 8 will fail on his case.

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