Number Of Corner Rectangles

Problem Statement

In this scenario, you are provided with an m x n matrix populated solely with binary integers (i.e., 0s and 1s). Your task is to determine how many distinct "corner rectangles" can be formed in the grid. Each corner rectangle is defined by four distinct 1s that form the vertices of an axis-aligned rectangle. Notably, it's essential for the rectangle to align with the axes of the grid, meaning that only horizontal and vertical alignments are permissible, with diagonally aligned 1s not constituting the corners of a valid rectangle.

Examples

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.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.
• The number of 1's in the grid is in the range [1, 6000].

Approach and Intuition

To solve this problem, one needs to adopt a systematic approach to count how many rectangles can be formed given the constraints:

1. Identify Pairs:

   • Conceptualize the matrix in terms of rows and columns. The idea is to identify all pairs of 1s in every row. These pairs will serve as potential top or bottom sides of the corner rectangles.

2. Count Matching Pairs:

   • For every pair of 1s identified in the above step, see if the same pair of columns has 1s in other rows too. Every time you find such a match in another row, a potential rectangle is identified.

3. Calculate Rectangle Count:

   • To avoid double-counting rectangles, focus only on identifying top sides and count every compatible bottom side found in any row below.
   • The rectangles formed by pairs (col1, col2) from different rows row1 and row2 are distinct rectangles. Keep a counter that sums up these valid rectangles.

4. Optimize Using Pre-Computed Values:

   • Use a hashmap or an equivalent structure to keep track of pairs and their occurrences across different row checks. This helps in quickly determining potential rectangles without redundant computations.

Example Explorations:

• Example 1:

  • The grid configuration [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]] results in one possible rectangle. This calculation aligns with the explanation and matches real grid visualization, confirming the approach.

• Example 2:

  • A fully populated grid with rows of 1s such as [[1,1,1],[1,1,1],[1,1,1]] provides multiple combination possibilities across rows, confirming the importance of systematic pairwise checks and counting.

• Example 3:

  • The provided row of [[1,1,1,1]] reminds us of the non-existence of rectangles in single-row scenarios regardless of the number of 1s, underscoring the necessity of having at least two rows for a rectangle to form.

Through these analyses, one can grasp how different grid configurations impact the potential for forming rectangles and adapt the counting methodology appropriately within the given constraints.

Solutions

class ShapeFinder {
    public int countRectangles(int[][] board) {
        List<List<Integer>> activeRows = new ArrayList<>();
        int countOnes = 0;
        for (int row = 0; row < board.length; ++row) {
            activeRows.add(new ArrayList());
            for (int col = 0; col < board[row].length; ++col)
                if (board[row][col] == 1) {
                    activeRows.get(row).add(col);
                    countOnes++;
                }
        }

        int threshold = (int) Math.sqrt(countOnes);
        int result = 0;
        Map<Integer, Integer> pairCount = new HashMap<>();

        for (int row = 0; row < board.length; ++row) {
            if (activeRows.get(row).size() >= threshold) {
                Set<Integer> currentSet = new HashSet(activeRows.get(row));

                for (int nextRow = 0; nextRow < board.length; ++nextRow) {
                    if (nextRow <= row && activeRows.get(nextRow).size() >= threshold) {
                        continue;
                    }
                    int matches = 0;
                    for (int item: activeRows.get(nextRow)) {
                        if (currentSet.contains(item)) {
                            matches++;
                        }
                    }
                    result += matches * (matches - 1) / 2;
                }
            } else {
                for (int first = 0; first < activeRows.get(row).size(); ++first) {
                    int col1 = activeRows.get(row).get(first);
                    for (int second = first + 1; second < activeRows.get(row).size(); ++second) {
                        int col2 = activeRows.get(row).get(second);
                        int code = 200 * col1 + col2;
                        int previousCount = pairCount.getOrDefault(code, 0);
                        result += previousCount;
                        pairCount.put(code, previousCount + 1);
                    }
                }
            }
        }
        return result;
    }
}