73. Set Matrix Zeroes

Set Matrix Zeroes

Problem Description

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?

Approach) Three Solution

var setZeroes = function(matrix) {
  let isCol = false, r = matrix.length, c = matrix[0].length;
  for (let i = 0; i < r; i++) {
    if (!matrix[i][0]) isCol = true;
    for (let j = 1; j < c; j++) {
      if (!matrix[i][j]) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      };
    }
  }
  for (let i = 1; i < r; i++) {
    for (let j = 1; j < c; j++) {
      if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
    }
  }
  if (!matrix[0][0]) {
    for (let j = 0; j < c; j++) matrix[0][j] = 0;
  }
  if (isCol) {
    for (let i = 0; i < r; i++) {
      matrix[i][0] = 0;
    }
  }
};

Here is a version where we use Sets to track 0's. A little extra space, but not a ton. Won't work if the interviewer challenges you to constant space though.

var setZeroes = function(matrix) {
  const rowSet = new Set(), colSet = new Set()
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (!matrix[i][j]) {
        rowSet.add(i);
        colSet.add(j);
      };
    }
  }
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (rowSet.has(i) || colSet.has(j)) matrix[i][j] = 0
    }
  }
};

Here is a version where we just deep-copy the array and go to town. This is the easiest imo and gets solid time complexity (Maybe slight redoing of the recursive calls if 0's overwrite cells more than once.). It Is the worst on space complexity though. Just depends what they're looking for and if Constant Space is make or break.

var setZeroes = function(matrix) {
  const copy = JSON.parse(JSON.stringify(matrix));
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (!copy[i][j]) traverse(i, j);
    }
  }
  
  function traverse(row, col, dir = 'all') {
    matrix[row][col] = 0;
    if (row - 1 >= 0 && (dir === 'all' || dir === 'up')) traverse(row - 1, col, 'up');
    if (row + 1 <= matrix.length - 1 && (dir === 'all' || dir === 'down')) traverse(row + 1, col, 'down');
    if (col - 1 >= 0 && (dir === 'all' || dir === 'left')) traverse(row, col - 1, 'left');
    if (col + 1 <= matrix[row].length - 1 && (dir === 'all' || dir === 'right')) traverse(row, col + 1, 'right');
  }
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 73. Set Matrix Zeroes

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!