Java O(n) solution (updated)


  • 1
    Y

    Original post was not correct. See reply below for a corrected solution.


    The idea is that, a perfect **m** x **n** rectangle can resemble integer 1 - m*n. The small pieces of rectangles need to sum up to exact the same number, just as one single rectangle does.

    Both sum methods below are O(1), so the whole solution is O(n) time.

    Note that I didn't consider integer overflow (the sum could be quite big). The solution can pass the current OJ, and it can instead use a float otherwise.

    public class Solution {
        
        int m=0, n=0;
        
        public boolean isRectangleCover(int[][] rectangles) {
            // finding bottom-left and top-right most corners
            int minx = Integer.MAX_VALUE, miny = Integer.MAX_VALUE, // bottom-left most 
                maxx = Integer.MIN_VALUE, maxy = Integer.MIN_VALUE; // top-right most
                
            for (int[] rec : rectangles) {
                minx = Math.min(minx, rec[0]);
                miny = Math.min(miny, rec[1]);
                maxx = Math.max(maxx, rec[2]);
                maxy = Math.max(maxy, rec[3]);
            }
            
            m = maxx-minx; n = maxy-miny;
            
            int count = 0;
            for (int[] rec : rectangles) {
                count += sum(rec[0]-minx, rec[1]-miny, rec[2]-minx, rec[3]-miny);
            }
            
            return count == sum(0, 0, m, n);
        }
        
        private int sum(int i1, int j1, int i2, int j2) { // bottom-left (i1, j1), top-right (i2, j2)
            return sum(i2, j2) - sum(i1, j2) - sum(i2, j1) + sum(i1, j1);
        }
        
        private int sum(int i, int j) { // top-right (i, j)
            return (1 + i*j) * i*j / 2;
        }
    }
    

  • 0
    Y

    Hmm, I realized that's not quite right, for example: [[1,1,2,2],[1,1,2,2],[1,1,2,2], [2,1,3,2],[2,2,3,3]]

    @administrators can we please add a test case? thanks


  • 0

    @ye23 Thanks for your test case, I have just added it.


  • 0
    Y

    @1337c0d3r Thanks!


  • 0
    Y

    A corrected solution built on top of the incomplete solution above. O(n) time and space.

    public class Solution {
        
        int m=0, n=0;
        int minx = 0, miny = 0, maxx = 0, maxy = 0;
        
        public boolean isRectangleCover(int[][] rectangles) {
            // finding bottom-left and top-right most corners
            minx = Integer.MAX_VALUE; miny = Integer.MAX_VALUE; // bottom-left most 
            maxx = Integer.MIN_VALUE; maxy = Integer.MIN_VALUE; // top-right most
                
            for (int[] rec : rectangles) {
                minx = Math.min(minx, rec[0]);
                miny = Math.min(miny, rec[1]);
                maxx = Math.max(maxx, rec[2]);
                maxy = Math.max(maxy, rec[3]);
            }
            
            m = maxx-minx; n = maxy-miny;
            
            int count = 0;
            for (int[] rec : rectangles) {
                count += sum(rec[0]-minx, rec[1]-miny, rec[2]-minx, rec[3]-miny);
            }
            
            // if they don't sum up same, it can't be a perfect rectangle
            if (count != sum(0, 0, m, n)) return false;
            
            // but equal sum doesn't guarantee a perfect rectangle, 
            // for example: [[1,1,2,2],[1,1,2,2],[1,1,2,2], [2,1,3,2],[2,2,3,3]]
    
            // similar idea as presented here: https://discuss.leetcode.com/topic/56052/really-easy-understanding-solution-o-n-java
            // all points, other than corners, must appear even number of times
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int[] rec : rectangles) {
                for(int num : fourCorners(rec)) {
                    map.put(num, (map.containsKey(num) ? map.get(num) : 0) + 1);
                }
            }
            for (Integer key : map.keySet()) {
                int val = map.get(key);
                if ((val&1) == 1 && 
                    point2Num(0, 0) != key && 
                    point2Num(0, n) != key && 
                    point2Num(m, 0) != key && 
                    point2Num(m, n) != key) {
                        return false;
                    }
            }
            
            return true;
        }
        
        private int sum(int i1, int j1, int i2, int j2) { // bottom-left (i1, j1), top-right (i2, j2)
            return sum(i2, j2) - sum(i1, j2) - sum(i2, j1) + sum(i1, j1);
        }
        
        private int sum(int i, int j) { // top-right (i, j)
            return (1 + i*j) * i*j / 2;
        }
        
        private int[] fourCorners(int[] rec) {
            int tl = point2Num(rec[2]-minx, rec[1]-miny),
                tr = point2Num(rec[2]-minx, rec[3]-miny),
                bl = point2Num(rec[0]-minx, rec[1]-miny),
                br = point2Num(rec[0]-minx, rec[3]-miny);
            return new int[]{tl, tr, bl, br};
        }
        
        private int point2Num(int x, int y) {
            return x * m + y;
        }
    }
    

Log in to reply
 

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