Yet another O(1) space solution


  • 0
    F

    I have to say the first_row, first_column solution in the discussions is the best idea in my opinion. However, here I present another O(1) space, assuming that -2147483647 is not an element in the matrix, so I can treat it as a placeholder.

    The idea is we do rows and columns separately.

    First, we do rows, if there are zeros in a row[i],

    a) if matrix[i][j] = 0, we assign matrix[i][j] = placeholder (-2147483647)

    b) if matrix[i][j] != 0, we assign matrix[i][j] = 0

    Then, we do columns, in the matrix, if there is an element matrix[i][j] == placeholder, then I assign the whole column as 0s.

    The extra space is O(1)

    The time complexity is O(3mn + n)

    def set_zeroes(matrix)
        place_holder = -(1 << 32)
        #fill rows
        for i in 0...matrix.length
            count = 0
            matrix[i].each {|x| count += 1 if x === 0}
            if count > 0
                for j in 0...matrix[i].length
                    if matrix[i][j] === 0
                        matrix[i][j] = place_holder
                    else 
                        matrix[i][j] = 0
                    end
                end
            end
        end
        #fill columns
        for i in 0...matrix.length
            for j in 0...matrix[i].length
                if matrix[i][j] === place_holder
                    for k in 0...matrix.length
                        matrix[k][j] = 0
                    end
                end
            end
        end
        return nil
    end

  • 0
    L

    I thought of similar solution too. Use Interger_MAXVALUE as a magic number, for example in first round scan, when we meet 0, set all elements of its column and row to magic number. In second round, when we meet magic number, set it to 0. The only problem is we really shouldn't assume such magic number is not in the original matrix. What if a matrix contains all the integers? Later I came up with the first column first row method :)


  • 0
    F

    Yes, That is great.

    I do think that first-column first row idea is the best, but I didn't figure that out before I read the forum...I was a little disappointed to myself.


Log in to reply
 

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