Problem statement

https://leetcode.com/problems/set-matrix-zeroes/

Solution

The idea is to use first row and first column as indicator, if we need to set the whole corresponding column or row to zeros. We also keep r1 and c1` variables: do we need to update first column and/or first row in the end. So, we have the following steps:

  1. Create r1 and c1.
  2. Iterate through our matrix and if we see that for if element M[i][j] is equal to 0, we put both elements M[i][0] and M[0][j] to 0.
  3. Now, we updated all elements in first row and column, so we iterate our matrix once again: and if we see that one of elements M[i][0] or M[0][j] equal to 0, we make M[i][j] equal to 0`.
  4. Finally, we need to update first row and column, so we make them 0, if we have indicator r1 for row and c1 for column.

Complexity

Time complexity is O(mn), space is O(1).

Code

class Solution:
    def setZeroes(self, M):
        m, n = len(M[0]), len(M)
        r1 = any(M[0][j] == 0 for j in range(m))
        c1 = any(M[i][0] == 0 for i in range(n))
        for i in range(1, n):
            for j in range(1, m):
                if M[i][j] == 0: M[i][0] = M[0][j] = 0
                
        for i in range(1, n):
            for j in range(1, m):
                if M[i][0] * M[0][j] == 0: M[i][j] = 0
                
        if r1:
            for i in range(m): M[0][i] = 0
                
        if c1:
            for j in range(n): M[j][0] = 0