Set Matrix Ones

Easy

0/40

Average time to solve is 15m

Contributed by

61 upvotes

Asked in company

Problem statement

You have been given a non-empty grid ‘MAT’ consisting of only 0s and 1s. Your task is to modify it in such a way that if a cell has value 1 (MAT[i][j] == 1), then all the cells of the i-th row and j-th column should be changed to 1.

For Example

If the given grid is this:
[0, 0, 0]
[0, 0, 1]

Then the modified grid will be
[0, 0, 1],
[1, 1, 1]

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

Input Format

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two space integers‘ N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

The next 'N' lines represent the rows of the grid. Every row contains M single space-separated integers.

Output Format

For each test case, print the modified grid.

Print the output of each test case in a separate line.

Note

You are not required to print the expected output; it has already been taken care of. Just implement the function. 

Also, update the given matrix in place.

Constraints

1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= MAT[i][j] <= 1

Time limit: 1 sec

Sample Input 1

Sample Output 1:

1 1
1 0
1 1

Explanation of the Sample Input 1

Test Case 1: For the given grid, 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.

Test Case 2: For the given grid, there is only one row and the element in this row is 1, thus all elements in the grid are set to 1.

Sample Input 2

Sample Output 2

Hint 1

Hint 2

Hint 3

Naively set all rows and columns of cells with value 1.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive Approach

We will traverse the whole grid and whenever MAT[i][j] == 1, we will mark all 0s in the i-th row and j-th column as -1. This will help us in differentiating between the 1s that are initially there in the matrix and the 1s which we will set now.

Now, traverse the grid again and mark the cells with value -1 as 1.

Time Complexity

O(N*M*max(N, M)), where N is the number of rows in the given grid, and M is the number of columns.

In the worst case(when we all cells have value 1), we are visiting a row and a column for all cells. Hence, the time complexity is O(N * M * max(N, M)).

Space Complexity

O(1)

We are using constant space.

(100% EXP penalty)

Set Matrix Ones

Console