850. Rectangle Area II

850. Rectangle Area II

Question

We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectangles in the plane. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.

Example 2:

Input: [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.

Note:

1. 1 <= rectangles.length <= 200
2. rectanges[i].length = 4
3. 0 <= rectangles[i][j] <= 10^9
4. The total area covered by all rectangles will never exceed 2^63 - 1 and thus will fit in a 64-bit signed integer.

Thinking:

• Method 1: Set TLE

    class Solution {
        public int rectangleArea(int[][] rectangles) {
            Set<Long> set = new HashSet<>();
            long width = (long)10e9;
            for(int[] rectangle : rectangles){
                for(long x = rectangle[0]; x < rectangle[2]; x++){
                    for(int y = rectangle[1]; y < rectangle[3]; y++){
                        set.add(x * width + y);
                    }
                }
            }
            return set.size() % (int)(10e9 + 7);
        }
    }
  

• Method 2: Sweep line AC

    class Solution {
        private static final int ENTER = 0;
        private static final int LEAVE = 1;
        public int rectangleArea(int[][] rectangles) {
            int[][] events = new int[rectangles.length * 2][4];
            int index = 0;
            for(int[] rect : rectangles){
                // bottom side as enter event, upper side as leaving event
                events[index++] = new int[]{rect[1], ENTER, rect[0], rect[2]};
                events[index++] = new int[]{rect[3], LEAVE, rect[0], rect[2]};
            }
            // Reorder the sweep lines in ascending order.
            Arrays.sort(events, (a, b)->{   // sort according to the increase of the sweep line.
                return a[0] - b[0];
            });
            long res = 0L;
            int cur_y = events[0][0];
            // List to save all activate ranges, may have overlap.
            List<int[]> active = new ArrayList<>();
            for(int[] event : events){
                int y = event[0], act = event[1], start = event[2], end = event[3];
                long cur = 0, width = 0;
                // Find the width length(without overlap)
                for(int[] range : active){
                    cur = Math.max(cur, range[0]);
                    width += Math.max(0, range[1] - cur);
                    cur = Math.max(cur, range[1]);
                }
                // Add the area.
                res += width * (y - cur_y);
                // If enter event, add the range to active list, otherwise remove the range.
                if(act == ENTER){
                    active.add(new int[]{start, end});
                    Collections.sort(active, (a, b)->{
                        return a[0] - b[0];
                    });
                }else{
                    for(int i = 0; i < active.size(); i++){
                        if(start == active.get(i)[0] && end == active.get(i)[1]){
                            active.remove(i);
                            break;
                        }
                    }
                }
                cur_y = y;
            }
            res %= 1000000007;
            return (int)res;
        }
    }
  

• Method 3: Coordinate comparison

    class Solution {
        public int rectangleArea(int[][] rectangles) {
            int N = rectangles.length;
            Set<Integer> xSet = new HashSet<>();
            Set<Integer> ySet = new HashSet<>();
            for(int[] rec : rectangles){
                xSet.add(rec[0]);
                xSet.add(rec[2]);
                ySet.add(rec[1]);
                ySet.add(rec[3]);
            }
            Integer[] xArr = xSet.toArray(new Integer[0]);
            Integer[] yArr = ySet.toArray(new Integer[0]);
            Arrays.sort(xArr);
            Arrays.sort(yArr);
            Map<Integer, Integer> xMap = new HashMap<>();
            Map<Integer, Integer> yMap = new HashMap<>();
            for(int i = 0; i < xArr.length; i++){
                xMap.put(xArr[i], i);
            }
            for(int i = 0; i < yArr.length; i++){
                yMap.put(yArr[i], i);
            }
            boolean[][] grid = new boolean[xArr.length][yArr.length];
            for(int[] rec: rectangles){
                for(int x = xMap.get(rec[0]); x < xMap.get(rec[2]); x++){
                    for(int y = yMap.get(rec[1]); y < yMap.get(rec[3]); y++){
                        grid[x][y] = true;
                    }
                }
            }
            long res = 0L;
            for(int i = 0; i < grid.length; i++){
                for(int j = 0; j < grid[0].length; j++){
                    if(grid[i][j]){
                        res += (long)(xArr[i + 1] - xArr[i]) * (yArr[j + 1] - yArr[j]);
                    }
                }
            }
            res %= 1000_000_007;
            return (int)res;
        }
    }