750. Number Of Corner Rectangles

// LeetCode URL: https://leetcode.com/problems/number-of-corner-rectangles/

/**
 * To find an axis-aligned rectangle, the idea is to fix two rows (or two
 * columns) first, then check column by column (or row by row) to find "1" on
 * both rows. Say you find n pairs, then just pick any 2 of those to form an
 * axis-aligned rectangle
 *
 * Time Complexity: O(max(R,C) * (min(R,C))^2)
 *
 * Space Complexity: O(1)
 */
class Solution {
    public int countCornerRectangles(int[][] grid) {
        if (grid == null || grid.length <= 1 || grid[0].length <= 1) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;

        return rows <= cols ? util(grid, rows, cols, true) : util(grid, cols, rows, false);
    }

    private int util(int[][] grid, int m, int n, boolean isRowSmall) {
        int result = 0;

        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j < m; j++) {
                int counter = 0;
                for (int k = 0; k < n; k++) {
                    if (isRowSmall) {
                        counter += (grid[i][k] & grid[j][k]);
                    } else {
                        counter += (grid[k][i] & grid[k][j]);
                    }
                }
                result += counter * (counter - 1) / 2;
            }
        }

        return result;
    }
}