Set Matrix Zeroes

72.4k
0

Given an m x n integer matrix matrix. If any element is 0, every element in that element's row and column must become 0. Modify the matrix in place.

Example 1

Input: matrix = [[1,2,0,4],[5,6,7,8],[9,0,11,12],[13,14,15,16]]

Output: [[0,0,0,0],[5,0,0,8],[0,0,0,0],[13,0,0,16]]

Explanation: The original zeros are at positions (0, 2) and (2, 1). Row 0, row 2, column 2, and column 1 are changed to zero.

Example 2

Input: matrix = [[0,1,2],[3,4,5],[6,0,8]]

Output: [[0,0,0],[0,0,5],[0,0,0]]

Explanation: The original zeros are at (0, 0) and (2, 1). The first row, third row, first column, and second column are cleared.

Brute Force Approach

Every zeroing decision must be based on the original matrix, not on cells that become zero later. A direct way to preserve that information is to keep a full copy of the matrix and use the copy only for identifying zeros.

When a zero is found in the copy, the corresponding row and column are cleared in the actual matrix. This is correct because the copy never changes. The cost is high because a row and a column may be cleared again for many different zero cells.

Algorithm

  • If the matrix has no rows, there is no cell to update; otherwise, read the row and column counts.

  • Store a full copy of the original matrix so later changes do not affect zero detection.

  • Inspect every cell in the copied matrix and identify each original zero.

  • For every original zero, set the matching row and the matching column in the actual matrix to zero.

  • After the last copied cell is inspected, the actual matrix contains all required zeros and the process terminates.

Dry Run

Brute Force

