Reset Matrix
You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns in which each element contains only two values,i.e., 0 and 1. Your task is to convert the given matrix into the Good matrix in which if an element is 0, you need to set all elements values present in its entire row and column to 0.

For example:

Consider ARR = [[1 , 0 , 1] , [1 , 1 , 1] , [1 , 1 , 1]], the Good matrix after updating the given matrix as described in the question is [[0 , 0 , 0] , [1 , 0 , 1] , [1 , 0 , 1]]. Since ARR[0][1] is 0, we need to set all element’s values present in 0-th row and 1-th column to 0.

Note :

You do not need to print the matrix. Just change in the given input.

Input format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains two integers, 'N' and ‘M’, denoting the number of rows and columns in the array. The Next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'ARR'.

Output format :

For each test case, return the Good matrix after updating the given matrix as described in the question. Print the output of each test case in a separate line

Constraints :

1

Question

Reset Matrix

You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns in which each element contains only two values,i.e., 0 and 1. Your task is to convert the given matrix into the Good matrix in which if an element is 0, you need to set all elements values present in its entire row and column to 0.

For example:

Consider ARR = [[1 , 0 , 1] ,
                [1 , 1 , 1] , 
                [1 , 1 , 1]], 
the Good matrix after updating the given matrix as described in the question is  
                [[0 , 0 , 0] , 
                 [1 , 0 , 1] , 
                 [1 , 0 , 1]]. 
Since ARR[0][1] is 0, we need to set all element’s values present in 0-th row and 1-th column to 0.

Note :

You do not need to print the matrix. Just change in the given input.

Input format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers, 'N' and ‘M’, denoting the number of rows and columns in the array.
The Next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'ARR'.

Output format :

For each test case, return the Good matrix after updating the given matrix as described in the question.

Print the output of each test case in a separate line

Constraints :

1 <= T <= 20
1 <= N <= 300
1 <= M <= 300

ARR[i][j] can only contain two values, i.e, 0 and 1.    

 Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of rows and the number of columns in the array ‘ARR’ respectively, and 'ARR[i][j]' denotes the ’j-th’ element of  'i-th' row of the array 'ARR'. 

Time Limit: 1sec

Accepted Answer

Brute Force

A simple method is to create a 2-dimensional array to store the changes we need to update in the original matrix to convert the given matrix into the Good matrix.

Our approach will be to create a 2-dimensional array answer with N rows and M columns, and we will copy all elements value present in the matrix ARR into the matrix answer. We will iterate the variable row from 0 to N - 1, and in each iteration, we will iterate col from 0 to M - 1.

We will check if ARR[row][col] is equal to 0, then we need to set all elements value in the entire row and column of ARR[row][col] to 0. We will iterate index from 0 to N - 1, and set answer[index][col] as 0.
We will iterate index from 0 to M - 1, and set answer[row][index] as 0.

In the end, the matrix answer is the Good matrix which we will get after updating the given matrix as described in the question. We will return the matrix answer.

Algorithm:

Create a 2-dimensional array answer with N rows and M columns, which we will use to convert the given matrix into the Good matrix. We will update the changes in the matrix answer.
Copy all elements value present in the array ARR into the array answer.
Iterate row from 0 to N - 1.
- Iterate col from 0 to M - 1.
  - Check if ARR[row][col] is equal to 0.
    - Iterate index from 0 to N - 1, and set answer[index][col] as 0.
    - Iterate index from 0 to M - 1, and set answer[row][index] as 0.
Return the matrix answer.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M denote the number of rows and columns in the array.

The Space Complexity O(N * M) is used to create a 2-dimensional array to store the changes we need to update in the given matrix to convert the given matrix into the Good matrix. Hence, the overall Space Complexity is O(N * M).

Time Complexity: OtherExplanation:

O(N * M * (N + M)), where N and M denote the number of rows and columns in the array.

In the worst case, we are doing N * M iteration, and in each iteration, it takes O(N + M) to update the changes as described in the question to find the Good matrix. Hence, the overall Time Complexity = O(N * M) * (N + M) = O(N * M * (N + M)).

Java (SE 1.8)

/*

   Time Complexity: O(N * M * (N + M))

   Space Complexity: O(N * M)



   where N and M denote the number of rows and columns in the array.

*/



import java.util.ArrayList;



public class Solution {



