O(N) solution of Problem 3 based on range addition


  • 0
    Y

    Update: This code fails the test case [[0, 1, 2, 3],[0, 1, 1, 2],[2, 2, 3, 3],[1, 0, 3, 1],[2, 0, 3, 1]]. Because this test case has overlap but still has the right height and width sum. Anyone can provide a right solution? I am wondering if this problem can be solved in O(N) time.

    The basic idea is:

    If the rectangles can cover a big rectangle [x0, y0, x1, y1], then for any x in [x0, x1], the total height of small rectangles should be y1 - y0; for any y in [y0, y1], the total width of small rectangles should be x1 - x0.

    Based on this idea, we can firstly convert rectangles to ranges [begin, end, height] on x axis. Then we do a range addition on all these ranges. If they can form a large rectangle, the result should be a single range with height y1 - y0. Similarly, we can convert rectangles to ranges [begin, end, width] on y axis. Again, we check if the result is a single range whose width is x1 - x0.

    public class Solution {
        
        public boolean isRectangleCover(int[][] rectangles) {
            Map<Integer, Integer> x = new HashMap<>();
            Map<Integer, Integer> y = new HashMap<>();
            int xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
            int yMin = Integer.MAX_VALUE, yMax = Integer.MIN_VALUE;
            for(int[] rect: rectangles) {
                int width = rect[2] - rect[0];
                int height = rect[3] - rect[1];
                increase(x, rect[0], height);
                increase(x, rect[2], -height);
                increase(y, rect[1], width);
                increase(y, rect[3], -width);
                xMin = Math.min(xMin, rect[0]);
                xMax = Math.max(xMax, rect[2]);
                yMin = Math.min(yMin, rect[1]);
                yMax = Math.max(yMax, rect[3]);
            }
            int xCount = 0, yCount = 0, height = 0, width = 0;
            for(int val: x.values()) {
                if(val != 0) {
                    xCount ++;
                    height = Math.abs(val);
                }
            }
            for(int val: y.values()) {
                if(val != 0) {
                    yCount ++;
                    width = Math.abs(val);
                }
            }
            return xCount == 2 && yCount == 2 && height == yMax-yMin && width == xMax-xMin;
        }
        
        private void increase(Map<Integer, Integer> map, int key, int inc) {
            map.put(key, map.containsKey(key)? (map.get(key)+inc): inc);
        }
    }
    

  • 0

    Thanks, I have just added your test case.


Log in to reply
 

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