Welcome to Subscribe On Youtube

Question

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

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

 

Example 1:

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

Example 2:

Input: matrix = [[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]]

 

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

 

Follow up:

  • A straightforward 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?

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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++;
    	            }
    	        }
    	    }
    	}
    }
    
    ############
    
    class Solution {
        public void setZeroes(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            boolean[] rows = new boolean[m];
            boolean[] cols = new boolean[n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0) {
                        rows[i] = true;
                        cols[j] = true;
                    }
                }
            }
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (rows[i] || cols[j]) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
    
  • // 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
    
    
  • func setZeroes(matrix [][]int) {
    	m, n := len(matrix), len(matrix[0])
    	rows := make([]bool, m)
    	cols := make([]bool, n)
    	for i, row := range matrix {
    		for j, v := range row {
    			if v == 0 {
    				rows[i] = true
    				cols[j] = true
    			}
    		}
    	}
    	for i := 0; i < m; i++ {
    		for j := 0; j < n; j++ {
    			if rows[i] || cols[j] {
    				matrix[i][j] = 0
    			}
    		}
    	}
    }
    
  • /**
     Do not return anything, modify matrix in-place instead.
     */
    function setZeroes(matrix: number[][]): void {
        let m = matrix.length,
            n = matrix[0].length;
        let c0 = false,
            r0 = false;
        // 遍历第一行
        for (let i = 0; i < m; i++) {
            if (!matrix[i][0] && !c0) {
                c0 = true;
            }
        }
        // 第一列
        for (let j = 0; j < n; j++) {
            if (!matrix[0][j] && !r0) {
                r0 = true;
            }
        }
        // 用第一行、第一列标记全部
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // set
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        // set 第一列
        if (c0) {
            for (let i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        // 第一行
        if (r0) {
            for (let j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
    
    
  • /**
     * @param {number[][]} matrix
     * @return {void} Do not return anything, modify matrix in-place instead.
     */
    var setZeroes = function (matrix) {
        const m = matrix.length;
        const n = matrix[0].length;
        const rows = new Array(m).fill(false);
        const cols = new Array(n).fill(false);
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    };
    
    
  • public class Solution {
        public void SetZeroes(int[][] matrix) {
            int m = matrix.Length, n = matrix[0].Length;
            bool i0 = matrix[0].Contains(0), j0 = false;
            for (int i = 0; i < m; ++i) {
                if (matrix[i][0] == 0) {
                    j0 = true;
                    break;
                }
            }
            for (int i = 1; i < m; ++i) {
                for (int j = 1; j < n; ++j) {
                    if (matrix[i][j] == 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            for (int i = 1; i < m; ++i) {
                for (int j = 1; j < n; ++j) {
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                        matrix[i][j] = 0;
                    }
                }
            }
            if (i0) {
                for (int j = 0; j < n; ++j) {
                    matrix[0][j] = 0;
                }
            }
            if (j0) {
                for (int i = 0; i < m; ++i) {
                    matrix[i][0] = 0;
                }
            }
        }
    }
    

All Problems

All Solutions