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

To solve the Set Matrix Zeros problem, we can use O(1) space by utilizing the first row and column to store information about zeros in the rest of the matrix.

Iterate through the matrix and use the first row and column to mark rows and columns that need to be zeroed out.
After marking, iterate through the matrix again and zero out the rows and columns based on the marks in the first row and column.
Remember to handle the special case of the first row and column separately.
Example: If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0 to mark the row and column.
Example: After marking, go through the matrix again and zero out rows and columns based on the marks in the first row and column.

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