Short Java solution with explanation (updated)


  • 15

    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;
        }
    }
    

  • 2

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


  • 1

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


  • 4
    X

    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;
        }
    }
    
    

  • 3
    X

    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()) {
                table[corner] = mask;
            } else if ((table[corner] & mask) != 0) {
                return true;
            } else {
                table[corner] |= mask;
            }
            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);
        }
    };
    

  • 0
    This post is deleted!

  • 1

    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)
    

  • 0

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


  • 0

    Really straight-forward solution. Thanks for sharing.


  • 1
    J

    @mylzsd
    best solution, really clever for overlapping solution!


  • 0
    W

    A very nice solution. Thx!


  • 0
    S

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


  • 0

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


  • 0
    S

    @mylzsd said in Short Java solution with explanation (updated):

    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;


  • 0
    L

    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.


  • 0
    F

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


  • 0

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


  • 0
    C

    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.


  • 0

    @coldknight said in Short Java solution with explanation (updated):

    I think your codes will fail on

    Why don't you just test it?


  • 0

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


Log in to reply
 

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