Create number-of-corner-rectangles.cpp

kamyu104 · web-flow · commit 7210c74ff0b9 · 2017-12-17T09:02:12.000-06:00
diff --git a/C++/number-of-corner-rectangles.cpp b/C++/number-of-corner-rectangles.cpp
@@ -0,0 +1,32 @@
+// 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;
+    }
+};
