Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]] Output: 1 Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Example 2:
Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Example 3:
Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.
Note:
The number of rows and columns of grid will each be in the range [1, 200]. Each grid[i][j] will be either 0 or 1. The number of 1s in the grid will be at most 6000.
[[0,1,0],[1,0,1],[1,0,1],[0,1,0]] [[1, 1, 1],[1, 1, 1],[1, 1, 1]] [[1, 0, 0, 1, 0],[0, 0, 1, 0, 1],[0, 0, 0, 1, 0],[1, 0, 1, 0, 1]] 0 1 0 1 0 1 1 0 1 0 1 0
vector<vector<vector>> vv = { {{0,1,0},{1,0,1},{1,0,1},{0,1,0}}, {{1, 1, 1},{1, 1, 1},{1, 1, 1}}, {{1, 0, 0, 1, 0},{0, 0, 1, 0, 1},{0, 0, 0, 1, 0},{1, 0, 1, 0, 1}}};
// 144ms, 80%
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
const int M = grid.size();
const int N = grid[0].size();
vector<vector<int>> rows(M); // rows[i] is the col num of 1's in row i
vector<vector<int>> cols(N); // cols[j] is the row num of 1's in col j
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
rows[i].push_back(j);
cols[j].push_back(i);
}
}
}
unordered_map<int, int> mmap;
int res = 0;
for (int i = 0; i < M; i++) {
if (rows[i].size() < 2)
continue;
for (int j = 0; j < rows[i].size(); j++) {
for (int k = j + 1; k < rows[i].size(); k++) {
auto v = rows[i][j]*200 + rows[i][k];
auto it = mmap.find(v);
if (it != mmap.end()) {
res += it->second;
it->second++;
} else {
mmap[v] = 1;
}
}
}
}
return res;
}
};
// 156ms, 77%
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
const int M = grid.size();
const int N = grid[0].size();
unordered_map<int, int> mmap;
int res = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
int k = j + 1;
while (k < N) {
if (grid[i][k] == 1) {
auto v = j*200 + k;
auto it = mmap.find(v);
if (it != mmap.end()) {
res += it->second;
it->second++;
} else {
mmap[v] = 1;
}
}
k++;
}
}
}
}
return res;
}
};
// 332ms, 32%
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
const int M = grid.size();
const int N = grid[0].size();
vector<vector<int>> rows(M); // rows[i] is the col num of 1's in row i
vector<vector<int>> cols(N); // cols[j] is the row num of 1's in col j
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
rows[i].push_back(j);
cols[j].push_back(i);
}
}
}
int res = 0;
for (int i = 0; i < M; i++) {
// if there is only one 1 in the row
if (rows[i].size() < 2)
continue;
for (int m = 0; m < rows[i].size(); m++) {
int p = m + 1; // next 1 in the row
int j = rows[i][m]; // col no of the top left 1
int q0 = 0;
// found next 1 in the col
while (q0 < cols[j].size() && cols[j][q0] <= i)
q0++;
if (q0 >= cols[j].size())
continue;
while (p < rows[i].size()) {
int q = q0;
while (q < cols[j].size()) {
int r2 = cols[j][q];
int c2 = rows[i][p];
if (grid[r2][c2] == 1)
res++;
q++;
}
p++;
}
}
}
return res;
}
};