Leetcode 850: Rectangle Area II

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

Example 2:

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (109 + 7), which is 49.

Constraints:

• 1 <= rectangles.length <= 200
• rectanges[i].length == 4
• 0 <= xi1, yi1, xi2, yi2 <= 10^9
• xi1 <= xi2
• yi1 <= yi2

Problem Analysis:

This problem needs some trick skill to solve it. As the number of rectangles is at most 200. Then we know the number of different y position is at most 400.

We can compute the areas between different y position. Then we sum the area it would be the answer.

The diff of different y position as the height, and we sum the coverage of x position as the width. Height multiply width is the area of the y position.

We sort different x and y positions, the trick here is use a count variable to make sure the area of (x[i], x[i + 1]) in current y position should not be repeated summed.

If a rectangle is ended at x[i], then count[i] should minus 1, or count[i] add 1. Then if count[i] > 0, we know we need add the (x[i], x[i+1]) area.

Solution

class Solution {
public:
  const int mod = 1e9 + 7;
  int rectangleArea(vector<vector<int>>& rectangles) {
    vector<int> x;
    for (const auto& item : rectangles) {
      x.push_back(item[0]);
      x.push_back(item[2]);
    }
    sort(x.begin(), x.end());
    vector<int>::iterator end_unique = unique(x.begin(), x.end());
    x.erase(end_unique, x.end());

    unordered_map<int, int> x_i;
    for (int i = 0; i < x.size(); ++i) x_i[x[i]] = i;

    vector<int> count(x.size());
    vector<vector<int>> len;
    for (const auto& item : rectangles) {
      len.push_back({item[1], item[0], item[2], 1});
      len.push_back({item[3], item[0], item[2], -1});
    }
    sort(len.begin(), len.end());

    long long current_y{0};
    long long current_x{0};
    long long res{0};
    for (const auto& item : len) {
      res = (res + (item[0] - current_y) * current_x) % mod;
      current_y = item[0];
      for (int i = x_i[item[1]]; i < x_i[item[2]]; ++i)
        count[i] += item[3];
      current_x = 0;
      for (int i = 0; i < x.size() - 1; ++i) {
        if (count[i] > 0) current_x += x[i + 1] - x[i];
      }
    }

    return res;
  }
};

Time complexity is O(n²)

Space complexity is O(n)