Problem Statement

Given a matrix, the task is to modify it in-place such that if an element in the original matrix is 0, its entire row and column are set to 0 in the modified matrix.

LeetCode

https://leetcode.com/problems/set-matrix-zeroes/description/

Constraints

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

Examples

Example 1:

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

Example 2:

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

Different Approaches

1️⃣ Brute Force Approach (using extra space)

Intuition:

We can create a copy of the original matrix, and then iterate over the original matrix, as soon as we encounter 0 in any cell, mark the entire row and column as 0 for the corresponding cell in the copied matrix. At last copy the contents of copied matrix back to original matrix.

Approach:

1. Traverse the original matrix.
   1. If 0 is encountered in cell:
      1. Mark the entire row and entire col as 0 for the cell in copied matrix.
2. Copy the updated matrix back to the original.

Code:

class Solution {
public:

    // Helper function to mark the entire row as 0
    void markRow(vector<vector<int>>& matrix, int row) {
        for (int col = 0; col < matrix[0].size(); col++) {
            matrix[row][col] = 0;
        }
    }

    // Helper function to mark the entire column as 0
    void markCol(vector<vector<int>>& matrix, int col) {
        for (int row = 0; row < matrix.size(); row++) {
            matrix[row][col] = 0;
        }
    }

    // Main function to set matrix zeroes
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();       // Total number of rows
        int m = matrix[0].size();    // Total number of columns

        // Create a copy of the original matrix
        // This is needed so we don't overwrite data in the original matrix while scanning it
        vector<vector<int>> copy = matrix;

        // Step 1: Traverse the original matrix to find zeros
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {

                // If we find a 0 in the original matrix,
                // we mark its entire row and column in the copy
                if (matrix[row][col] == 0) {
                    markRow(copy, row);   // Set entire row to 0 in the copy
                    markCol(copy, col);   // Set entire column to 0 in the copy
                }
            }
        }

        // Step 2: Copy the updated matrix back to the original matrix
        // This applies the row and column updates we made in the copy
        for (int row = 0; row < n; row++) {
            for(int col = 0; col < m; col++) {
                matrix[row][col] = copy[row][col];
            }
        }
    }
};

Complexity Analysis:

• Time Complexity:O(m * n * (m + n))
  • Because for each 0 element, we mark a full row and a column.
• Space Complexity:O(m * n)
  • Due to the copy of entire matrix

2️⃣ Better Approach (Using two extra arrays)

Intuition:

• Instead of marking entire rows and column, we use two arrays, row and col, to mark the rows and columns that contain zeroes.
• We iterate through the matrix to identify zero-containing cells and mark the corresponding indices in the row and col arrays.
• After marking, we traverse the matrix again and set the value of cells to 0 if their corresponding row or column is marked in the row or col array.

Algorithm:

1. First, we will declare two arrays: a row array of size N and a col array of size M and both are initialized with 0.
2. Then, we will use two loops(nested loops) to traverse all the cells of the matrix.
3. If any cell (i,j) contains the value 0, we will mark ith index of row array i.e. row[i] and jth index of col array col[j] as 1. It signifies that all the elements in the ith row and jth column will be 0 in the final matrix.
4. We will perform step 3 for every cell containing 0.
5. Finally, we will again traverse the entire matrix and we will put 0 into all the cells (i, j) for which either row[i] or col[j] is marked as 1.
6. Thus we will get our final matrix.

Code:

#include <bits/stdc++.h>
using namespace std;

// Function to set matrix zeroes
vector<vector<int>> zeroMatrix(vector<vector<int>> &matrix, int n, int m) {

    int row[n] = {0}; // Array to mark rows that should be zeroed
    int col[m] = {0}; // Array to mark columns that should be zeroed

    // Step 1: Traverse the matrix to find zeroes
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            // If a cell is 0, mark its row and column
            if (matrix[i][j] == 0) {
                row[i] = 1;  // Mark the i-th row
                col[j] = 1;  // Mark the j-th column
            }
        }
    }

    // Step 2: Traverse the matrix again and update cells
    // If either the row or column of a cell is marked, set it to 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }

    // Return the updated matrix
    return matrix;
}