	public static ArrayList> findGoodMatrix(ArrayList> arr) {



		int n = arr.size();

		int m = arr.get(0).size();



		// Create a 2-dimensional array answer

		ArrayList> answer = new ArrayList>(n);



		// Copy all elements value present in the array ARR into the array answer

		for (int row = 0; row < n; row++) {



			answer.add(new ArrayList(m));



			for (int col = 0; col < m; col++) {



				answer.get(row).add(arr.get(row).get(col));

			}

		}



		// Traverse through the array ARR

		for (int row = 0; row < n; row++) {



			for (int col = 0; col < m; col++) {



				// Check if ARR[row][col] is equal to 0

				if (arr.get(row).get(col) == 0) {



					// Set all elements present in the column col to 0 in the array answer

					for (int index = 0; index < n; index++) {

						answer.get(index).set(col, 0);

					}



					// Set all elements present in row to 0 in the array answer

					for (int index = 0; index < m; index++) {

						answer.get(row).set(index, 0);

					}

				}

			}

		}



		// Return the matrix answer

		return answer;



	}

}

Python (3.5)

'''

   Time Complexity: O(N * M * (N + M))

   Space Complexity: O(N * M)



   where N and M denote the number of rows and columns in the array.

'''



def findGoodMatrix(arr):

    n = len(arr)

    m = len(arr[0])

    

    # Create a 2-dimensional array answer

    answer = [[0 for j in range(m)] for i in range(n)]



    # Copy all elements value present in the array ARR into the array answer

    for row in range(n):



        for col in range(m):

            answer[row][col] = arr[row][col]



    # Traverse through the array ARR

    for row in range(n):



        for col in range(m):



            # Check if ARR[row][col] is equal to 0

            if (arr[row][col] == 0):



                # Set all elements present in the column col to 0 in the array answer 

                for index in range(n):

                    answer[index][col] = 0



                # Set all elements present in row to 0 in the array answer          

                for index in range(m):



                    answer[row][index] = 0

            

    # Return the matrix answer

    return answer

C++ (g++ 5.4)

/*

   Time Complexity: O(N * M * (N + M))

   Space Complexity: O(N * M)



   where N and M denote the number of rows and columns in the array.

*/



vector> findGoodMatrix(vector> &arr) 

{

    int n = arr.size();

    int m = arr[0].size();



    // Create a 2-dimensional array answer

    vector> answer(n);



    // Copy all elements value present in the array ARR into the array answer

    for (int row = 0; row < n; row++) 

    {

        answer[row].resize(m);



        for (int col = 0; col < m; col++) 

        {

            answer[row][col] = arr[row][col];

        }

    }



    // Traverse through the array ARR

    for (int row = 0; row < n; row++) 

    {

        for (int col = 0; col < m; col++) 

        {

            // Check if ARR[row][col] is equal to 0

            if (arr[row][col] == 0) 

            {

                // Set all elements present in the column col to 0 in the array answer 

                for (int index = 0; index < n; index++) 

                {

                    answer[index][col] = 0;

                }



                // Set all elements present in row to 0 in the array answer          

                for (int index = 0; index < m; index++) 

                {

                    answer[row][index] = 0;

                }

            }

        }

    }



    // Return the matrix answer

    return answer;

}

Accepted Answer

Store rows and columns

The basic idea is to create an array for all rows and an array for all columns in which we will keep the information of those rows and columns whose value we need to set as 0 for the entire row and column.

We will create array rows of size N and array columns of size M. The array rows will keep the record of all rows, and the array columns will keep the record for all columns whose value of all elements we need to set to 0. Initially, all elements of rows and columns will contain the value 0. We will set the element’s value to 1 if we need to set all element values present in that particular row or column to 0.

We will iterate the variable index from 0 to N - 1, and in each iteration, we will iterate pos from 0 to M - 1. We will check if ARR[index][pos] is equal to 0, then we need to set all elements in the row index and the column pos to 0. We will set rows[index] and columns[pos] as 1.
Now, we will update the changes in the original matrix. We will iterate the variable index from 0 to N - 1, and in each iteration, we will iterate pos from 0 to M - 1. We will check either rows[index] or columns[pos] is equal to 1, then we will update ARR[index][pos] with the value 1.

In the end, the matrix ARR is converted into the Good matrix. We will return the matrix ARR.

Algorithm:

