Set Matrix Zeroes In Place in DSA Go

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a grid of lights where if one light goes off, the whole row and column of lights must also turn off, but you only have one small notebook to remember which rows and columns to turn off.

Matrix before:
1 2 3
4 0 6
7 8 9

We mark row 1 and column 1 to zero later.

Dry Run Walkthrough

Input: matrix = [[1,2,3],[4,0,6],[7,8,9]]

Goal: Set entire row and column to zero for each zero cell, in place without extra matrix

Step 1: Scan first row and first column to check if they contain zero

First row: 1 2 3
First column: 1 4 7

Why: We need to know if first row or column should be zeroed later to avoid overwriting markers

Step 2: Use first row and first column as markers for zero rows and columns

Mark matrix[1][0] = 0 and matrix[0][1] = 0 because matrix[1][1] is zero
Matrix:
1 0 3
0 0 6
7 8 9

Why: Marking which rows and columns to zero without extra space

Step 3: Zero rows based on first column markers

Row 1 zeroed: 0 0 0
Matrix:
1 0 3
0 0 0
7 8 9

Why: Row 1 contains zero, so set entire row to zero

Step 4: Zero columns based on first row markers

Column 1 zeroed for rows 1+: set matrix[2][1] = 0
Matrix:
1 0 3
0 0 0
7 0 9

Why: Column 1 contains zero, so set entire column to zero

Step 5: Zero first row if needed (not needed here)

First row unchanged: 1 0 3

Why: First row did not originally contain zero

Step 6: Zero first column if needed (not needed here)

First column unchanged: 1 0 7

Why: First column did not originally contain zero

Result:

Final matrix:
1 0 3
0 0 0
7 0 9

Annotated Code

DSA Go

package main

import "fmt"

func setZeroes(matrix [][]int) {
	if len(matrix) == 0 {
		return
	}
	rows := len(matrix)
	cols := len(matrix[0])

	firstRowZero := false
	firstColZero := false

	// Check if first row has zero
	for c := 0; c < cols; c++ {
		if matrix[0][c] == 0 {
			firstRowZero = true
			break
		}
	}

	// Check if first column has zero
	for r := 0; r < rows; r++ {
		if matrix[r][0] == 0 {
			firstColZero = true
			break
		}
	}

	// Use first row and column as markers
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			if matrix[r][c] == 0 {
				matrix[r][0] = 0 // mark row
				matrix[0][c] = 0 // mark column
			}
		}
	}

	// Zero rows based on markers
	for r := 1; r < rows; r++ {
		if matrix[r][0] == 0 {
			for c := 1; c < cols; c++ {
				matrix[r][c] = 0
			}
		}
	}

	// Zero columns based on markers
	for c := 1; c < cols; c++ {
		if matrix[0][c] == 0 {
			for r := 1; r < rows; r++ {
				matrix[r][c] = 0
			}
		}
	}

	// Zero first row if needed
	if firstRowZero {
		for c := 0; c < cols; c++ {
			matrix[0][c] = 0
		}
	}

	// Zero first column if needed
	if firstColZero {
		for r := 0; r < rows; r++ {
			matrix[r][0] = 0
		}
	}
}

func printMatrix(matrix [][]int) {
	for _, row := range matrix {
		for i, val := range row {
			if i > 0 {
				fmt.Print(" ")
			}
			fmt.Print(val)
		}
		fmt.Println()
	}
}

func main() {
	matrix := [][]int{
		{1, 2, 3},
		{4, 0, 6},
		{7, 8, 9},
	}
	setZeroes(matrix)
	printMatrix(matrix)
}

for c := 0; c < cols; c++ { if matrix[0][c] == 0 { firstRowZero = true break } }

Check if first row contains zero to handle it later

for r := 0; r < rows; r++ { if matrix[r][0] == 0 { firstColZero = true break } }

Check if first column contains zero to handle it later

for r := 1; r < rows; r++ { for c := 1; c < cols; c++ { if matrix[r][c] == 0 { matrix[r][0] = 0 matrix[0][c] = 0 } } }