int main()
{
    // Input matrix
    vector<vector<int>> matrix = {
        {1, 1, 1},
        {1, 0, 1},
        {1, 1, 1}
    };

    int n = matrix.size();        // Number of rows
    int m = matrix[0].size();     // Number of columns

    // Call the function
    vector<vector<int>> ans = zeroMatrix(matrix, n, m);

    // Print the final matrix
    cout << "The Final matrix is: \n";
    for (auto it : ans) {
        for (auto ele : it) {
            cout << ele << " ";
        }
        cout << "\n";
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2 * (N * M)), where N = number of rows in the matrix and M = number of columns in the matrix.
  • We are traversing the entire matrix 2 times and each traversal is taking O(N * M) time.
• Space Complexity: O(N) + O(M), where N = Number of rows in the matrix and M = number of columns in the matrix.
  • O(N) for using the row array.
  • O(M) for using the column array.

3️⃣ Optimal Approach

💡 Intuition:

The optimal approach for setting zeroes in a matrix involves utilizing the first row and first column of the matrix to mark the rows and columns that need to be zeroed out. This approach allows us to achieve the task in constant space complexity without using any additional data structures.

If we naively mark all rows and columns as zeroes immediately upon encountering a 0, we’ll mistakenly zero out more rows and columns than needed (because we modify the matrix while scanning it).
To avoid this, we need to:

1. Mark the rows and columns that should become zero.
2. Only apply the zeroes after the marking is done.

To do this efficiently without extra space, we can use the first row and first column of the matrix itself as storage for these marks.

Approach:

1. Check if the first row and first column contain any zero
   1. Use two boolean flags:
      1. isFirstRowZero: true if any element in the first row is 0
      2. isFirstColZero: true if any element in the first column is 0
2. Use first row and first column as markers
   1. For each element from (1,1) to (n-1, m-1):
      1. If it's 0, set:
         1. matrix[i][0] = 0 (to mark the row)
         2. matrix[0][j] = 0 (to mark the column)
3. Apply zeroes based on markers
   1. For every cell from (1,1) to (n-1, m-1), if its row or column is marked (i.e., matrix[i][0] == 0 or matrix[0][j] == 0), set it to 0.
4. Zero the first row and column (if needed)
   1. If isFirstRowZero is true, zero the entire first row.
   2. If isFirstColZero is true, zero the entire first column.

Code:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        // Step 1: Check if the first row has any zero
        bool isFirstRowZero = false;
        for (int col = 0; col < cols; col++) {
            if (matrix[0][col] == 0) {
                isFirstRowZero = true;
                break;
            }
        }

        // Step 2: Check if the first column has any zero
        bool isFirstColZero = false;
        for (int row = 0; row < rows; row++) {
            if (matrix[row][0] == 0) {
                isFirstColZero = true;
                break;
            }
        }

        // Step 3: Use first row and column as markers
        // If matrix[row][col] == 0, mark its row and column in first row and column
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0; // mark row
                    matrix[0][col] = 0; // mark column
                }
            }
        }

        // Step 4: Set matrix cells to 0 based on markers in first row and column
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }

        // Step 5: If the first row originally had a 0, set entire first row to 0
        if (isFirstRowZero) {
            for (int col = 0; col < cols; col++) {
                matrix[0][col] = 0;
            }
        }

        // Step 6: If the first column originally had a 0, set entire first column to 0
        if (isFirstColZero) {
            for (int row = 0; row < rows; row++) {
                matrix[row][0] = 0;
            }
        }
    }
};

Complexity Analysis:

• Time Complexity: O(2 * (m * n)), where n = number of rows in the matrix, and m = number of columns in the matrix.
  • First pass to scan matrix: O(m * n)
  • Second pass to apply zeroes: O(m * n)
  • Final pass for first row/col: O(m + n)
• Space Complexity: O(1)
  • As we are not using any extra space.