// Time: O(m^2 * n), m is the number of rows with 1s, n is the number of cols with 1s

// Space: O(m * n)

class Solution {

public:

int countCornerRectangles(vector<vector<int>>& grid) {

vector<vector<int>> rows;

for (int i = 0; i < grid.size(); ++i) {

vector<int> row;

for (int j = 0; j < grid[i].size(); ++j) {

if (grid[i][j]) {

row.emplace_back(j);

}

}

if (!row.empty()) {

rows.emplace_back(move(row));

}

}

int result = 0;

for (int i = 0; i < rows.size(); ++i) {

unordered_set<int> lookup(rows[i].begin(), rows[i].end());

for (int j = 0; j < i; ++j) {

int count = 0;

for (const auto& c : rows[j]) {

count += lookup.count(c);

}

result += count * (count - 1) / 2;

}

}

return result;

}

};