Set Matrix Zeros Problem Statement

Given an N x M integer matrix, if an element is 0, set its entire row and column to 0's, and return the matrix. Specifically, if a cell has a value 0 (i.e., matrix[i][j] == 0), change all cells in the ith row and jth column to 0. Perform modifications in-place.

Input:

The first line of the input contains an integer T representing the number of test cases. For each test case, the first line contains two space-separated integers N and M, denoting the number of rows and columns of the matrix. For the next N lines, each line contains M space-separated integers representing the matrix elements.

Output:

For each test case, print the modified matrix. Print the output of each test case in a separate line.

Example:

Input: 1 2 3 7 19 3 4 21 0 Output: 7 19 0 0 0 0

Constraints:

1 ≤ T ≤ 1000

1 ≤ M, N ≤ 1000

Σ(M * N) ≤ 2000000

-2³¹ ≤ matrix[i][j] ≤ 2³¹-1, for all 1 ≤ i ≤ N and 1 ≤ j ≤ M.

Time Limit: 1 sec

Note:

You are not required to print anything; the function should return the modified matrix as the output.

Follow-up:

Can we optimize space usage better than O(M * N)? Using O(M + N) space improves memory use, but further optimizations can be made to use constant space. Can you achieve this?

Question

Set Matrix Zeros Problem Statement

Given an N x M integer matrix, if an element is 0, set its entire row and column to 0's, and return the matrix. Specifically, if a cell has a value 0 (i.e., matrix[i][j] == 0), change all cells in the ith row and jth column to 0. Perform modifications in-place.

Input:

                The first line of the input contains an integer T representing the number of test cases.                    For each test case, the first line contains two space-separated integers N and M, denoting the number of rows and columns of the matrix.                       For the next N lines, each line contains M space-separated integers representing the matrix elements.

Output:

            For each test case, print the modified matrix. Print the output of each test case in a separate line.

Example:

Constraints:

1 ≤ T ≤ 1000
1 ≤ M, N ≤ 1000
Σ(M * N) ≤ 2000000
-2³¹ ≤ matrix[i][j] ≤ 2³¹-1, for all 1 ≤ i ≤ N and 1 ≤ j ≤ M.
Time Limit: 1 sec

Note:

You are not required to print anything; the function should return the modified matrix as the output.

Follow-up:

Can we optimize space usage better than O(M * N)? Using O(M + N) space improves memory use, but further optimizations can be made to use constant space. Can you achieve this?

Accepted Answer

    rows,cols = len(matrix),len(matrix[0])
    arr_rows,arr_cols = [False]*rows,[False]*cols
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                arr_rows[i] = True
                arr_cols[j] = True
    for i in range(rows):
        for j in range(cols):
            if arr_rows[i] or arr_cols[j]:
                matrix[i][j] = 0
    return matrix

Accepted Answer

rows,cols = len(matrix),len(matrix[0]) arr_rows,arr_cols = [False]*rows,[False]*cols for i in range(rows): for j in range(cols): if matrix[i][j] == 0: arr_rows[i] = True arr_cols[j] = True for i in range(rows): for j in range(cols): if arr_rows[i] or arr_cols[j]: matrix[i][j] = 0 return matrix