# Set Matrix Zeros in Java

In coding round interviews, it is frequently asked as the most significant challenge.

an m*n matrix is provided. Set the entire column and row of the matrix to 0 if any element is 0. Keep in mind that the operation shouldn't use any more arrays.

Think of the following matrix as an example.

Input:

Output

The second row, as well as the second column elements in the array above both, have the value 0. In light of this, we will set each element in the second column and row to 0.

Java code to set matrix zeros

### Different Approaches

The following three approaches can be used to fix the issue:

• Brute force approach

Using stacked loops and auxiliary space, the brute force method.

• Hash table approach

keeping an eye on the state of the hash table's rows and columns.

• In-place hashing approach

Using In-Place Hashing: Store the hash in the matrix's top row and bottom column.

### Brute Force Approach

The practice of setting matrix zeros is foolish. In this method, we iterate through the matrix, updating each row and column to 0 for every 0. The method is quite simple, however, it could result in an incorrect answer.

Steps

Step1: Makean (n x m)-dimensional array response and initialize each element to 1.

Step 2: If the current row includes an element equal to 0, proceed row-by-row across the matrix array as well as set its current row as 0 in the response array.

Step 3: If the present column contains an element equal to 0, move column-by-column across the matrix array and set the current column as 0 in the response array.

Step 4: Now, as you traverse the response array if the element you are on is 0, set it to 0 in a matrix array.

Step 5: Return the Matrix array.

Pseudocode

``````void setMatrixZero(int a[][], int m, int n)
{
int temp[m][n]
for (i = 0 to m-1)
for (j = 0 to n-1)
temp[i][j] = 1
for(i = 0 to m - 1)
{
for (j = 0 to n - 1)
{
if (a[i][j] == 0)
{
for (k = 0 to m - 1)
temp[k][j] = 0
for (k = 0 to n - 1)
temp[i][k] = 0
}
}
}
for (i = 0 to M-1)
for (j = 0 to N-1)
arr[i][j] = temp[i][j]
}
``````

In the method described above, we have explored every row and column of the appropriate matrix cell. The aforementioned method has an O(n*m(n+m)) time complexity and an O(n*m) space complexity for recording the primary matrix.

But it's our job to carry out the same action without taking up extra room. The same is shown in the approaches that follow.

Example program

``````public class SetMatrixZeroes {
public static void setZeroes(int[][] matrix, int n, int m) {
int ans[][] = new int[n][m];
for (int i = 0; i< n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = 1;
}
}
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++) {
ans[i][k] = 0;
}
break;
}
}
}
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++) {
ans[k][j] = 0;
}
}
}
}
for (int i = 0; i< n; i++) {
for (int j = 0; j < m; j++) {
if (ans[i][j] == 0) {
matrix[i][j] = 0;
}
}
}
}
public static void main(String[] args) {
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();
}
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();
}
}
}
``````

The output of the above program

``````1 0 1
0 0 0
1 0 1
0 0 0 0
0 4 5 0 0 3 1 0
``````

### Hash Table Approach

We will employ a hash table to perform the same action. We will first create a HashTable and set all of the matrix's rows and columns to false. When the value of a row or column was changed from false to true, its value was set to 0.

Steps

Step 1: Make two HashTables with M and N-sized columns and rows, respectively.

Step 2: Set all of the row[] and col[] values to false at the beginning.

Step 3: Now, iterate through the matrix, setting row[i] and col[j] to true for each time a[i][j] == 0.

Step 4: Once step 3 is complete, traverse over matrix a once again and change any value a[i][j] to 0 if row[i] and otherwise col[j] are true.

Pseudocode

``````void setMatrixZeros(int a[][], int m, int n)
{
bool row[m], col[n]
for(i = 0 to m-1)
row[i] = false
for(j = 0 to n-1)
col[j] = false
for(i = 0 to m-1)
{
for(j = 0 to n-1)
{
if(a[i][j] == 0)
{
row[i] = true
col[j] = true
}
}
}
for(i = 0 to m-1)
{
for(j = 0 to n-1)
{
if(row[i] == true or col[j] == true)
arr[i][j] = 0
}
}
}
``````

The time complexity of the aforementioned method is O(n*m). Due to the time required to create two hash tables, fill them with values, traverse them, and update them (O(n*m)). Because of this, the temporal complexity is O(n*m).The complexity of the storage space is increased by the usage of two hash tables.i.e, O(n+m)

The aforementioned strategy is likewise not optimal. The in-place hashing can be used to provide the optimal answer.

### In-place Hashing Approach

This method involves storing row and column hashes in the matrix component. The matrix's initial row and column can be used to hold, respectively, the position of the matrix's rows and columns. The initial row and column status, which can be managed using two variables, will provide a challenge.

Steps

Step 1: First, define two variables. To store the state of the first column and first row, use the row, and the first column. Make them false.

Step 2: Use this row and column to store the row's and column's status in a hash.

Step 3: As you iterate through the matrix, set a[i][0] = 0 and col[0][j] = 0 for each time a[i][j] == 0.

Step 4: If a[i][0] = true for a[i][j] or a[0][i] = true for a[i][i], then set all of the matrix's values to 0 except for the first row and column.

Step 5: Update the first row's and first column's values last.

Pseudocode

``````void setMatrixZeros(int a[][], int m, int n)
{
for(j = 0 to n-1)
if(a[0][j] == 0)
firstRow = true
for(i = 0 to M-1)
if(a[i][0] == 0)
firstCol = true
for(i = 0 to m-1)
{
for(j = 0 to n-1)
{
if(a[i][j] == 0)
{
a[i][0] = 0
a[0][j] = 0
}
}
}
for (i = 1 to m-1)
{
for (j = 1 to N-1)
{
if(a[0][j] == 0 || a[i][0] == 0)
a[i][j] = 0
}
}
if(firstRow == true)
{
for( i = 0 to n-1 )
a[0][i] = 0
}
if(firstCol == true)
{
for(i = 0 to m-1)
a[i][0] = 0
}
}
``````

The above method has an O(m*n) time complexity because we traversed the first row and the first column, updating the matrix, and finally modifying the first row as well as the first column, which takes O(m) + O(n) time (n). As a result, O(m*n) is the time complexity. Since we did not employ an auxiliary array, the space complexity is O. (1).

Example program of the set matrix to zeros in java

``````public class SetMatrixZeros
{
private static void setZeros(int[][] matrix, int n, int m)
{
int ans[][] = new int[n][m];
for (int i = 0; i< n; i++)
{
for (int j = 0; j < m; j++)
{
ans[i][j] = 1;
}
}
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;
}
}
}
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++)
{
ans[k][j] = 0;
}
}
}
}
for (int i = 0; i< n; i++)
{
for (int j = 0; j < m; j++)
{
if (ans[i][j] == 0)
{
matrix[i][j] = 0;
}
}
}
}
public static void main(String args[])
{
int[][] matrix = new int[][]
int  n = matrix.length;
int m = matrix[0].length;
setZeros(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();
}
}
}
``````

The output of the above program

``````0 0 0 0
0 8 0 0
0 0 0 0
``````