Python solution


  • 0
    def countCornerRectangles(self, grid):
            n = len(grid[0])
            d = collections.Counter((i, j) for line in grid for i in range(n)
                                    for j in range(i + 1, n) if line[i] and line[j])
            return sum(x * (x - 1) / 2 for x in d.values())

  • 1

    Bit shorter and much faster (about 1200 ms instead of around 2800 ms or even TLE):

    def countCornerRectangles(self, grid):
        d = collections.Counter((i, j) for line in grid
                                for j in range(len(line)) if line[j]
                                for i in range(j) if line[i])
        return sum(x * (x - 1) / 2 for x in d.values())
    

    Another version, takes about 900 ms:

    def countCornerRectangles(self, grid):
        d = collections.Counter(ij for line in grid
                                for ij in itertools.combinations((i for i, v in enumerate(line) if v), 2))
        return sum(x * (x - 1) / 2 for x in d.values())
    

    And an very itertools-heavy version: https://discuss.leetcode.com/topic/114742/itertools-galore


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.