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
-2³¹ <= matrix[i][j] <= 2³¹ - 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:

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++;
	            }
	        }
	    }
	}
}

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

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;
            }
        }
    }
}

73 - Set Matrix Zeroes

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions