750. Number Of Corner Rectangles

Approach 1: Hash Map

from collections import defaultdict
class Solution(object):
    def countCornerRectangles(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        R, C = len(grid), len(grid[0])
        if R == 1 or C == 1:
            return 0
        rs = defaultdict(set)
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 1:
                    rs[i].add(j)
        count = 0
        rsl = {}
        for i in rs:
            rsl[i] = len(rs[i])
        for i in rs:
            for j in rs:
                if i != j:
                    n = len(rs[i] - rs[j])
                    if n != rsl[i]:
                        n = rsl[i] - n
                        count += (n * (n-1))/2
        return count/2

We start off by indexing the matrix and converting it into a dictionary, where the positions of all the ones are stored in a hash map. The key is the row number and the value associated with that is a set of column numbers that have a 1 in that row.

After that we look for rows that have common indices and append the number of squares that can be formed using the number of common indices. That number can be found by a bit of math. If n is the number of common indices, then nC2 or n Choose 2 is the number of rectangles that can be formed with those.

We keep a counter that keeps track of the number of rectangles we've seen.

Since we're double counting [(i,j) and (j,i) will both be added] I divide by 2 before returning

Time Complexity: O(R*C^2)

Space Complexity: O(R*C)

Approach 2: Minor optimization to approach 1

class Solution(object):
    def countCornerRectangles(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        R, C = len(grid), len(grid[0])
        if R == 1 or C == 1:
            return 0
        rs = {}
        for i in range(R):
            rs[i] = set()
            for j in range(C):
                if grid[i][j] == 1:
                    rs[i].add(j)
        count = 0
        rsl, rows, le = {}, [], 0
        for i in rs:
            rsl[i] = len(rs[i])
            rows.append(i)
            le += 1
        for i in range(le):
            for j in range(i+1, le):
                n = rsl[rows[i]] - len(rs[rows[i]] - rs[rows[j]])
                count += (n * (n-1))/2
        return count

Very minor improvement, only went from 63% to 72% but stopped double counting and removed an external library

Time Complexity: O(R*C^2)

Space Complexity: O(R*C)