# Set Matrix Zeroes

Difficulty Level Medium
Array Matrix

In the set matrix zeroes problem, we have given a (n X m) matrix, if an element is 0, set its entire row and column 0.

Input:
{
[1, 1, 1]
[1, 0, 1]
[1, 1, 1]
}
Output:
{
[1, 0, 1]
[0, 0, 0]
[1, 0, 1]
}

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

## Naive Approach for Set Matrix Zeroes

1. Create an array answer of size (n X m) and initialize every element as 1.
2. Traverse the matrix array row-wise and set the current row as 0 in answer array if the current row contains an element equals to 0.
3. Traverse the matrix array column-wise and set the current column as 0 in answer array if the current column contains an element equals to 0.
4. Now traverse the answer array, if the current element is 0, then set this element as 0 in a matrix array.
5. Return matrix array.

### Pseudo Code

```Initialize all the elements of array answer as 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
set row i as 0(zero) in answer array
break
}
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j] == 0) {
set column j as 0(zero) in matrix array
}
break
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
}
}
}

### JAVA Code for Set Matrix Zeroes

```public class SetMatrixZeroes {
private static void setZeroes(int[][] matrix, int n, int m) {

// Set all elements of answer array as 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
}
}

// Traverse row wise
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
// Set this row as zero in answer array
for (int k = 0; k < m; k++) {
}
break;
}
}
}

// Traverse column wise
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j] == 0) {
// Set this column as 0 in answer array
for (int k = 0; k < n; k++) {
}
}
}
}

// Update the elements in matrix array
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = 0;
}
}
}
}

public static void main(String[] args) {
// Example 1
int[][] matrix = new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
int n = matrix.length;
int m = matrix[0].length;

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}

// Example 2
matrix = new int[][] {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
n = matrix.length;
m = matrix[0].length;

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}```

### C++ Code for Set Matrix Zeroes

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

void setZeroes(vector<vector<int>> &matrix, int n, int m) {

// Set all elements of answer array as 1
for (int i = 0; i < n; i++) {
vector<int> curr;
for (int j = 0; j < m; j++) {
curr.push_back(1);
}
}

// Traverse row wise
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
for (int k = 0; k < m; k++) {
}
break;
}
}
}

// Traverse column wise
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j] == 0) {
for (int k = 0; k < n; k++) {
}
}
}
}

// Update the elements in matrix array
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = 0;
}
}
}
}

int main() {
// Example 1
vector<vector<int>> matrix{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
int n = matrix.size();
int m = matrix[0].size();

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}

// Example 2
vector<vector<int>> matrix2{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
n = matrix2.size();
m = matrix2[0].size();

setZeroes(matrix2, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<matrix2[i][j]<<" ";
}
cout<<endl;
}

return 0;
}```
```1 0 1
0 0 0
1 0 1
0 0 0 0
0 4 5 0
0 3 1 0
```

### Complexity Analysis

Time Complexity = O(n * m)
Space Complexity = O(n * m)
where n is the number of rows in the matrix and m is the number of columns in the matrix.

Check if Two Expressions With Brackets are Same

## Optimal Approach for Set Matrix Zeroes

The time complexity cannot be decreased further, but we can optimize the space complexity to O(1).

If we assume that -9999, do not occur in the matrix array, then

1. Traverse the matrix array row-wise and set all the elements of current row which are not 0 as -9999, if the current row contains an element equals to 0.
2. Traverse the matrix array column-wise and set all the elements of the current column which are not 0 as -9999, if the current column contains an element equals to 0.
3. Again traverse the matrix and set all the elements that are -9999 to 0.
4. Return matrix array.

### JAVA Code

```public class SetMatrixZeroes {
private static void setZeroes(int[][] matrix, int n, int m) {
// Traverse row wise
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
// Set all the elements that are not zero as -9999
for (int k = 0; k < m; k++) {
if (matrix[i][k] != 0) {
matrix[i][k] = -9999;
}
}
}
}
}

// Traverse column wise
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j] == 0) {
// Set all the elements that are not zero as -9999
for (int k = 0; k < n; k++) {
if (matrix[k][j] != 0) {
matrix[k][j] = -9999;
}
}
}
}
}

// Update all -9999 as 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == -9999) {
matrix[i][j] = 0;
}
}
}
}

public static void main(String[] args) {
// Example 1
int[][] matrix = new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
int n = matrix.length;
int m = matrix[0].length;

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}

// Example 2
matrix = new int[][] {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
n = matrix.length;
m = matrix[0].length;

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}```

### C++ Code

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

void setZeroes(vector<vector<int>> &matrix, int n, int m) {
// Traverse row wise
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
// Set all the elements that are not zero as -9999
for (int k = 0; k < m; k++) {
if (matrix[i][k] != 0) {
matrix[i][k] = -9999;
}
}
break;
}
}
}

// Traverse column wise
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j] == 0) {
// Set all the elements that are not zero as -9999
for (int k = 0; k < n; k++) {
if (matrix[k][j] != 0) {
matrix[k][j] = -9999;
}
}
}
}
}

// Update all -9999 as 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == -9999) {
matrix[i][j] = 0;
}
}
}
}

int main() {
// Example 1
vector<vector<int>> matrix{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
int n = matrix.size();
int m = matrix[0].size();

setZeroes(matrix, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}

// Example 2
vector<vector<int>> matrix2{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
n = matrix2.size();
m = matrix2[0].size();

setZeroes(matrix2, n, m);

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<matrix2[i][j]<<" ";
}
cout<<endl;
}

return 0;
}```
```1 0 1
0 0 0
1 0 1
0 0 0 0
0 4 5 0
0 3 1 0
```

### Complexity Analysis

Time Complexity = O(n * m)
Space Complexity = O(1)
where n is the number of rows in the matrix and m is the number of columns in the matrix.