Create an array rows of size N and columns of size M. The element of the array rows, and the array columns will contain the value 1 if we need to set all elements value present in that particular row and column to 0.
Iterate index from 0 to N - 1.
- Iterate pos from 0 to M - 1.
  - Check if ARR[index][pos] is equal to 0.
    - Update rows[index] with the value 1.
    - Update columns[pos] with the value 1.
Iterate index from 0 to N-1.
- Iterate pos from 0 to M - 1.
  - Check either rows[index] is equal to 1 or columns[pos] is equal to 1.
    - Set ARR[index][pos] as 0.
Return the matrix ARR.

Space Complexity: OtherExplanation:

O(N + M), where N and M denote the number of rows and columns in the array.

The Space Complexity O(N + M) is used to store rows and columns, whose value we need to set as 0 for the entire row and column. Hence, the overall Space Complexity is O(N + M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M denote the number of rows and columns in the array.

The Time Complexity to find the rows and columns, whose value we need to set as 0 for the entire row and column is 0(N * M). The Time Complexity to update the changes in the matrix to convert the given matrix into the Good matrix is O(N * M). Hence, the overall Time Complexity is O(N * M).

Java (SE 1.8)

/*

   Time Complexity: O(N * M)

   Space Complexity: O(N + M)



   where N and M denote the number of rows and columns in the array.

*/



import java.util.ArrayList;



public class Solution {



	public static ArrayList> findGoodMatrix(ArrayList> arr) {



		int n = arr.size();

		int m = arr.get(0).size();



		// Create an array rows of size N and columns of size M with value 0 at each position

		ArrayList rows = new ArrayList(n);

		ArrayList columns = new ArrayList(m);



		for (int i = 0; i < Math.max(n, m); i++) {

			if (i < n) {

				rows.add(0);

			}

			if (i < m) {

				columns.add(0);

			}

		}



		// Traverse through the array ARR

		for (int index = 0; index < n; index++) {



			for (int pos = 0; pos < m; pos++) {



				// Check if ARR[index][pos] is equal to 0

				if (arr.get(index).get(pos) == 0) {



					// Update rows[index] and columns[pos] with the value 1

					rows.set(index, 1);

					columns.set(pos, 1);

				}

			}

		}



		// Update the array ARR to convert the matrix into the Good matrix

		for (int index = 0; index < n; index++) {



			for (int pos = 0; pos < m; pos++) {



				// Check either rows[index] or columns[pos] is equal to 1

				if (rows.get(index) == 1 || columns.get(pos) == 1) {

					arr.get(index).set(pos, 0);

				}

			}

		}



		// Return the matrix ARR

		return arr;

	}

}

C++ (g++ 5.4)

/*

   Time Complexity: O(N * M)

   Space Complexity: O(N + M)



   where N and M denote the number of rows and columns in the array.

*/



vector> findGoodMatrix(vector> &arr) 

{

    int n = arr.size();

    int m = arr[0].size();



    // Create an array rows of size N and columns of size M with value 0 at each position

    vector rows(n, 0);

    vector columns(m, 0);



    // Traverse through the array ARR

    for (int index = 0; index < n; index++) 

    {

        for (int pos = 0; pos < m; pos++) 

        {

            // Check if ARR[index][pos] is equal to 0

            if (arr[index][pos] == 0) 

            {

                // Update rows[index] and columns[pos] with the value 1

                rows[index] = 1;

                columns[pos] = 1;

            }

        }

    }



    // Update the array ARR to convert the matrix into the Good matrix

    for (int index = 0; index < n; index++) 

    {

        for (int pos = 0; pos < m; pos++) 

        {

            // Check either rows[index] or columns[pos] is equal to 1

            if (rows[index] == 1 || columns[pos] == 1) 

            {

                arr[index][pos] = 0;

            }

        }

    }



    // Return the matrix ARR

    return arr;

}

Python (3.5)

'''

   Time Complexity: O(N * M)

   Space Complexity: O(N + M)



   where N and M denote the number of rows and columns in the array.

'''



def findGoodMatrix(arr): 



    n = len(arr)

    m = len(arr[0])



    # Create an array rows of size N and columns of size M with value 0 at each position

    rows = [0 for i in range(n)]

    columns = [0 for i in range(m)]



    # Traverse through the array ARR

    for index in range(n):



        for pos in range(m):



            # Check if ARR[index][pos] is equal to 0

            if (arr[index][pos] == 0):



                # Update rows[index] and columns[pos] with the value 1

                rows[index] = 1

                columns[pos] = 1



    # Update the array ARR to convert the matrix into the Good matrix

    for index in range(n):



        for pos in range(m):

        

            # Check either rows[index] or columns[pos] is equal to 1

            if (rows[index] == 1 or columns[pos] == 1):

                arr[index][pos] = 0



    # Return the matrix ARR

    return arr

Accepted Answer

Optimized approach

As we have discussed in the previous approach, we have created an array for all rows and an array for all columns to keep information of those rows and columns whose value we need to set to 0 for the entire row and column. In this approach, we will keep the record of all rows and columns in the given matrix. We will use the 0’th row and 0’th column of the matrix to keep to record for all rows and columns.

To make this approach work, we will maintain a variable isCol, which will store if we need to set all elements value in the 0’th column to 0.

We will iterate the variable row from 0 to N - 1. In each iteration, we will check if ARR[row][0] is equal to 0, then we need to set all elements in the 0’th column to 0. So, we will update isCol with the value true. We will iterate the variable column from 0 to M - 1. We will check if ARR[row][colum] is equal to 0, then we need to set all in the entire row and column of ARR[row][col] to 0 and we will update ARR[0][column] and ARR[row][0] with the value 0.
Now, we will update changes in the given matrix. We will iterate the variable row from 0 to N - 1. In each iteration, We will iterate the variable column from 0 to M - 1. We will check either ARR[row][0] or ARR[0][column] is equal to 0, then we will update ARR[row][column] with the value 0.
Now, we need to take care of the 0’th row and 0’th column. We will check ARR[0][0] is equal to 0, and then we need to set all elements in the 0’th row to 0. We will iterate the variable column from 0 to M - 1, and we will update ARR[0][column] with the value 0.
We will check if isCol is equal to true, then we need to set all elements in the 0’th column to 0. We will iterate the variable row from 0 to N - 1, and we will update ARR[row][0] with the value 0.

In the end, the matrix ARR is converted into the Good matrix. We will return the matrix ARR.

Algorithm:

Set the variable isCol as false. The variable isCol stores if we need to set all element’s value in the 0’th column to 0.
Iterate row from 0 to N - 1.
- Check if ARR[row][0] is equal to 0.
  - Update the variable isCol with true.
- Iterate column from 1 to M - 1.
  - Check if ARR[row][column] is equal to 0.
    - Update ARR[0][column] with the value 0.
    - Update ARR[row][0] with the value 0.
Iterate row from 1 to N - 1.
- Iterate column from 1 to M - 1.
  - Check either ARR[row][0] is equal to 0 or ARR[0][column] is equal to 0, then update ARR[row][column] with the 0.
Check if ARR[0][0] is equal to 0.
- Iterate column from 0 to M - 1, update ARR[0][column] with the 0.
Check if isCol is equal to true.
- Iterate row from 0 to N - 1, and update ARR[row][0] with the 0.
Return the matrix ARR.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. The overall Space Complexity is O(1).

Time Complexity: OtherExplanation:

O(N * M + N + M), where N and M denote the number of rows and columns in the array.

In the worst case, we are traversing through the array ARR to update the changes to convert the given matrix into the Good matrix that takes O(N * M) time. The Time Complexity to set elements of 0’th row and 0’th column to 0 is O(N + M). Hence, the overall Time Complexity is O(N * M + N + M).

Java (SE 1.8)

/*

   Time Complexity: O(N * M + N + M)

   Space Complexity: O(1)



   where N and M denote the number of rows and columns in the array.

*/



import java.util.ArrayList;



public class Solution {



	public static ArrayList> findGoodMatrix(ArrayList> arr) {



		int n = arr.size();

		int m = arr.get(0).size();



		// The variable isCol stores if we need to set all element's value in the '0'th column to 0

		boolean isCol = false;



		// Iterate row from 0 to N - 1

		for (int row = 0; row < n; row++) {



			// Check if ARR[row][0] is equal to 0

			if (arr.get(row).get(0) == 0) {

				isCol = true;

			}



			for (int column = 1; column < m; column++) {



				// Check if ARR[row][column] is equal to 0

				if (arr.get(row).get(column) == 0) {

					// Update ARR[0][column] and arr[row][0] with the value 0

					arr.get(0).set(column, 0);

					arr.get(row).set(0, 0);



				}

			}

		}



		// Update in the array ARR to convert the matrix into the Good matrix

		for (int row = 1; row < n; row++) {

			for (int column = 1; column < m; column++) {



				// Check either ARR[row][0] or ARR[0][column] is equal to 0

				if (arr.get(row).get(0) == 0 || arr.get(0).get(column) == 0) {

					arr.get(row).set(column, 0);

				}

			}

		}



		// Check if ARR[0][0] is equal to 0

		if (arr.get(0).get(0) == 0) {



			// Set all elements in the '0'th row to 0

			for (int column = 0; column < m; column++) {

				arr.get(0).set(column, 0);

			}

		}



		// Check if isCol is equal to true

		if (isCol == true) {



			// Set all elements in the '0'th column to 0

			for (int row = 0; row < n; row++) {

				arr.get(row).set(0, 0);

			}

		}



		// Return the matrix ARR

		return arr;

	}

}

C++ (g++ 5.4)

/*

   Time Complexity: O(N * M + N + M)

   Space Complexity: O(1)



   where N and M denote the number of rows and columns in the array.

*/



vector> findGoodMatrix(vector> &arr) 

{

    int n = arr.size();

    int m = arr[0].size();



    // The variable isCol stores if we need to set all element’s value in the 0’th column to 0

    bool isCol = false;



    // Iterate row from 0 to N - 1

    for (int row = 0; row < n; row++) 

    {

        // Check if ARR[row][0] is equal to 0

        if (arr[row][0] == 0) 

        {

            isCol = true;

        }



        for (int column = 1; column < m; column++)

        {

            // Check if ARR[row][column] is equal to 0

            if (arr[row][column] == 0) 

            {

                // Update ARR[0][column] and arr[row][0] with the value 0

                arr[0][column] = 0;

                arr[row][0] = 0;

            }

        }

    }



    // Update in the array ARR to convert the matrix into the Good matrix

    for (int row = 1; row < n; row++) 

    {

        for (int column = 1; column < m; column++)

        {

            // Check either ARR[row][0] or ARR[0][column] is equal to 0

            if (arr[row][0] == 0 || arr[0][column] == 0) 

            {

                arr[row][column] = 0;

            }

        }

    }



    // Check if ARR[0][0] is equal to 0

    if (arr[0][0] == 0) 

    {

        // Set all elements in the 0’th row to 0 

        for (int column = 0; column < m; column++)

        {

            arr[0][column] = 0;

        }

    }



    // Check if isCol is equal to true

    if (isCol) 

    {

        // Set all elements in the 0’th column to 0

        for (int row = 0; row < n; row++) 

        {

            arr[row][0] = 0;

        }

    }



    // Return the matrix ARR

    return arr;

}

Python (3.5)

'''

   Time Complexity: O(N * M + N + M)

   Space Complexity: O(1)



   where N and M denote the number of rows and columns in the array.

'''



def findGoodMatrix(arr):



    n = len(arr)

    m = len(arr[0])



    # The variable isCol stores if we need to set all element’s value in the 0’th column to 0

    isCol = False



    # Iterate row from 0 to N - 1

    for row in range(n):



        # Check if ARR[row][0] is equal to 0

        if (arr[row][0] == 0):

            isCol = True



        for column in range(1, m):



            # Check if ARR[row][column] is equal to 0

            if (arr[row][column] == 0):

                

                # Update ARR[0][column] and arr[row][0] with the value 0

                arr[0][column] = 0

                arr[row][0] = 0

            

    # Update in the array ARR to convert the matrix into the Good matrix

    for row in range(1, n):



        for column in range(1, m):

            

            # Check either ARR[row][0] or ARR[0][column] is equal to 0

            if (arr[row][0] == 0 or arr[0][column] == 0):

                arr[row][column] = 0



    # Check if ARR[0][0] is equal to 0

    if (arr[0][0] == 0):



        # Set all elements in the 0’th row to 0 

        for column in range(m):

            arr[0][column] = 0

        

    # Check if isCol is equal to true

    if (isCol == True):



        # Set all elements in the 0’th column to 0

        for row in range(n):

            arr[row][0] = 0

        

    # Return the matrix ARR

    return arr

For example:

Note :

Input format :

Output format :

Constraints :

Top Infosys System Engineer Specialist interview questions & answers

Top HR questions asked in Infosys System Engineer Specialist