750. Number Of Corner Rectangles - cocoder39/coco39_LC GitHub Wiki

750. Number Of Corner Rectangles

pos = j*200 + k to identify a unique combination of j and k

O(m * n^2) time and O(n^2) space

public int countCornerRectangles(int[][] grid) {
        Map<Integer, Integer> mp = new HashMap<>();
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = j + 1; k < n; k++) {
                        if (grid[i][k] == 1) {
                            int pos = j * 200 + k;
                            int count = mp.getOrDefault(pos, 0);
                            res += count;
                            mp.put(pos, count+1);
                        }
                    }
                }   
            }
        }
        return res;
    }

f pairs of 1s -> f*(f-1)/2 rectangles

O(m^2 * n) time and O(1) space

public int countCornerRectangles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < i; j++) {
                int count = 0;
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        count++;
                    }
                }
                res += count * (count - 1) / 2;
            }       
        }
        return res;
    }