Leetcode 0750 Number Of Corner Rectangles

Problem statement

https://leetcode.com/problems/number-of-corner-rectangles/

Solution

Iterate over each row of table and keep pairs of coordinates, where both values equal to 1, put them to counter. In the end, for each element of counter calculate i*(i-1)/2.

Complexity

Time complexity is O(n^2m), space complexity is O(n^2) (or O(m^2n)/O(m^2)).

Code

class Solution:
    def countCornerRectangles(self, grid):
        d = Counter()
        
        for row in grid:
            for t in combinations([i for i, t in enumerate(row) if t == 1], 2):
                d[t] += 1
                
        return sum(i*(i-1)//2 for i in d.values())