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

The requirement of this question is to use O(1) space, then we cannot create a new array. We consider using the first row and first column of the original array to record whether each row and column has 0.

  • Scan the first row and first column first, if there is 0, set the respective flag to true
  • Then scan to remove the entire array of the first row and first column, if there is 0, assign 0 to the corresponding number in the first row and first column
  • Traverse the entire array again except the first row and first column. If one of the corresponding numbers in the first row and the first column is 0, assign the current value to 0
  • Finally update the first row and first column according to the flag in the first row and first column

Code

Java

  • 
    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(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
    
    

All Problems

All Solutions