Rectangle Area: Coordinate Compression

Problem

850. Rectangle Area II

Explanation

We can use coordinate compression to solve this probem. Detail explanation can be found here.

Our idea is this: we’ll take all the x and y coordinates, and re-map them to 0, 1, 2, ...etc. For example, if rectangles = [[0,0,200,200],[100,0,200,300],[100,0,300,100]], we could re-map it to [[0,0,2,2],[1,0,2,3],[1,0,3,1]]. Then, we can solve the problem with brute force. However, each region may actually represent some larger area, so we'll need to adjust for that at the end. From [1]

Code

/*
time complexity: O(n^3) where n is the number of rectangles.
apace complexity: O(n^2)
*/
typedef long long int64;
const int MOD = 1e9 + 7;
class Solution {
public:
    int rectangleArea(vector<vector<int>>& a) {
        int n = a.size();
        vector<int> X, Y;
        for (int i = 0; i < n; ++i) {
            X.push_back(a[i][0]);
            X.push_back(a[i][2]);
            Y.push_back(a[i][1]);
            Y.push_back(a[i][3]);
        }
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());
        vector<vector<bool>> visit(X.size(), vector<bool>(Y.size()));
        for (int i = 0; i < n; ++i) {
            int x1 = lower_bound(X.begin(), X.end(), a[i][0]) - X.begin();
            int x2 = lower_bound(X.begin(), X.end(), a[i][2]) - X.begin();
            int y1 = lower_bound(Y.begin(), Y.end(), a[i][1]) - Y.begin();
            int y2 = lower_bound(Y.begin(), Y.end(), a[i][3]) - Y.begin();
            for (int u = x1; u < x2; ++u) {
                for (int v = y1; v < y2; ++v) {
                    visit[u][v] = true;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < X.size(); ++i) {
            for (int j = 0; j < Y.size(); ++j) {
                if (visit[i][j]) {
                    ret = (ret + (int64)(X[i + 1] - X[i]) * (Y[j + 1] - Y[j])) % MOD;
                }
            }
        }
        return ret;
}
};

Reference

[1] https://leetcode.com/problems/rectangle-area-ii/solution/