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 form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1’s used must be distinct.
Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]Output: 1Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Input: grid = [[1,1,1],[1,1,1],[1,1,1]]Output: 9Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Input: grid = [[1,1,1,1]]Output: 0Explanation: Rectangles must have four distinct corners.
from collections import Counterclass Solution: # Time: O(m * n^2) # Space: O(n^2) def count_corner_rectangles(self, grid: list[list[int]]) -> int: ans = 0 cnt: Counter[tuple[int, int]] = Counter() for row in grid: ones = [i for i, v in enumerate(row) if v] for a in range(len(ones)): for b in range(a + 1, len(ones)): pair = (ones[a], ones[b]) ans += cnt[pair] cnt[pair] += 1 return ans
