Python O(1) solution, 12 lines of code

  • 0

    A general principle to reduce space complexity is to take advantage of existing space. In this case, we embed the information of zero indexes into the matrix.
    Note we must keep distinction of two types of information in doing this: matrix elements and marked zeros. The two type of information shouldn't mess up with each other throughout the process.
    A small trick in choosing flag: any value outside the domain of matrix suffices. In a statically typed language one may choose max(maxtrix)+1 or min(matrix)-1. In Python one can simply choose None.

          def setZeroes(self, matrix):
            def setzeros(i,j):
                for m,n in chain(product(xrange(self.m),[j]), product([i],xrange(self.n))): 
                    if matrix[m][n] != None: # avoid messing up with marked zero
            def markzeros():
                for i,j in product(xrange(self.m),xrange(self.n)):
                    if matrix[i][j]==0: matrix[i][j]=None
            for i,j in product(xrange(self.m),xrange(self.n)):
                if matrix[i][j] == None: setzeros(i,j)

Log in to reply

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