Set Matrix Zeroes

 

Problem Statement: Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

1. Clarify the problem:

  • Can we assume that the matrix is valid (non-empty)?
  • How do we handle an empty matrix as input?

2. Analyze the problem:

  • Input: Matrix (2D array)
  • Output: None (in-place modification of the matrix)
  • Constraints:
    • The matrix can be empty.
    • The matrix can have multiple rows and columns.

3. Design an algorithm:

  • Iterate through the matrix to find the positions of all zeros.
  • Use two sets to store the row and column indices of the zeros.
  • Iterate through the matrix again and set the corresponding rows and columns to zeros.

4. Explain your approach:

  • We will iterate through the matrix to find the positions of all zeros, storing their row and column indices in two separate sets.
  • Then, we will iterate through the matrix again and set the elements in the corresponding rows and columns to zeros.

5. Write clean and readable code:

python
class Solution:
    def setZeroes(self, matrix):
        if not matrix or not matrix[0]:
            return

        rows = set()
        cols = set()

        # Find positions of zeros
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        # Set rows and columns to zeros
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in rows or j in cols:
                    matrix[i][j] = 0

6. Test your code: Let's test the code with some example and additional test cases:

python
# Example test case
solution = Solution()
matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
solution.setZeroes(matrix)
# Expected output: matrix = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

# Additional test cases
matrix = []
solution.setZeroes(matrix)
# Expected output: matrix = []

matrix = [[]]
solution.setZeroes(matrix)
# Expected output: matrix = [[]]

matrix = [[1]]
solution.setZeroes(matrix)
# Expected output: matrix = [[1]]

matrix = [[0]]
solution.setZeroes(matrix)
# Expected output: matrix = [[0]]

matrix = [
    [1, 2, 3],
    [4, 0, 6],
    [7, 8, 9]
]
solution.setZeroes(matrix)
# Expected output: matrix = [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

7. Optimize if necessary: The provided solution has a time complexity of O(m * n), where m is the number of rows and n is the number of columns in the matrix. We iterate through the matrix twice to find the positions of zeros and set the corresponding rows and columns to zeros. The space complexity is O(m + n) since we use two sets to store the row and column indices of the zeros.

8. Handle error cases: The code handles the case where the input matrix is empty or has an empty row. In such cases, the code returns without making any modifications to the matrix.

9. Discuss complexity analysis: The time complexity of the solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix. The space complexity is O(m + n) since we use two sets to store the row and column indices of the zeros. The solution is optimal in terms of time complexity as we need to visit each element at least once to determine the zeros and update the matrix accordingly.

Next Post Previous Post