Leetcode 73. Set Matrix Zero

Description:

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Example:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Constraints:

• m == matrix.length

• n == matrix[0].length

• 1 <= m, n <= 200

• -2^31 <= matrix[i][j] <= 2^31 - 1

---

Solution:

Brute force approach:

The steps are the following:

1. 1. First, we will use two loops (nested loops) to traverse all the cells of the matrix.

      2. If any cell (i, j) contains the value 0, we will mark all cells in row i and column j with -1 except those that contain 0.

      3. We will perform step 2 for every cell containing 0.

      4. Finally, we will mark all the cells containing -1 with 0.

      5. Thus, the given matrix will be modified according to the question.

Pseudo Code:

function markRow(matrix, n, m, i):
    for j from 0 to m-1:
        if matrix[i][j] != 0:
            matrix[i][j] = -1

function markCol(matrix, n, m, j):
    for i from 0 to n-1:
        if matrix[i][j] != 0:
            matrix[i][j] = -1

function zeroMatrix(matrix, n, m):
    for i from 0 to n-1:
        for j from 0 to m-1:
            if matrix[i][j] == 0:
                markRow(matrix, n, m, i)
                markCol(matrix, n, m, j)

    for i from 0 to n-1:
        for j from 0 to m-1:
            if matrix[i][j] == -1:
                matrix[i][j] = 0

    return matrix

matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

n = size of rows in matrix
m = size of columns in matrix

ans = zeroMatrix(matrix, n, m)

print("The Final matrix is: ")
for each row in ans:
    for each element in row:
        print(element + " ")
    print()

Time Complexity:

O(NM(N+M)) + O(NM), where N = number of rows in the matrix and M = number of columns in the matrix. Explanation: Traversing the matrix to find cells with value 0 takes O(NM). For each zero cell found, marking its row and column with -1 takes O(N+M). Thus, the total time complexity is O(NM(N+M)). Finally, marking all -1 cells as 0 takes O(N*M).

Space Complexity:

O(1), as no extra space is used apart from the input matrix.

---

Better approach:

The steps are as follows:

1. First, we will declare two arrays: a row array of size N and a col array of size M and both are initialized with 0.

2. Then, we will use two loops (nested loops) to traverse all the cells of the matrix.

3. If any cell (i, j) contains the value 0, we will mark ith index of row array i.e. row[i] and jth index of col array col[j], as 1. It signifies that all the elements in the ith row and jth column will be 0 in the final matrix.

4. We will perform step 3 for every cell containing 0.

5. Finally, we will again traverse the entire matrix and we will put 0 into all the cells (i, j) for which either row[i] or col[j] is marked as 1.

6. Thus we will get our final matrix.

Pseudo Code:

function zeroMatrix(matrix, n, m):
    row = array of size n, initialized to 0
    col = array of size m, initialized to 0

    // Mark rows and columns containing zeros
    for i from 0 to n-1:
        for j from 0 to m-1:
            if matrix[i][j] == 0:
                row[i] = 1
                col[j] = 1

    // Zero out rows and columns
    for i from 0 to n-1:
        for j from 0 to m-1:
            if row[i] == 1 OR col[j] == 1:
                matrix[i][j] = 0
    return matrix

// Example usage
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

n = number of rows in matrix
m = number of columns in matrix

ans = zeroMatrix(matrix, n, m)

print "The Final matrix is: "
for each row in ans:
    for each element in row:
        print (element + " ")
    print (new line)

Time Complexity:

O(2*(N*M)), where N = the number of rows in the matrix and M = the number of columns in the matrix.
Reason: We are traversing the entire matrix 2 times and each traversal takes O(N*M) time.

Space Complexity:

O(N) + O(M), where N = no. of rows in the matrix and M = no. of columns in the matrix.
Reason: O(N) is for using the row array, and O(M) is for using the col array.

---

Optimal Approach:

The steps are as follows:

1. First, we will traverse the matrix and mark the proper cells of 1st row and 1st column with 0 accordingly. The marking will be like this: if cell(i, j) contains 0, we will mark the i-th row, i.e. matrix[i][0] with 0 and we will mark j-th column i.e. matrix[0][j] with 0.
   If i is 0, we will mark matrix[0][0] with 0 but if j is 0, we will mark the col0 variable with 0 instead of marking matrix[0][0] again.

2. After step 1 is completed, we will modify the cells from (1,1) to (n-1, m-1) using the values from the 1st row, 1st column, and col0 variable.
   We will not modify the 1st row and 1st column of the matrix here, as the modification of the rest of the matrix(i.e. From (1,1) to (n-1, m-1)) is dependent on that row and column.

3. Finally, we will change the 1st row and column using the values from the matrix[0][0] and col0 variables. Here also, we will change the row first and then the column.
   If matrix[0][0] = 0, we will change all the elements from the cell (0,1) to (0, m-1), to 0.
   If col0 = 0, we will change all the elements from the cell (0,0) to (n-1, 0) to 0.

Pseudo Code:

function zeroMatrix(matrix, n, m):
    col0 = 1

    // Step 1: Mark the first row and column
    for i from 0 to n-1:
        for j from 0 to m-1:
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                if j != 0:
                    matrix[0][j] = 0
                else:
                    col0 = 0

    // Step 2: Zero out the rest of the matrix based on marks
    for i from 1 to n-1:
        for j from 1 to m-1:
            if matrix[i][0] == 0 OR matrix[0][j] == 0:
                matrix[i][j] = 0

    // Step 3: Zero out the first row and column if necessary
    if matrix[0][0] == 0:
        for j from 0 to m-1:
            matrix[0][j] = 0
    if col0 == 0:
        for i from 0 to n-1:
            matrix[i][0] = 0

    return matrix

// Example usage
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

n = number of rows in matrix
m = number of columns in matrix

ans = zeroMatrix(matrix, n, m)

print "The Final matrix is: "
for each row in ans:
    for each element in row:
        print (element + " ")
    print (new line)

Time Complexity:

O(2*(N*M)), where N = the number of rows in the matrix and M = the number of columns in the matrix.
Reason: In this approach, we are also traversing the entire matrix 2 times and each traversal takes O(N*M) time.

Space Complexity:

O(1), as we are not using any extra space.

---

Conclusion:

In this problem, we explored three different approaches to set zeros in a matrix: brute force, better, and optimal. Each approach offers a different trade-off between time and space complexity.

• The brute force approach is simple but inefficient, requiring multiple passes through the matrix.

• The better approach reduces the space complexity by using additional arrays to mark rows and columns to be zeroed out.

• The optimal approach achieves O(1) space complexity by cleverly using the first row and column of the matrix as markers.

If you enjoy detailed problem-solving approaches like this, consider following my page for more content. You can also connect with me on LinkedIn, Twitter, and GitHub for updates and more coding insights.