Set Matrix Zeroes - Python Solution

1. Introduction

"Set Matrix Zeroes" is a problem that deals with array manipulation, specifically focusing on modifying a matrix in place. The challenge is to set entire rows and columns to zero in a matrix if any cell in them is zero. This problem tests one’s ability to efficiently navigate and manipulate 2D arrays without using additional space for storage.

Problem

Given an m x n integer matrix, the task is to set an entire row and column to zeros if any element in that row or column is zero. The key constraint is to do this in place, without using extra space for another matrix.

2. Solution Steps

1. First, determine if the first row and first column need to be set to zero separately.

2. Traverse the matrix and use the first row and first column to mark zero rows and columns.

3. Iterate over the matrix again and use the marks to set elements to zero.

4. Finally, set the first row and first column to zero if needed.

3. Code Program

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))

    # Mark zeros on first row and column
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0

    # Use marks to set elements to zero
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    # Set first row and column to zero if needed
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

# Example Usage
matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
setZeroes(matrix)
print(matrix)  # Output: [[1,0,1],[0,0,0],[1,0,1]]

Output:

[[1,0,1],[0,0,0],[1,0,1]]

Explanation:

1. Initial Checks: The existence of zeroes in the first row and column is checked and stored.

2. Marking Rows and Columns: The first row and column are used to mark which rows and columns should be set to zero.

3. Applying Zeroes: The matrix is traversed again, setting elements to zero based on the marks in the first row and column.

4. Zeroing First Row and Column: Based on the initial checks, the first row and/or column are set to zero if necessary.

5. In-Place Modification: The matrix is modified in place, adhering to the problem's space constraint.

6. Efficient Solution: The solution efficiently traverses the matrix with a time complexity of O(m*n) and does not use extra space, making it optimal for large matrices.