O(mn) solution for python.


  • 0
    T
    def findBlackPixel(self, picture, N):
            if not picture: return 0
            m, n = len(picture), len(picture[0])
            # storing 'B' coordinates so the second pass is faster. Could be removed if memory is constrained.
            black_coordinates = []
            # storing # of 'B' in a row and a column. For all 'B' in the same column, we also need their row id,
            # and defaultdict is a convenient way to store it.
            row, col = [0] * m, collections.defaultdict(list)
            for i in xrange(m):
                for j in xrange(n):
                    if picture[i][j] == 'B':
                        black_coordinates.append( (i, j) )
                        row[i] += 1
                        col[j].append(i)
            count = 0
            for (i, j) in black_coordinates:
                #  -------    rule 1    --------------- rule 2, makesure all rows are the same using set-------
                if row[i] == N and len(col[j]) == N and len(set([tuple(picture[r]) for r in col[j]])) == 1:
                        count += 1
            return count
    

  • 0

    It's not O(mn) but O(m2n2). Think of a completely black picture of size N×N. For each of the N2 coordinates, you'll do N2 work.


Log in to reply
 

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