Accepted O(m*n), O(m+n), O(1) python solution.


  • 1
    L

    O(m*n) solution, use a list to remember all zero.

    class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        zeros=[];
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(matrix[i][j]==0):
                    zeros.append((i,j));
    
        for p in zeros:
            for i in range(len(matrix)):
                matrix[i][p[1]]=0;
            for i in range(len(matrix[0])):
                matrix[p[0]][i]=0;
    

    O(m+n) solution, only need to remember rows and cols:

    class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        rows=set();
        columns=set();
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(matrix[i][j]==0):
                   rows.add(i);
                   columns.add(j);
    
        for row in rows:
            for i in range(len(matrix[0])):
                matrix[row][i]=0;
        for col in columns:
            for i in range(len(matrix)):
                matrix[i][col]=0;
    

    O(1) solution, Why we need a list to remember rows and cols?
    We can directly set the matrix row, col to a flag value like 9999.
    So here is the O(1) solution:

    class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        def setMatrix(row,col,matrix,val):
            matrix[row][col]=val;
            for i in range(len(matrix[0])):
                if(matrix[row][i]!=9999): # key point, to skip the other 9999, so we can process it later.
                    matrix[row][i]=val;
            for i in range(len(matrix)):
                if(matrix[i][col]!=9999):
                    matrix[i][col]=val;
    
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(matrix[i][j]==0):
                   matrix[i][j]=9999;
    
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(matrix[i][j]==9999):
                   setMatrix(i,j,matrix,0);

  • 0
    G

    what if the interviewer asks "if the matrix is very large and has all kinds of numbers you can use as flags"? i just wonder what the standard answer is for this kind of non-sense questions.


  • 0
    W

    @gilbertliu42 Well, I agree with your opinion about the flags. Yeah, if the origin matrix contains 9999, even INT_MAX or INT_MIN, this answer won't works. I have seen another friend using '.' as a flag, which is the same method. I think we should using first row and first col to store the information whether this row or col will be zero or not, which is my solution. It can achieve O(m*n) and O(1) space, but two pass. Any comments.


Log in to reply
 

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