Set Matrix Zeroes

Medium

The problem

If a cell of matrix is 0, set its entire row and entire column to 0. Change the matrix itself; the function returns nothing. Only zeros that were in the original matrix cause rows and columns to be cleared.

Example 1
Input: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: matrix becomes [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
The 0 in the middle clears the middle row and the middle column.
Example 2
Input: matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Output: matrix becomes [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
The zeros in the first row clear columns 0 and 3 plus the first row.

Limits

1 ≤ rows, columns ≤ 200
-2,147,483,648 ≤ matrix[r][c] ≤ 2,147,483,647
Edit the matrix in place

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You need to remember which rows and columns to clear. Where can you store that without extra memory?

The idea

Use the first row and first column as markers (with two flags for whether they themselves need zeroing).

Target: O(m·n) time, O(1) space

Go function shape

func setZeroes(matrix [][]int)

Reference solution

Tested with go test. Try it yourself first, then compare.

// SetZeroes zeroes the whole row and column of every 0, using O(1) extra memory: the first row and first column
// double as the "clear this row / column" markers. Two flags remember whether those two themselves need clearing.
func SetZeroes(m [][]int) {
	rows, cols := len(m), len(m[0])
	firstRow, firstCol := false, false
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if m[r][c] == 0 {
				if r == 0 {
					firstRow = true
				}
				if c == 0 {
					firstCol = true
				}
				m[r][0], m[0][c] = 0, 0 // mark the row and the column
			}
		}
	}
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			if m[r][0] == 0 || m[0][c] == 0 {
				m[r][c] = 0
			}
		}
	}
	if firstRow {
		for c := 0; c < cols; c++ {
			m[0][c] = 0
		}
	}
	if firstCol {
		for r := 0; r < rows; r++ {
			m[r][0] = 0
		}
	}
}

Read the lesson: Bit Manipulation & Math