Mark rows and columns to be zeroed using first row and column

for r := 1; r < rows; r++ { if matrix[r][0] == 0 { for c := 1; c < cols; c++ { matrix[r][c] = 0 } } }

Zero entire rows based on markers

for c := 1; c < cols; c++ { if matrix[0][c] == 0 { for r := 1; r < rows; r++ { matrix[r][c] = 0 } } }

Zero entire columns based on markers

if firstRowZero { for c := 0; c < cols; c++ { matrix[0][c] = 0 } }

Zero first row if it originally contained zero

if firstColZero { for r := 0; r < rows; r++ { matrix[r][0] = 0 } }

Zero first column if it originally contained zero

Output

1 0 3

0 0 0

7 0 9

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each cell is visited a constant number of times

Space: O(1) because we use the matrix itself for marking without extra space

vs Alternative: Naive approach uses extra space O(m+n) to store zero rows and columns; this approach saves space by using the matrix as markers

Edge Cases

Empty matrix

Function does nothing and returns immediately

DSA Go

if len(matrix) == 0 {
	return
}
rows := len(matrix)
cols := len(matrix[0])

Matrix with no zeros

Matrix remains unchanged

DSA Go

for r := 1; r < rows; r++ {
	for c := 1; c < cols; c++ {
		if matrix[r][c] == 0 {
			matrix[r][0] = 0
			matrix[0][c] = 0
		}
	}
}

Matrix with zeros in first row and first column

First row and/or column zeroed at the end correctly

DSA Go

if firstRowZero {
	for c := 0; c < cols; c++ {
		matrix[0][c] = 0
	}
}
if firstColZero {
	for r := 0; r < rows; r++ {
		matrix[r][0] = 0
	}
}

When to Use This Pattern

When you need to set entire rows and columns to zero based on zero cells without extra space, use the in-place marker pattern with first row and column as flags.

Common Mistakes

Mistake: Overwriting first row or column markers too early and losing information
Fix: Check and store if first row or column originally had zero before using them as markers

Mistake: Not handling first row and first column separately at the end
Fix: Use separate boolean flags to zero first row and column after processing other rows and columns

Summary

Sets entire rows and columns to zero in a matrix if any cell in them is zero, without extra space.

Use when you want to modify the matrix in place efficiently without extra memory.

Use the first row and column as markers to remember which rows and columns to zero, and handle them separately.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Modify the matrix so that if an element is 0, its entire row and column become 0

B. Find the sum of all elements in the matrix

C. Sort each row of the matrix in ascending order

D. Transpose the matrix without changing its elements

Solution

1. Step 1: Understand the problem requirement

   The problem asks to change the matrix so that any row or column containing a zero should be set entirely to zero.

2. Step 2: Identify the correct operation

   Only Modify the matrix so that if an element is 0, its entire row and column become 0 describes this exact operation, modifying rows and columns based on zero elements.

3. Final Answer:

   Modify the matrix so that if an element is 0, its entire row and column become 0 -> Option A

4. Quick Check:

   Set rows and columns to zero = Modify matrix [OK]

Hint: Remember: zero means zero out whole row and column [OK]

Common Mistakes:

• Confusing with matrix transpose
• Trying to sum elements instead of modifying
• Sorting rows instead of zeroing

2. Which of the following Go code snippets correctly declares a fixed-size 2D array of integers?

easy

A. matrix := [][]int{{1, 2}, {3, 4}}

B. matrix := [2][2]int{{1, 2}, {3, 4}}

C. matrix := [][]int{1, 2, 3, 4}

D. matrix := [2]int{1, 2, 3, 4}

Solution

1. Step 1: Understand Go 2D array declaration

   In Go, fixed-size 2D arrays use syntax like [rows][cols]type, so [2][2]int is a 2x2 matrix.

2. Step 2: Check each option

   matrix := [2][2]int{{1, 2}, {3, 4}} correctly declares a 2x2 integer array with values. matrix := [][]int{{1, 2}, {3, 4}} is a slice of slices (dynamic), not a fixed-size array. matrix := [][]int{1, 2, 3, 4} and D are invalid for 2D matrix.

