Leetcode 750. Number Of Corner Rectangles

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:

1. The number of rows and columns of grid will each be in the range [1, 200].
2. Each grid[i][j] will be either 0 or 1.
3. The number of 1s in the grid will be at most 6000.

Solution 1:
One straight-forward solution is: we can iterate any two rows, say r1 and r2, and for every column, we check if grid[r1][c] == grid[r2][c]. IF yes, we increate the count by 1. Then the number of rentangles formed by these two rows are count * (count - 1) / 2.

The time complexity of the solution is O(m^2 * n). 

If the number of rows is significantly greater than number of columns, we can iterate the columns and check the rows for each of the two columns. Then the time complexity is O(n^2 * m).

Solution 2:
Solution 2 is similar to solution 1. The main difference is we use a hash map to save the positions of the two rows.

Code (Java):

class Solution {
    public int countCornerRectangles(int[][] grid) {
        if (grid == null || grid.length < 2 || grid[0] == null || grid[0].length < 2) {
            return 0;
        }
        
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        int m = grid.length;
        int n = grid[0].length;
        
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r1][c] == 1 && grid[r2][c] == 1) {
                        int pos = r1* n + r2;
                        if (map.containsKey(pos)) {
                            int val = map.get(pos);
                            ans += val;
                            map.put(pos, val + 1);
                        } else {
                            map.put(pos, 1);
                        }
                    }
                }
            }
        }
        
        return ans;
    }
}