Boolean Matrix

Moderate

0/80

Average time to solve is 35m

Contributed by

19 upvotes

Asked in companies

Problem statement

Given a 2-dimensional boolean matrix mat of size N x M, modify the matrix such that if an element is 1, set its entire row and column to 1 i.e. if mat[i][j] = 1, then make all the elements of the ith row and the jth column as 1.

Note :

You need to make the modifications in the input matrix.

You do not need to print anything, it has already been taken care of.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains two single-spaced integers N and M, representing the number of rows and columns of the matrix respectively.

The next N line contains M single-spaced elements (0 or 1).

Output Format:

For each test case, the modified matrix is printed.

The output for each test case is in a separate line.

Constraints:

1 <= T <= 10
1 <= N, M <= 200

Where N and M are the number of rows and columns respectively.

Sample Input 1:

Sample Output 1:

1 1
1 0

Explanation of the Sample Input 1:

For the given matrix, the element in the first row and column is 1, thus all the elements in the first row and first column are set to 1.

Sample Input 2:

Sample Output 2:

Hint 1

Hint 2

For any cell in the matrix that has the element 1, try storing its row and column.

Approaches (2)

Approach 1

Approach 2

Using additional space

The main idea behind this approach is that we use two temporary arrays, row[N] and col[M], to keep a track of the rows and columns which should be set to 1. Initially, both the arrays are initialized as 0.

Now, we traverse the given matrix and whenever we find a cell Mat[i][j] with value 1, we set row[i] = 1 and col[j] = 1.

After this traversal, we again traverse the given matrix and for each cell Mat[i][j], we check if either of row[i] or col[j] is 1. If either of the two values is 1, we set the value of the cell in the given matrix to 1.

Time Complexity

O(N * M), where N and M are the number of rows and columns in the given matrix respectively.

The traversal of the matrix takes O(N * M) time. Since we are traversing the matrix two times, the final complexity is O(2 * N * M) = O(N * M).

Space Complexity

O(N + M), where N and M are the number of rows and columns in the given matrix respectively.

This approach requires two temporary arrays, row and col, of sizes N and M respectively. Also, we are making the modifications in the input matrix itself, so no additional space is required on that end. Thus, the final space complexity is O(N + M).

(100% EXP penalty)

Boolean Matrix

Console