Set Matrix Zeroes - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Set Matrix Zeroes" Problem in Go

Difficulty: Medium | Tags: Array, Hash Table, Matrix

Introduction

The "Set Matrix Zeroes" problem requires modifying a matrix in-place such that if an element is zero, its entire row and column are set to zero. This problem tests your ability to optimize space usage while manipulating matrix data.

Problem Analysis

Given an m x n matrix, the task is to scan the matrix and, for every zero encountered, set all elements in its row and column to zero. The challenge lies in doing this efficiently without using extra space for tracking zero positions. The examples provided illustrate how the transformation should work.

Solution Approach

The optimal solution involves using the first row and first column of the matrix to mark which rows and columns need to be zeroed out. This avoids using additional space. Here's the step-by-step approach:

  1. Check if the first row or column needs to be zeroed out.
  2. Use the first row and column to mark zero positions in the rest of the matrix.
  3. Iterate through the matrix and zero out marked rows and columns.
  4. Finally, zero out the first row and column if needed.

Go Implementation


func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    firstRowHasZero := false
    firstColHasZero := false
    // Check if first row has zero
    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowHasZero = true
            break
        }
    }
    // Check if first column has zero
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColHasZero = true
            break
        }
    }
    // Mark zeros on first row and column
    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
            }
        }
    }
    // Zero out marked rows and columns
    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
            }
        }
    }
    // Zero out first row if needed
    if firstRowHasZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }
    // Zero out first column if needed
    if firstColHasZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

Complexity Analysis

The time complexity is O(m * n) since we traverse the matrix multiple times but each traversal is linear. The space complexity is O(1) because we use the matrix's first row and column for marking, avoiding additional storage.

Testing and Examples

Test the solution with the provided examples:

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]]

Edge cases include matrices with all zeros, single-row or single-column matrices, and matrices with no zeros.

Best Practices and Tips

Key takeaways include leveraging the matrix itself for marking to save space, carefully handling the first row and column, and ensuring all edge cases are tested. Always verify the solution with multiple test cases to ensure correctness.

Read more