750. Number Of Corner Rectangles

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

Iteration, O(n ^ 2 * k), S(nk)

class Solution {
    public int countCornerRectangles(int[][] grid) {
        List<List<Integer>> ones = new ArrayList<>();
        
        for (int[] row : grid) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < row.length; ++j) {
                if (row[j] == 1) {
                    list.add(j);
                }
            }
            
            ones.add(list);
        }
        
        int count = 0;
        for (int i = 0; i < ones.size() - 1; ++i) {
            for (int j = i + 1; j < ones.size(); ++j) {
                int common = getCommonCount(ones.get(i), ones.get(j));
                count += common * (common - 1) / 2;
            }
        }
        
        return count;
    }
    
    private int getCommonCount(List<Integer> l1, List<Integer> l2) {
        int count = 0;
        
        for (int i = 0, j = 0; i < l1.size() && j < l2.size(); ) {
            if (l1.get(i) < l2.get(j)) {
                ++i;
            } else if (l1.get(i) > l2.get(j)) {
                ++j;
            } else {
                ++count;
                ++i;
                ++j;
            }
        }
        
        return count;
    }
}