Set Matrix Zeroes

Description

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

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?

 

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

Solution(javascript)

// O(m+n) space
// const setZeroes = function (matrix = []) {
//   const rows = {}
//   const columns = {}
//   for (let i = 0; i < matrix.length; i++) {
//     for (let j = 0; j < matrix[i].length; j++) {
//       if (matrix[i][j] === 0) {
//         rows[i] = true
//         columns[j] = true
//       }
//     }
//   }
//   Object.keys(rows).forEach((row) => {
//     matrix[row].forEach((v, index) => {
//       matrix[row][index] = 0
//     })
//   })
//   Object.keys(columns).forEach((column) => {
//     matrix.forEach((v, index) => {
//       matrix[index][column] = 0
//     })
//   })
//   return matrix
// }

// O(1) space 第一行和第一列的元素设置标志位，但是要注意第一个元素
const setZeroes = function (matrix = []) {
  let isRow = false
  let isColumn = false
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === 0) {
        if (j === 0) {
          isColumn = true
        }
        if (i === 0) {
          isRow = true
        }
        matrix[i][0] = 0
        matrix[0][j] = 0
      }
    }
  }

  for (let i = 1; i < matrix.length; i++) {
    for (let j = 1; j < matrix[i].length; j++) {
      if (matrix[0][j] === 0 || matrix[i][0] === 0) {
        matrix[i][j] = 0
      }
    }
  }
  if (isRow) {
    for (let i = 0; i < matrix[0].length; i++) {
      matrix[0][i] = 0
    }
  }
  if (isColumn) {
    for (let i = 0; i < matrix.length; i++) {
      matrix[i][0] = 0
    }
  }
  return matrix
}