Set Matrix Zeroes - Naukri Code 360

Introduction

In computer programming, working with matrices is a common task. One interesting problem that developers often encounter is setting specific elements of a matrix to zero based on certain conditions. This problem is known as "set matrix zeroes."

In this article, we will discuss the set matrix zeroes problem, understand its requirements, & discuss different approaches to solve it efficiently. We will also see the code implementation, just to make it easier to understand.

Problem Statement

The set matrix zeroes problem can be stated as follows: Given a matrix of integers, if any element in the matrix is zero, set its entire row & column to zeroes. In other words, if a cell in the matrix contains a zero, we need to update all the cells in the same row & column to zero as well. The goal is to modify the matrix in place, without using any additional space. This problem tests our ability to efficiently manipulate matrices & handle the propagation of zeroes across rows & columns. It requires careful consideration of the order in which we update the cells to avoid overwriting important information.

Examples

Let's consider a few examples to clarify the problem & its expected output.

Example 1

Input:

[
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]

Output:

[
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

In the input matrix, the element at position (1, 1) is zero. Therefore, we set all the elements in the second row & second column to zero.

Example 2

Input

[
  [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]
]

In this example, the input matrix contains two zeroes at positions (0, 0) & (0, 3). As a result, we set all the elements in the first row & the elements in the first & fourth columns to zero.

Naive Approach

The naive approach to solving the set matrix zeroes problem is straightforward but inefficient in terms of space complexity.

Let’s see how it works:

1. Create two boolean arrays, `rowZero` & `colZero`, to keep track of the rows & columns that need to be set to zero.

2. Iterate through the matrix & mark the corresponding entries in `rowZero` & `colZero` as `true` whenever a zero is encountered.

3. Iterate through the matrix again & set the elements to zero if their corresponding row or column is marked as `true` in `rowZero` or `colZero`.

For example :

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> rowZero(m, false);
        vector<bool> colZero(n, false);
        
        // Mark the rows & columns that need to be set to zero
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowZero[i] = true;
                    colZero[j] = true;
                }
            }
        }
        
        // Set the elements to zero based on the marked rows & columns
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rowZero[i] || colZero[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

The naive approach has a time complexity of O(m * n), where m is the number of rows & n is the number of columns in the matrix. However, it requires additional space of O(m + n) to store the `rowZero` & `colZero` arrays.

Note: While the naive approach solves the problem, it is not the most efficient solution.

Better Approach

To solve the set matrix zeroes problem more efficiently, we can use the first row & first column of the matrix itself to store the information about which rows & columns need to be set to zero. This approach optimizes the space complexity to O(1) while maintaining the time complexity of O(m * n).

Let’s see how it works:

1. Use two boolean variables, `firstRow` & `firstCol`, to store whether the first row & first column should be set to zero.

2. Iterate through the matrix starting from the second row & second column. If an element is zero, mark the corresponding cell in the first row & first column as zero.

3. Iterate through the matrix again, starting from the second row & second column. If the corresponding cell in the first row or first column is marked as zero, set the current element to zero.

4. Finally, check if `firstRow` is true & set all elements in the first row to zero. Similarly, check if `firstCol` is true & set all elements in the first column to zero.

For example :

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        
        // Check if the first row contains any zeroes
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRow = true;
                break;
            }
        }
        
        // Check if the first column contains any zeroes
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstCol = true;
                break;
            }
        }
        
        // Mark the corresponding cells in the first row & first column as zero
        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;
                }
            }
        }
        
        // Set the elements to zero based on the marks in the first row & first column
        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;
                }
            }
        }        
        // Set the first row to zero if necessary
        if (firstRow) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }        
        // Set the first column to zero if necessary
        if (firstCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

This approach efficiently solves the set matrix zeroes problem with a time complexity of O(m * n) & a space complexity of O(1). By using the first row & first column to store the information, we avoid the need for additional arrays, making the solution more space-efficient.

Code Implementation

C++
Java
JavaScript
Python

C++

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool firstRow = false, firstCol = false;
        
        // Check if the first row contains any zeroes
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRow = true;
                break;
            }
        }
        
        // Check if the first column contains any zeroes
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstCol = true;
                break;
            }
        }
        
        // Mark the corresponding cells in the first row & first column as zero
        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;
                }
            }
        }
        
        // Set the elements to zero based on the marks in the first row & first column
        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;
                }
            }
        }
        
        // Set the first row to zero if necessary
        if (firstRow) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Set the first column to zero if necessary
        if (firstCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

// Helper method to print the matrix
void printMatrix(vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int element : row) {
            cout << element << " ";
        }
        cout << endl;
    }
}

