Leetcode Study Day 18

Set Matrix Zeroes

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

Solution

The solution is to move the elements with 0 value to the boundary of the martix, which is the first row and the first column specifically, then we can use the first row and the first column to mark the rows and columns that need to be set to 0.

Let’s breakdown the solution step by step:

1. Check if the first row and the first column contains 0. If so, we set two boolean variables isZeroCol and isZeroCol to true.

   int length = matrix[0].size();
   int height = matrix.size();
   bool isZeroCol = false;
   bool isZeroRow = false;
   // Check the first row
   for (int i = 0; i < length; i++){
       if(matrix[0][i] == 0){
           isZeroRow = true;
           break;
       }
   }
   
   // Check the first column
   for (int i = 0; i < height; i++){
       if(matrix[i][0] == 0){
           isZeroCol = true;
           break;
       }
   }

2. Iterate through the matrix, if the element is 0, set the first element of the row and the column to 0.

   // Check columns and rows except the first one
   for (int i = 1; i < height; i++){
       for (int j = 1; j < length; j++){
           if (matrix[i][j]==0){
               matrix[0][j] = 0;
               matrix[i][0] = 0;
           }
       }
   }

3. We check if there is any element in first row and first column is 0, if so, we set the whole row and column to 0.

   // Set columns and rows except the first one to 0
   for (int i = 1; i < height; i++){
       for (int j = 1; j < length; j++){
           if (matrix[0][j]==0)
               matrix[i][j] = 0;
           if (matrix[i][0]==0)
               matrix[i][j] = 0;
       }
   }

4. Finally, we set the first row and the first column to 0 if our boolean flag is true.

// Now set the first column if there exists 0 in first column
if (isZeroCol){
    for (int i = 0; i < height; i++)
        matrix[i][0] = 0;
}

// Now set the first row if there exists 0 in first row
if (isZeroRow){
    for (int i = 0; i < length; i++)
        matrix[0][i] = 0;
}

Full code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int length = matrix[0].size();
        int height = matrix.size();
        bool isZeroCol = false;
        bool isZeroRow = false;
        // Check the first row
        for (int i = 0; i < length; i++){
            if(matrix[0][i] == 0){
                isZeroRow = true;
                break;
            }
        }

        // Check the first column
        for (int i = 0; i < height; i++){
            if(matrix[i][0] == 0){
                isZeroCol = true;
                break;
            }
        }

        // Check columns and rows except the first one
        for (int i = 1; i < height; i++){
            for (int j = 1; j < length; j++){
                if (matrix[i][j]==0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        // Set columns and rows except the first one to 0
        for (int i = 1; i < height; i++){
            for (int j = 1; j < length; j++){
                if (matrix[0][j]==0)
                    matrix[i][j] = 0;
                if (matrix[i][0]==0)
                    matrix[i][j] = 0;
            }
        }

        // Now set the first column if there exists 0 in first column
        if (isZeroCol){
            for (int i = 0; i < height; i++)
                matrix[i][0] = 0;
        }

        // Now set the first row if there exists 0 in first row
        if (isZeroRow){
            for (int i = 0; i < length; i++)
                matrix[0][i] = 0;
        }
    }
};