3. Final Answer:

   matrix := [2][2]int{{1, 2}, {3, 4}} -> Option B

4. Quick Check:

   Fixed 2D array syntax = [2][2]int [OK]

Hint: Use [rows][cols]type for fixed 2D arrays in Go [OK]

Common Mistakes:

• Using slice syntax when fixed array needed
• Incorrect nesting of braces
• Declaring 1D array instead of 2D

3. What will be the matrix after running the following Go code snippet?

matrix := [][]int{
  {1, 2, 3},
  {4, 0, 6},
  {7, 8, 9},
}
// After applying Set Matrix Zeroes In Place logic
// (zero out rows and columns containing zero)

medium

A. [[1, 0, 3], [0, 0, 0], [0, 0, 0]]

B. [[1, 2, 3], [0, 0, 0], [7, 0, 9]]

C. [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

D. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions

   Zero is at matrix[1][1]. So row 1 and column 1 must be zeroed.

2. Step 2: Apply zeroing

   Row 1 becomes [0,0,0]. Column 1 elements at rows 0 and 2 become 0. So matrix[0][1] and matrix[2][1] are zero.

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option C

4. Quick Check:

   Zero row and column applied correctly = [[1,0,3],[0,0,0],[7,0,9]] [OK]

Hint: Zero entire row and column for each zero found [OK]

Common Mistakes:

• Zeroing entire matrix
• Missing zero in column 1 for rows 0 and 2
• Zeroing wrong rows or columns

4. Consider this Go function snippet for setting matrix zeroes:

func setZeroes(matrix [][]int) {
  for i := 0; i < len(matrix); i++ {
    for j := 0; j < len(matrix[0]); j++ {
      if matrix[i][j] == 0 {
        for k := 0; k < len(matrix); k++ {
          matrix[k][j] = 0
        }
        for l := 0; l < len(matrix[0]); l++ {
          matrix[i][l] = 0
        }
      }
    }
  }
}

What is the main problem with this code?

medium

A. It only zeros rows but not columns

B. It uses wrong loop ranges for rows and columns

C. It does not check for zero elements at all

D. It modifies the matrix while iterating, causing incorrect zeroing

Solution

1. Step 1: Analyze matrix modification during iteration

   The code sets zeros immediately when it finds a zero, changing matrix elements during iteration.

2. Step 2: Understand side effects

   This causes new zeros to appear and triggers more zeroing incorrectly, leading to wrong final matrix.

3. Final Answer:

   It modifies the matrix while iterating, causing incorrect zeroing -> Option D

4. Quick Check:

   In-place modification during scan = incorrect zeroing [OK]

Hint: Mark zeros first, then update matrix to avoid side effects [OK]

Common Mistakes:

• Changing matrix while scanning
• Not using extra storage or flags
• Assuming immediate zeroing is safe

5. You want to set matrix zeroes in place with O(1) extra space. Which approach below correctly achieves this in Go?

hard

A. Use first row and first column as markers to track zero rows and columns, then update matrix accordingly

B. Create a separate boolean matrix to mark zero rows and columns, then update original matrix

C. Copy matrix to a new matrix and update zeros there to avoid modifying original during iteration

D. Use recursion to zero rows and columns when zero found

Solution

1. Step 1: Understand space constraints

   O(1) extra space means no additional matrix or large data structures allowed.

2. Step 2: Use first row and column as markers

   Mark zeros in first row and column to remember which rows and columns to zero later, then update matrix in place.

3. Step 3: Avoid extra space and recursion

   Options A and B use extra space, D uses recursion unnecessarily.

4. Final Answer:

   Use first row and first column as markers to track zero rows and columns, then update matrix accordingly -> Option A

5. Quick Check:

   In-place markers = O(1) space zeroing [OK]

Hint: Use matrix edges as flags to save space [OK]

Common Mistakes:

• Using extra arrays violating space constraint
• Modifying matrix during iteration without markers
• Overcomplicating with recursion