Optimized version of top Java solution, 35ms (beats 100%)


  • 0
    K

    Credit to hu19 for posting the original O(n) solution. I just took the idea and put in some micro-optimizations. It might not work for every possible test case but you can increase the value of MULT to make it more resilient to malicious test cases.

        private static final int MULT = 10;
    
        public boolean isRectangleCover(int[][] rectangles) {
            transform(rectangles);
            int maxy = Integer.MIN_VALUE;
            int miny = Integer.MAX_VALUE;
            int maxx = Integer.MIN_VALUE;
            int minx = Integer.MAX_VALUE;
            
            int totalArea = 0;
            BitSet corners = new BitSet();
            int smallx, bigx, smally, bigy;
            for (int[] rect : rectangles) {
                smallx = rect[0];
                smally = rect[1];
                bigx = rect[2];
                bigy = rect[3];
                minx = Math.min(minx, smallx);
                miny = Math.min(miny, smally);
                maxx = Math.max(maxx, bigx);
                maxy = Math.max(maxy, bigy);
                
                totalArea += (bigx - smallx) * (bigy - smally);
                int topleft = MULT * smallx + bigy;
                int topright = MULT * bigx + bigy;
                int bottomleft = MULT * smallx + smally;
                int bottomright = MULT * bigx + smally;
    
                corners.flip(topleft);
                corners.flip(topright);
                corners.flip(bottomleft);
                corners.flip(bottomright);
            }
            
            int overallArea = (maxx - minx) * (maxy - miny);
            if (overallArea != totalArea) {
                return false;
            }
            
            BitSet overallCorners = new BitSet();
            overallCorners.set(MULT * minx + miny);
            overallCorners.set(MULT * minx + maxy);
            overallCorners.set(MULT * maxx + miny);
            overallCorners.set(MULT * maxx + maxy);
            
            return overallCorners.equals(corners);
        }
        
        private void transform(int[][] rectangles) {
            int maxy = Integer.MIN_VALUE;
            int miny = Integer.MAX_VALUE;
            int maxx = Integer.MIN_VALUE;
            int minx = Integer.MAX_VALUE;
            for (int[] rect : rectangles) {
                minx = Math.min(minx, rect[0]);
                miny = Math.min(miny, rect[1]);
                maxx = Math.max(maxx, rect[2]);
                maxy = Math.max(maxy, rect[3]);
            }
            for (int[] rect : rectangles) {
                rect[0] -= minx;
                rect[1] -= miny;
                rect[2] -= minx;
                rect[3] -= miny;
            }
        }```

Log in to reply
 

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