menu

[LeetCode] 073. Set Matrix Zeroes

Problem

073. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]

Example 2:

Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]

Follow up:

  • A straight forward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Approach 1: (My Solution: Additional Memory [Space $O(M+N)$])

Idea

  • Save the row and column indices into sets;
  • Loop the sets to make those lines to zeroes.

Solution

class Solution1:
    def setZeroes(self, matrix):
        """ 
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        set_i, set_j = set(), set()
        m, n = len(matrix[0]), len(matrix)
        for i, row in enumerate(matrix):
            for j, val in enumerate(row):
                if val == 0:
                    set_i.add(i)
                    set_j.add(j)
        for i in set_i:
            for j in range(m):
                matrix[i][j] = 0
        for j in set_j:
            for i in range(n):
                matrix[i][j] = 0
        return

Complexity

  • Time: $O(MN)$ where $M,N$ are the width and height of the matrix.
  • Space: $O(M+N)$

Approach 2: Space Complexity $O(1)$ *

Idea

The inefficiency in the second approach is that we might be repeatedly setting a row or column even if it was set to zero already. We can avoid this by postponing the step of setting a row or a column to zeroes.

We can rather use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero. This means for every cell instead of going to $\overline{M+N}$ cells and setting it to zero we just set the flag in two cells.

Solution

class Solution2:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        r, c = len(matrix), len(matrix[0])
        r0, c0 = all(matrix[0]), all([row[0] for row in matrix])
        for i in range(1, r):
            for j in range(1, c):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(1, r):
            if matrix[i][0] == 0:
                for j in range(1, c):
                    matrix[i][j] = 0
        for j in range(1, c):
            if matrix[0][j] == 0:
                for i in range(1, r):
                    matrix[i][j] = 0
        if not c0:
            for i in range(r):
                matrix[i][0] = 0
        if not r0:
            for j in range(c):
                matrix[0][j] = 0
        return

Complexity

  • Time: $O(MN)$ where $M,N$ are the width and height of the matrix.
  • Space: $O(1)$



KF

Comments