int main() {
    Solution solution;
    
    // Example input
    vector<vector<int>> matrix = {
        {1, 1, 1, 0},
        {4, 5, 6, 7},
        {8, 9, 0, 2},
        {3, 4, 5, 6}
    };
    
    // Print original matrix
    cout << "Original matrix:" << endl;
    printMatrix(matrix);
    
    // Apply the setZeroes method
    solution.setZeroes(matrix);
    
    // Print the modified matrix
    cout << "Matrix after calling setZeroes:" << endl;
    printMatrix(matrix);
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Example input
        int[][] matrix = {
            {1, 1, 1, 0},
            {4, 5, 6, 7},
            {8, 9, 0, 2},
            {3, 4, 5, 6}
        };
        
        // Print original matrix
        System.out.println("Original matrix:");
        printMatrix(matrix);
        
        // Apply the setZeroes method
        solution.setZeroes(matrix);
        
        // Print the modified matrix
        System.out.println("Matrix after calling setZeroes:");
        printMatrix(matrix);
    }
    
    // Helper method to print the matrix
    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int element : row) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        
        // Check if the first row contains any zeroes
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRow = true;
                break;
            }
        }
        
        // Check if the first column contains any zeroes
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstCol = true;
                break;
            }
        }
        
        // Mark the corresponding cells in the first row & first column as zero
        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;
                }
            }
        }
        
        // Set the elements to zero based on the marks in the first row & first column
        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;
                }
            }
        }
        
        // Set the first row to zero if necessary
        if (firstRow) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Set the first column to zero if necessary
        if (firstCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

JavaScript

function setZeroes(matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let firstRow = false, firstCol = false;
    
    // Check if the first row contains any zeroes
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            firstRow = true;
            break;
        }
    }
    
    // Check if the first column contains any zeroes
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            firstCol = true;
            break;
        }
    }
    
    // Mark the corresponding cells in the first row & first column as zero
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    
    // Set the elements to zero based on the marks in the first row & first column
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // Set the first row to zero if necessary
    if (firstRow) {
        for (let j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
    
    // Set the first column to zero if necessary
    if (firstCol) {
        for (let i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
}

// Helper method to print the matrix
function printMatrix(matrix) {
    for (let row of matrix) {
        console.log(row.join(' '));
    }
}

// Example input
let matrix = [
    [1, 1, 1, 0],
    [4, 5, 6, 7],
    [8, 9, 0, 2],
    [3, 4, 5, 6]
];

// Print original matrix
console.log("Original matrix:");
printMatrix(matrix);

// Apply the setZeroes method
setZeroes(matrix);

// Print the modified matrix
console.log("Matrix after calling setZeroes:");
printMatrix(matrix);

You can also try this code with Online Javascript Compiler

Run Code

Python

class Solution:
    def setZeroes(self, matrix):
        m = len(matrix)
        n = len(matrix[0])
        firstRow = False
        firstCol = False
        
        # Check if the first row contains any zeroes
        for j in range(n):
            if matrix[0][j] == 0:
                firstRow = True
                break
        
        # Check if the first column contains any zeroes
        for i in range(m):
            if matrix[i][0] == 0:
                firstCol = True
                break
        
        # Mark the corresponding cells in the first row & first column as zero
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        # Set the elements to zero based on the marks in the first row & first column
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        # Set the first row to zero if necessary
        if firstRow:
            for j in range(n):
                matrix[0][j] = 0
        
        # Set the first column to zero if necessary
        if firstCol:
            for i in range(m):
                matrix[i][0] = 0

# Helper method to print the matrix
def printMatrix(matrix):
    for row in matrix:
        print(' '.join(map(str, row)))

# Example input
matrix = [
    [1, 1, 1, 0],
    [4, 5, 6, 7],
    [8, 9, 0, 2],
    [3, 4, 5, 6]
]

# Print original matrix
print("Original matrix:")
printMatrix(matrix)

# Apply the setZeroes method
Solution().setZeroes(matrix)

# Print the modified matrix
print("Matrix after calling setZeroes:")
printMatrix(matrix)

You can also try this code with Online Python Compiler

Run Code

Output

Original matrix:
1 1 1 0 
4 5 6 7 
8 9 0 2 
3 4 5 6 
Matrix after calling setZeroes:
0 0 0 0 
4 5 0 0 
0 0 0 0 
3 4 0 0

Frequently Asked Questions

Can we use additional data structures like hash sets to solve this problem?

Yes, we can use additional data structures, but it would increase the space complexity. The approach discussed here optimizes both time & space complexity.

What if the matrix is empty or has only one row or one column?

The code handles these edge cases gracefully. If the matrix is empty, no modifications are needed. If the matrix has only one row or one column, the code will set the entire row or column to zeroes if necessary.

Can we solve this problem by creating a copy of the matrix?

Yes, we can create a copy of the matrix & use it to determine which cells should be set to zero. However, this approach would have a space complexity of O(m * n), which is not optimal.

Conclusion

In this article, we discussed the set matrix zeroes problem, where we need to modify a matrix such that if an element is zero, its entire row & column are set to zeroes. We explained a naive approach that uses additional arrays to store the row & column information, which results in a space complexity of O(m + n). However, we then presented a more efficient approach that optimizes the space complexity to O(1) by using the first row & first column of the matrix itself to store the necessary information. This approach achieves a time complexity of O(m * n) & a space complexity of O(1).
You can also check out our other blogs on Code360.