# Simple Java Solution With HashMap

• To make a perfect rectangle, two conditions need to be met:

1. The total area of all sub-rectangles == (rightmost-leftmost)*(uppermost-lowermost);
2. For every side of each sub-rectangle, there should be one or more sub-rectangles with corresponding counter-sides, except for the outermost sides, i.e., for each top side, there should be corresponding bottom sides of other sub-rectangle(s) with the same values, and the right sides should have corresponding left ones . So we use four maps to store all sides(<Interval>) of the sub-rectangles, and for each key in topmap, except for the uppermost side of the parent-rectangle, there should be a same key in bottommap, and their values should be the same after merging.
``````public class Solution {
public boolean isRectangleCover(int[][] rectangles) {
long area=0;
int up=Integer.MIN_VALUE, low = Integer.MAX_VALUE, rightest=Integer.MIN_VALUE, leftest=Integer.MAX_VALUE;
HashMap<Integer,ArrayList<Interval>> topmap = new HashMap<>();
HashMap<Integer,ArrayList<Interval>> bottommap = new HashMap<>();
HashMap<Integer,ArrayList<Interval>> leftmap = new HashMap<>();
HashMap<Integer,ArrayList<Interval>> rightmap = new HashMap<>();
for(int i=0;i<rectangles.length;i++){
int[] r1 = rectangles[i];
int top = r1[3], right = r1[2], left = r1[0], bottom = r1[1];
up = Math.max(top,up);
low = Math.min(low, bottom);
rightest = Math.max(right,rightest);
leftest = Math.min(left, leftest);
if (!topmap.containsKey(top))  topmap.put(top,new ArrayList<Interval>());
if (!bottommap.containsKey(bottom))  bottommap.put(bottom,new ArrayList<Interval>());
if(!leftmap.containsKey(left)) leftmap.put(left,new ArrayList<Interval>());
if(!rightmap.containsKey(right)) rightmap.put(right,new ArrayList<Interval>());
area += (top-bottom)*(right-left);
}
if(area!=( rightest-leftest)*(up-low)) return false;
if(bottommap.size()!=topmap.size()||leftmap.size()!=rightmap.size()) return false;
return (compareMaps(bottommap,topmap,low) && compareMaps(rightmap,leftmap,rightest) ) ;
}
public boolean compareMaps(HashMap<Integer,ArrayList<Interval>> map1, HashMap<Integer,ArrayList<Interval>> map2, int side){
for(int top: map1.keySet()  ){
if(top==side) continue;
List<Interval> mergedTopList = merge(map1.get(top));
if(!map2.containsKey(top)) return false;
List<Interval> mergedBottomeList = merge(map2.get(top));
if(mergedBottomeList.size()!=mergedTopList.size()) return false;
for(int i=0;i<mergedBottomeList.size();i++) {
if(mergedBottomeList.get(i).start!=mergedTopList.get(i).start ||mergedBottomeList.get(i).end!=mergedTopList.get(i).end) return false;
}
}
return true;
}
public List<Interval> merge(List<Interval> intervals) {
List<Interval> res = new ArrayList<>();
if(intervals==null||intervals.size()<2) return intervals;
Collections.sort(intervals, new Comparator<Interval>(){public int compare(Interval i1, Interval i2) { return i1.start-i2.start; } } );
int start = intervals.get(0).start, end=intervals.get(0).end;
for(int i=1;i<intervals.size();i++){
Interval cur = intervals.get(i);
if(cur.start>end){
start=cur.start;
}
if(cur.end>end) end=cur.end;
}
return res;
}
}
class Interval {
int start,end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
}
``````

• @schenley Great job! Could could be way cleaner though. Or perhaps it's me that I hate Java...

• @agave Yeah it's a bit verbose, and I just reused the codes of "merge intervals", while it can actually be simplified because we don't need to consider intervals overlapping here.

• This post is deleted!

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