> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/math/750-number-of-corner-rectangles.md).

# 750 Number Of Corner Rectangles

## 750. [Number Of Corner Rectangles](https://leetcode.com/problems/number-of-corner-rectangles/description/)

## 1. Question

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

Acorner rectangleis 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`.

## 2. Implementation

(1)

思路: 1. 对于任意两行，找出它们在同一列都有1的个数count

2.然后我们从这些count中，任意选择两列作为矩形的边，根据组合公式，n里面取两个，公式为 n \* (n - 1) /2

```java
class Solution {
    public int countCornerRectangles(int[][] grid) {
        if  (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length, n = grid[0].length;

        int count = 0;
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                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;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(nm^2)，m为矩形的行数，n为矩形的列数，空间复杂度O(1)