Python: O(mn(m+n)) time and O(1) space


  • 0
    G
    class Solution(object):
        def setZeroes(self, matrix):
            rows = len(matrix)
            cols = len(matrix[0])
            zero = object()
            
            for i in xrange(rows):
                for j in xrange(cols):
                    if matrix[i][j] == 0:
                        matrix[i][j] = zero
            
            for i in xrange(rows):
                for j in xrange(cols):
                    if matrix[i][j] is zero:
                        for k in xrange(rows):
                            if matrix[k][j] is not zero:
                                matrix[k][j] = 0
                        for k in xrange(cols):
                            if matrix[i][k] is not zero:
                                matrix[i][k] = 0
                        matrix[i][j] = 0

  • 0
    A

    Your solution has O(mn(n+m)) time complexity


  • 0
    G

    right, sorry


Log in to reply
 

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