Rectangle Area

So many problems related to Rectangle Areas. I will have a very quick summary here.

850. Rectangle Area II

Rectangle Area II - LeetCode

As suggested by AoXiang Cui. It has solution of O(N³) and O(NlogN)

O(N³) from aoxiang cui (C++ 16 ms)

LeetCode Weekly Contest 88 screencast - LeetCode Discuss

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;
}
};

Convert to python version (132ms)

from bisect import bisect_left
class Solution:
    def rectangleArea(self, a: List[List[int]]) -> int:
        n = len(a)
        X, Y = [], []
        for x1, y1, x2, y2 in a:
            X.append(x1)
            X.append(x2)
            Y.append(y1)
            Y.append(y2)
        X, Y = sorted(set(X)), sorted(set(Y))
        visit = [[False]*len(Y) for _ in range(len(X))]
        for x1, y1, x2, y2 in a:
            x11, x22= bisect_left(X, x1), bisect_left(X, x2)
            y11, y22 = bisect_left(Y, y1), bisect_left(Y, y2)
            for u in range(x11, x22):
                for v in range(y11, y22):
                    visit[u][v] = True
        res = 0
        for i in range(len(X)):
            for j in range(len(Y)):
                if visit[i][j]:
                    res += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
        return res % (10**9+7)