Find the Good Matrix Problem in Java

A two-dimensional array 'arr' with 'n' rows and 'm' columns is provided to you. Each element of the array can store only two values in them; either zero (0) or one (1). The problem statement is to convert the input matrix into a Good matrix. A Good matrix is a matrix where if an element or value is 0, the values of the entire row and column must be changed to 0.

Example 1:

Input

Output

Explanation:

The rows and columns of the elements whose values are 0 will be changed to 0.

Arr [0][0] is 0, so the values of all the elements of the 0th row and 0th column will be changed to 0.

Example 2:

Input

Output

Explanation:

The element at the arr[0][1] is zero, so all the elements of the 0th row and 1st column will be changed to zero according to the problem statement. Similarly, all the zero elements, their respective elements of rows and columns, will be changed to zero.

Example 3:

Input

Output

Explanation:

In the example as mentioned above, we can observe that only arr[1][1] is zero. According to the problem statement, the Good matrix should contain values of both the 1st row and 1st column as zero.

Approach:

This approach is the easiest approach to finding the good matrix of the given input matrix. Simply, a second matrix must be created, which will be used to store the resultant matrix generated that follows the given problem statement. The second matrix can be labelled result.

Step-1: A two-dimensional array or a matrix of N rows and M columns must be created. This matrix will transform the input matrix into the good matrix. The modifications will be done in the second matrix labelled as the result.

Step-2: All the values of the input array must be copied into the result array.

Step-3:

• The row will iterate from 0 to N-1. The col will iterate from 0 to M-1.
  • We will check whether Arr[row][col] is zero.
    • The index will iterate from 0 to N-1, and the result[index][col] will be 0.

Step-4: The resultant matrix where the good matrix is stored will be returned.

Step-5: The algorithm ends.

Explanation:

While iterating through all the elements of the input matrix, in the first row, 2nd column element is zero. This indicates that all the elements of the 0th row and 2nd column must be set as zero. Similarly, in the 1st row, the 0th column element's value is zero. This means that the matrix will be a good matrix if all elements of the 1st row and the 0th column are zero.

Filename: GoodMatrix.java

public class FindGoodMatrix
{
public static int[][] Transform_to_GoodMatrix(int[][] matrix, int rows, int cols)
{
int[][] ans = new int[rows][cols];
// The elements of the input matrix will be copied into the answer matrix.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
ans[i][j] = matrix[i][j];
}
}
// We will iterate through each and every element in the matrix.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (matrix[row][col] == 0) {
// All the elements of the complete row will be set as 0.
for (int index = 0; index < rows; index++) {
ans[index][col] = 0;
}
// All the elements of the complete column will be set as 0.
for (int index = 0; index < cols; index++) {
ans[row][index] = 0;
}
}
}
}
return ans;
}
public static void main(String[] args)
{
int count = 1;
// The count variable is used to declare the number of test cases that will be provided in this program.
for (int i = 0; i < count; i++) {
int rows = 3; // 'rows' represents the number of rows in the matrix.
int cols = 3; // 'cols' represents the number of columns in the matrix.
//'matrix' is the name of the two-dimensional array referred to as the input array.
int[][] matrix = { {1, 1, 1}, {1, 0, 0}, {1, 1, 1}};
// The given input matrix will be converted to Good Matrix.
int[][] GoodMatrix = Transform_to_GoodMatrix(matrix, rows, cols);
// The matrix will be displayed.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(GoodMatrix[i][j] + " ");
}
System.out.println();
}
}
}
}

Output:

Complexity Analysis:

The above-mentioned program keeps iterating through

all the elements present in the matrix using nested loops. The external or outer loop is used to iterate starting from 0 till N-1. Here, N stands for the number of rows present in the matrix. The internal loop or inner loop is used to iterate starting from 0 till M-1. Also, extra loops in the form of nested loops are mentioned for setting the values of elements zero. Finally, the time complexity of the above-mentioned Java program can be represented by 0(N*M(N+M)).

The above-mentioned program creates a new two-dimensional array for storing the resultant good matrix in it. The space allocated for the resultant matrix is the same as the size of the input matrix, as the number of elements present in the matrix is not modified. Finally, the space complexity of the above-mentioned program is 0(N*M).