Brute Force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Updates the matrix after zeroing affected rows and columns.
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
// An empty matrix has no row or column to update.
if (rows == 0) {
return;
}
int cols = matrix[0].size();
vector<vector<int>> original = matrix;
// Original zeros must be read from the unchanged copy.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Only zeros present in the original matrix trigger clearing.
if (original[row][col] == 0) {
// Clear the entire affected row in the real matrix.
for (int c = 0; c < cols; c++) {
matrix[row][c] = 0;
}
// Clear the entire affected column in the real matrix.
for (int r = 0; r < rows; r++) {
matrix[r][col] = 0;
}
}
}
}
}
};
// Prints the matrix rows.
void printMatrix(const vector<vector<int>>& matrix) {
// Print each row on a separate line.
for (const vector<int>& row : matrix) {
for (int value : row) {
cout << value << " ";
}
cout << "\n";
}
}
// Driver code
int main() {
vector<vector<int>> matrix = {
{1, 2, 0, 4},
{5, 6, 7, 8},
{9, 0, 11, 12},
{13, 14, 15, 16}
};
// instance for class Solution
Solution sol;
sol.setZeroes(matrix);
printMatrix(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(m * n * (m + n)), because each of the m * n original cells may trigger clearing one full row and one full column.

Space Complexity: O(m * n), because a full copy of the matrix is stored.

Better Approach

Instead of storing every original value, only the rows and columns that must become zero need to be remembered. A row marker array records which rows contain an original zero, and a column marker array records the same information for columns.

After those markers are built, each cell can be updated by checking whether its row or column was marked. This avoids repeated row and column clearing, so the time improves while extra space is reduced to the marker arrays.

Algorithm

  • Create one marker array for rows and one for columns.

  • Inspect every matrix cell once and mark its row and column whenever an original zero is found.

  • Inspect every matrix cell again and decide its final value from the row and column markers.

  • Set a cell to zero when either its row or its column was marked.

  • The update ends after the second full matrix traversal, and the matrix itself stores the final answer.

Dry Run

Better Approach

Better Approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Updates the matrix after zeroing affected rows and columns.
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
// An empty matrix has no row or column to update.
if (rows == 0) {
return;
}
int cols = matrix[0].size();
vector<bool> zeroRows(rows, false);
vector<bool> zeroCols(cols, false);
// Record every row and column that contains an original zero.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// A zero marks both its row and its column.
if (matrix[row][col] == 0) {
zeroRows[row] = true;
zeroCols[col] = true;
}
}
}
// Apply the stored row and column markers to the matrix.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// A cell becomes zero when its row or column was marked.
if (zeroRows[row] || zeroCols[col]) {
matrix[row][col] = 0;
}
}
}
}
};
// Prints the matrix rows.
void printMatrix(const vector<vector<int>>& matrix) {
// Print each row on a separate line.
for (const vector<int>& row : matrix) {
for (int value : row) {
cout << value << " ";
}
cout << "\n";
}
}
// Driver code
int main() {
vector<vector<int>> matrix = {
{1, 2, 0, 4},
{5, 6, 7, 8},
{9, 0, 11, 12},
{13, 14, 15, 16}
};
// instance for class Solution
Solution sol;
sol.setZeroes(matrix);
printMatrix(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(m * n), because the matrix is scanned once to build markers and once to apply them.

Space Complexity: O(m + n), because one row marker array and one column marker array are stored.

Optimal Approach

The marker arrays can be replaced by storage already available inside the matrix. The first cell of each row can mark whether that row must become zero, and the first cell of each column can mark whether that column must become zero.

The first row and first column need special care because they are also used as marker storage. Their original zero status is saved before marking begins. After the inner cells are updated from the markers, the saved status decides whether the first row and first column should be cleared.

Algorithm

  • Record whether the first row or first column originally contains zero.

  • Inspect only the inner matrix cells and use the first cell of the same row and same column as zero markers.

  • Inspect the inner matrix cells again and set a cell to zero when its row marker or column marker is zero.

  • Clear the first row when it originally contained zero, and clear the first column when it originally contained zero.

  • The process terminates after these marker applications, and only constant extra variables are used.

Dry Run

Optimal

Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Updates the matrix after zeroing affected rows and columns.
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
// An empty matrix has no row or column to update.
if (rows == 0) {
return;
}
int cols = matrix[0].size();
bool firstRowZero = false;
bool firstColZero = false;
// Check whether the first row must be cleared later.
for (int col = 0; col < cols; col++) {
// A zero in the first row must be remembered before markers change it.
if (matrix[0][col] == 0) {
firstRowZero = true;
}
}
// Check whether the first column must be cleared later.
for (int row = 0; row < rows; row++) {
// A zero in the first column must be remembered before markers change it.
if (matrix[row][0] == 0) {
firstColZero = true;
}
}
// Store row and column markers inside the first row and first column.
for (int row = 1; row < rows; row++) {
for (int col = 1; col < cols; col++) {
// An inner zero marks its whole row and column.
if (matrix[row][col] == 0) {
matrix[row][0] = 0;
matrix[0][col] = 0;
}
}
}
// Apply markers to the inner part of the matrix.
for (int row = 1; row < rows; row++) {
for (int col = 1; col < cols; col++) {
// A zero row marker or column marker clears this cell.
if (matrix[row][0] == 0 || matrix[0][col] == 0) {
matrix[row][col] = 0;
}
}
}
// The saved first-row status decides whether the first row is cleared.
if (firstRowZero) {
for (int col = 0; col < cols; col++) {
matrix[0][col] = 0;
}
}
// The saved first-column status decides whether the first column is cleared.
if (firstColZero) {
for (int row = 0; row < rows; row++) {
matrix[row][0] = 0;
}
}
}
};
// Prints the matrix rows.
void printMatrix(const vector<vector<int>>& matrix) {
// Print each row on a separate line.
for (const vector<int>& row : matrix) {
for (int value : row) {
cout << value << " ";
}
cout << "\n";
}
}
// Driver code
int main() {
vector<vector<int>> matrix = {
{1, 2, 0, 4},
{5, 6, 7, 8},
{9, 0, 11, 12},
{13, 14, 15, 16}
};
// instance for class Solution
Solution sol;
sol.setZeroes(matrix);
printMatrix(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(m * n), because the matrix is scanned a constant number of times.

Space Complexity: O(1), because only a few Boolean variables are stored outside the matrix.

Interview follow-up Questions

Immediate mutation can create new zeros before all original cells have been checked. Those new zeros may then incorrectly clear additional rows and columns. The decision source must remain the original matrix state.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0