Simple Java Solution With HashMap

  • 4

    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>());
                topmap.get(top).add(new Interval(left,right));
                if (!bottommap.containsKey(bottom))  bottommap.put(bottom,new ArrayList<Interval>());
                bottommap.get(bottom).add(new Interval(left,right));
                if(!leftmap.containsKey(left)) leftmap.put(left,new ArrayList<Interval>());
                leftmap.get(left).add(new Interval(bottom,top));
                if(!rightmap.containsKey(right)) rightmap.put(right,new ArrayList<Interval>());
                rightmap.get(right).add(new Interval(bottom,top));
                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);
                    res.add(new Interval(start, end) );
                if(cur.end>end) end=cur.end;
            res.add(new Interval(start, end) ); 
            return res;
    class Interval {
        int start,end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }

  • 0

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

  • 0

    @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.

  • 0
    This post is deleted!

Log in to reply

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