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 1 s in the grid will be at most 6000 .

class Solution {
    public int countCornerRectangles(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        Map<String, Integer> hash = new HashMap<>();

        int ans = 0;
        for (int[] row : grid){
            for (int c1 = 0; c1 < row.length; c1++){
                if (row[c1] == 1){
                    for (int c2 = c1 + 1; c2 < row.length; c2++){
                        if (row[c2] == 1){
                            String pos = c1 + ":" + c2;
                            int count = hash.getOrDefault(pos, 0);
                            ans += count;
                            hash.put(pos, count + 1);
                        }
                    }
                }
            }
        }

        return ans;
    }
}