NUHMAN.com

Introduction

LeetCode 73: Set Matrix Zeroes is a problem that tests your understanding of matrix manipulation and space optimization. It involves setting entire rows and columns to zero in a matrix based on certain conditions. The challenge emphasizes the need for in-place modifications without using extra space for an additional matrix.

This problem is commonly used in coding interviews to assess your ability to work with 2D arrays and optimize space complexity.

Problem Statement

Given an m x n matrix, if an element in the matrix is 0, set its entire row and its entire column to 0 in place.

Do not use extra space for another matrix. You must do it in O(1) space.

Examples:

go

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

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Approach:

The key idea is to utilize the first row and first column of the matrix to store information about whether a row or column should be set to zero. This allows us to avoid using extra space.

Steps:

1. First, check if the first row and first column contain any zeroes. We will use these to keep track of which rows and columns should be zeroed.
2. Mark the first row and first column:

• Traverse the matrix, and if any element is zero, mark the corresponding row's first element and column's first element as zero.

1. Set zeroes in the rest of the matrix:

• Traverse from the second row and second column. If any element in the matrix is zero, set its row and column's first element to zero.

1. Update the matrix:

• Set each element to zero based on the markers in the first row and first column.

1. Handle the first row and column separately:

• Finally, update the first row and first column if needed.

Go Implementation

go

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    firstRowZero, firstColZero := false, false
    
    // Check if the first row has any zero
    for i := 0; i < n; i++ {
        if matrix[0][i] == 0 {
            firstRowZero = true
            break
        }
    }
    
    // Check if the first column has any zero
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColZero = true
            break
        }
    }
    
    // Use first row and column to mark zero rows and columns
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    // Set the zeroes based on marks in the first row and column
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }

    // Set the first row and first column to zero if needed
    if firstRowZero {
        for i := 0; i < n; i++ {
            matrix[0][i] = 0
        }
    }
    if firstColZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

Explanation

• First check for zeroes in the first row and first column.
• Marking: Use the first row and first column to store information about which rows and columns should be set to zero.
• Setting zeroes: After marking, update the matrix by setting zeroes in the appropriate rows and columns.
• Final adjustments: Finally, handle the special case of the first row and first column.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(1)

Where m is the number of rows and n is the number of columns. The solution uses O(1) extra space as it modifies the matrix in place.

Edge Cases

• Empty matrix: An empty matrix should be handled without any errors.
• Single row/column: Ensure that edge cases like a single row or column are handled correctly.
• All elements are zero: If the matrix already contains only zeroes, it should remain unchanged.
• No zeroes in matrix: If there are no zeroes in the matrix, the function should not alter the matrix.

Conclusion

LeetCode 73 is a great problem for learning how to handle matrix manipulations in place while avoiding extra space usage. This solution is efficient, with O(m * n) time complexity and O(1) space complexity, making it suitable for large matrices.

The use of the first row and column for storing state is a simple yet powerful optimization technique to solve this problem.