Description

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

HashMap, time O(m * n ^ 2), space O(n ^ 2)

We ask the question: for each additional row, how many more rectangles are added?

For each pair of 1s in the new row (say at new_row[i] and new_row[j]), we could create more rectangles where that pair forms the base. The number of new rectangles is the number of times some previous row had row[i] = row[j] = 1.

Algorithm

Let's maintain a count count[i, j], the number of times we saw row[i] = row[j] = 1. When we process a new row, for every pair new_row[i] = new_row[j] = 1, we add count[i, j] to the answer, then we increment count[i, j].

此外，为了方便判断两个pair(i, j)是否相等，可以用一维i * n + j 来表示pair。

class Solution {
    public int countCornerRectangles(int[][] grid) {
        Map<Integer, Integer> idx2Count = new HashMap<>();
        int rectangles = 0;
        int n = grid[0].length;
        
        for (int[] row : grid) {
            for (int col0 = 0; col0 < n - 1; ++col0) {
                if (row[col0] != 1) {
                    continue;
                }
                
                for (int col1 = col0 + 1; col1 < n; ++col1) {
                    if (row[col1] != 1) {
                        continue;
                    }
                    
                    int idx = getIndex(col0, col1, n);
                    int count = idx2Count.getOrDefault(idx, 0);
                    rectangles += count;
                    idx2Count.put(idx, count + 1);
                }
            }
        }
        
        return rectangles;
    }
    
    private int getIndex(int i, int j, int n) {
        return i * n + j;
    }
}