73. Set Matrix Zeroes #

Problem #

Given an *m* x *n* matrix. If an element is 0, set its entire row and column to 0. Do it  in-place.

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

Example 1:

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

Example 2:

Input: matrix = [[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]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• 2^31 <= matrix[i][j] <= 2^31 - 1

Problem Summary #

Given an m x n matrix, if an element is 0, set all elements in its row and column to 0. Please use an in-place algorithm.

Solution Approach #

• This problem tests the ability to control the program; there is no algorithmic idea involved. The problem requires using an in-place algorithm, so all modifications are performed on the original two-dimensional array. There are 2 special positions in the two-dimensional array: the first row and the first column. Their special property is that as long as either of them contains a 0, they will become entirely 0. First use 2 variables to record whether this row and this column contain a 0, to prevent subsequent modifications from overwriting these 2 places. Then, excluding this row and this column, check whether the remaining part contains a 0. If there is a 0, mark the first element of its row as 0 and the first element of its column as 0. Finally, use the marks to set the corresponding rows and columns to 0.

Code #

package leetcode

func setZeroes(matrix [][]int) {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return
	}
	isFirstRowExistZero, isFirstColExistZero := false, false
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			isFirstColExistZero = true
			break
		}
	}
	for j := 0; j < len(matrix[0]); j++ {
		if matrix[0][j] == 0 {
			isFirstRowExistZero = true
			break
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
	// Set all rows [1:] to 0
	for i := 1; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			for j := 1; j < len(matrix[0]); j++ {
				matrix[i][j] = 0
			}
		}
	}
	// Set all columns [1:] to 0
	for j := 1; j < len(matrix[0]); j++ {
		if matrix[0][j] == 0 {
			for i := 1; i < len(matrix); i++ {
				matrix[i][j] = 0
			}
		}
	}
	if isFirstRowExistZero {
		for j := 0; j < len(matrix[0]); j++ {
			matrix[0][j] = 0
		}
	}
	if isFirstColExistZero {
		for i := 0; i < len(matrix); i++ {
			matrix[i][0] = 0
		}
	}
}