Number Of Corner Rectangles — LeetCode 750 Python Solution
MediumLeetCode PremiumArrayMathDynamic ProgrammingMatrix
- Problem
- #750
- Pattern
- Matrix and Grid
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an m x n integer matrix grid where each entry is only 0 or 1, return the number of corner rectangles. A corner rectangle is four distinct 1's on the grid that forms an axis-aligned rectangle.
Example
- 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].
Python solution
Python
class Solution:
def countCornerRectangles(self, grid: List[List[int]]) -> int:
ans = 0
cnt = Counter()
n = len(grid[0])
for row in grid:
for i, c1 in enumerate(row):
if c1:
for j in range(i + 1, n):
if row[j]:
ans += cnt[(i, j)]
cnt[(i, j)] += 1
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(m \times n^2) |
| Space | O(n^2) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 750. Number Of Corner Rectangles is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 750. Number Of Corner Rectangles?
- LeetCode 750. Number Of Corner Rectangles is rated Medium on LeetCode.
- What is the time complexity of LeetCode 750. Number Of Corner Rectangles?
- The Python solution on this page runs in O(m \times n^2).
- What is the space complexity of LeetCode 750. Number Of Corner Rectangles?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 750. Number Of Corner Rectangles cover?
- LeetCode 750. Number Of Corner Rectangles is tagged Array, Math, Dynamic Programming and Matrix on LeetCode.
- Is LeetCode 750. Number Of Corner Rectangles a premium problem?
- Yes. LeetCode 750. Number Of Corner Rectangles is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.