750. Number Of Corner Rectangles

Problem Statement

link: LeetCode.cn LeetCode 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. Note that only the corners need to have the value 1. Also, all four 1’s used must be distinct.

Example:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]] Output: 9

Input: grid = [[1,1,1,1]] Output: 0

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].

Solution Approach

The solution uses a dictionary to count pairs of columns with ‘1’s in the same row, then iterates through the grid to accumulate the number of rectangles that can be formed by these column pairs across different rows.

Algorithm

1. Iterate through each row of the grid to identify pairs of columns that both contain ‘1’s.
2. Use a dictionary to track how often each column pair occurs across different rows.
3. For each new occurrence of a column pair, add the count of previous occurrences to the result, representing the number of rectangles that can be formed with that pair.

Implement

    class Solution:
  def countCornerRectangles(self, grid: List[List[int]]) -> int:
      count = collections.Counter()
      ans = 0
      for row in grid:
          for c1, v1 in enumerate(row):
              if v1:
                  for c2 in range(c1 + 1, len(row)):
                      if row[c2]:
                          ans += count[c1, c2]
                          count[c1, c2] += 1
      return ans
  

    
    

Twitter  facebook  Email