Question

Formatted question description: https://leetcode.ca/all/73.html

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]
]


click to show follow up.

Follow up:
    Did you use extra space?
    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?

@tag-array

Algorithm

To solve this question with O(1) space complexity, we cannot create a new array. Instead, we can use the first row and first column of the original array to record whether each row and column has a 0.

The following steps can be taken:

First, scan the first row and first column of the array. If a 0 is found, set the corresponding flag in the first row and first column to true.
Next, scan the entire array (excluding the first row and first column). If a 0 is found at position [i][j], assign 0 to the corresponding numbers in the first row and first column, i.e., set [0][j] and [i][0] to 0.
Traverse the entire array again (excluding the first row and first column). If [0][j] or [i][0] is 0, assign the current value to 0, i.e., set matrix[i][j] to 0.
Finally, update the first row and first column based on the flags in the first row and first column. If the flag in the first row is true, assign 0 to the corresponding numbers in the first row. Similarly, if the flag in the first column is true, assign 0 to the corresponding numbers in the first column.

Code

public class Set_Matrix_Zeroes {

	public class Solution {
	    public void setZeroes(int[][] matrix) {

	        if (matrix == null || matrix.length == 0) {
	            return;
	        }

	        int m = matrix.length;
	        int n = matrix[0].length;

	        // use first row and first column as marker
	        // first row/col itself 0 or not? use a boolean flag
	        boolean isFirstRowZero = false;
	        boolean isFirstColZero = false;

	        for (int i = 0; i < n; i++) {
	            if (matrix[0][i] == 0) {
	                isFirstRowZero = true;
	                break;
	            }
	        }

	        for (int i = 0; i < m; i++) {
	            if (matrix[i][0] == 0) {
	                isFirstColZero = true;
	                break;
	            }
	        }

	        for (int i = 1; i < m; i++) {
	            for (int j = 1; j < n; j++) {
	                if (matrix[i][j] == 0) {

	                    matrix[0][j] = 0;
	                    matrix[i][0] = 0;
	                }
	            }
	        }

	        // set 0: rest first, first-row/col last
	        for (int col = 1; col < n; col++) {
	            if (matrix[0][col] == 0) {

	                int i = 1;
	                while (i < m) {
	                    matrix[i][col] = 0;
	                    i++;
	                }
	            }
	        }
	        for (int row = 1; row < m; row++) {
	            if (matrix[row][0] == 0) {

	                int j = 1;
	                while (j < n) {
	                    matrix[row][j] = 0;
	                    j++;
	                }
	            }
	        }

	        if (isFirstRowZero) {
	            int j = 0;
	            while (j < n) {
	                matrix[0][j] = 0;
	                j++;
	            }
	        }
	        if (isFirstColZero) {
	            int i = 0;
	            while (i < m) {
	                matrix[i][0] = 0;
	                i++;
	            }
	        }
	    }
	}
}

// OJ: https://leetcode.com/problems/set-matrix-zeroes/
// Time: O(MN)
// Space: O(M + N)
class Solution {
public:
    void setZeroes(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<bool> row(M), col(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                row[i] = row[i] || A[i][j] == 0;
                col[j] = col[j] || A[i][j] == 0;
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (row[i] || col[j]) A[i][j] = 0;
            }
        }
    }
};

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        rows = [0] * m
        cols = [0] * n
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                if v == 0:
                    rows[i] = cols[j] = 1
        for i in range(m):
            for j in range(n):
                if rows[i] or cols[j]:
                    matrix[i][j] = 0

############

class Solution(object):
  def setZeroes(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: void Do not return anything, modify matrix in-place instead.
    """
    colZeroFlag = False
    for i in range(0, len(matrix)):
      if matrix[i][0] == 0:
        colZeroFlag = True
      for j in range(1, len(matrix[0])):
        if matrix[i][j] == 0:
          matrix[i][0] = matrix[0][j] = 0

    for i in reversed(range(0, len(matrix))):
      for j in reversed(range(1, len(matrix[0]))):
        if matrix[i][0] == 0 or matrix[0][j] == 0:
          matrix[i][j] = 0
      if colZeroFlag:
        matrix[i][0] = 0

73 - Set Matrix Zeroes

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions