Problem 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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
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:

1
2
3
4
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.

Solution:

  • Naive solution:
    Find four corner points by traversing the grid in $O(m^2 * n^2)$ time.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        int countCornerRectangles(vector<vector<int>>& grid) {
            //find corners start from top-left
            //only need four corner points to be 1
            int m= grid.size(), n= grid[0].size(), res= 0;
            for(int i= 0; i< m; i++){
                for(int j= 0; j< n; j++){
                    if(grid[i][j] == 0) continue; 
                    //no need to continue if top-left is 0
                    
                    printf("i, j grid[%d][%d] is 1\n", i, j);
                    for(int p= i+1; p< m; p++){
                        if(grid[p][j] == 0) {
                            printf("grid[%d][%d] is 0\n", p, j);
                            continue;
                        }
                            
                        printf("grid[%d][%d] is 1\n", p, j);
                        for(int q= j+1; q< n; q++){
                            res+= grid[p][q] && grid[i][q];
                        }
                    }
                }
            }
            return res;
        }
    };

time complexity: $O()$
space complexity: $O()$
reference:
https://goo.gl/iFofQc