CODEWITHSUNDEEP
pythonpython-3.xtuplestime-complexitybig-o
Jeb
Jeb

Reputation: 170

Explain the time and space complexity in this solution to generating zero matrix

Below is an answer to the following prompt:

Write an algo such that if an element in an M x N matrix is 0, its entire column and row are set to zero.

FYI: I realize there are more optimal solutions; I want to know what the time and space complexity are for this answer.

Please correct me if I'm wrong, but my understanding is that the crude time complexity of this is O(MN + K(N + M)) where k is the length of the list of zero position tuples that gets iterated through. But K will always be less than N * M, so can this be broken down to disregard K? Or am I completely off base here?

I'm not sure about space. I know that tuples take up less memory than lists, but does it matter? Would it be O(MN)?

def zero_matrix(matrix):
    if not matrix: return matrix

    zero_elem = []
    for (i,row) in enumerate(matrix):
        for (j,num) in enumerate(row):
            if num == 0: zero_elem.append((i,j))

    if not zero_elem or len(zero_elem) == len(matrix) * len(matrix[0]): 
        return matrix

    for (row, col) in zero_elem:
        matrix[row] = [0 for num in matrix[row]]
        for row in matrix:
            row[col] = 0

    return matrix

Thanks in advance!

Upvotes: 0

Views: 270

Answers (1)

Jacob Steinebronn
Jacob Steinebronn

Reputation: 863

I know that tuples take up less memory than lists, but does it matter?

Not for Big-O notation. They are both linear memory (If I understand correctly) so the complexity is not affected by this.

Your zero_elem list will have O(MN) memory, since it will have at most MN tuples of constant length.

As for your time complexity, you were on the right track. However, the full runtime would be O(MN(N+M)) since your matrix could simply be all zeros (or order MN zeros), which would require you iterating over every row and column order MN times.

If you wanted a more optimized solution, this can be done quite easily in O(MN) time and O(M+N) space. You could probably push an O(1) memory, but I don't see any reason to do so.

Upvotes: 1

Related Questions