O(1) space, Use only the first row that has a 0 to store 0s for column


  • 0
    H

    Unlike the most popular answer which uses the first row and first column to store the 0s.
    I use the first row that has a 0 to store 0s for columns, and update the rows that has 0 in time (except the first one, which is updated at last.)

    class Solution(object):
        def setZeroes(self, matrix):
            # Use the first row that has 0 to store columns that has 0
            row = -1
            for i in xrange(len(matrix)):
                rowHasZero = False
                for j in xrange(len(matrix[0])):
                    if matrix[i][j] == 0:
                        if row < 0:
                            row = i
                        rowHasZero = True
                        matrix[row][j] = 0
                if rowHasZero and row != i:
                    for j in xrange(len(matrix[0])):
                        matrix[i][j] = 0
    
            # update columns and first row
            if row >= 0:
                for j in xrange(len(matrix[0])):
                    if matrix[row][j] == 0:
                        for i in xrange(len(matrix)):
                            matrix[i][j] = 0
                    else:
                        matrix[row][j] = 0
    

Log in to reply
 

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