Golang concise solution with explanation


  • 0

    Somehow we need to store info whether each row and column should fill with 0, or not.
    We can of course use extra space for that purpose, but actually we can use 0 th row and column value for that, because if the row and column will be filled with 0, anyway the 0 th element will also be 0.

    But one thing critically we should notice is, after finishing marking to 0 th index, we iterate through the matrix again and do

    1. Current element is matrix[m][n]
    2. If either matrix[0][n] or matrix[m][0] is marked as 0, then set 0 to matrix[m][n].

    But if we do this step on 0 th row and column itself, we will ruin the markers themselves! 😳
    We need to carefully avoid setting 0 to one element will affect another element's result.

    So, to avoid this we need to handle 0 th row and column separately from other elements, and these should be processed lastly. (That is the reason why I iterate through from end to stat when calling set. You can alternatively iterate from 1 to end then process 0th row and column later)

    zeroRow and zeroCol flag stores whether 0 th row and column should be set as 0.
    For other rows and columns, we can apply the step mentioned above.

    func setZeroes(matrix [][]int) {
    	mlen := len(matrix)
    	if mlen == 0 {
    		return
    	}
    	nlen := len(matrix[0])
    
    	zeroRow, zeroCol := false, false
    	for m := 0; m < mlen; m++ {
    		for n := 0; n < nlen; n++ {
    			mark(matrix, m, n, &zeroRow, &zeroCol)
    		}
    	}
    	for m := mlen - 1; m >= 0; m-- {
    		for n := nlen - 1; n >= 0; n-- {
    			set(matrix, m, n, zeroRow, zeroCol)
    		}
    	}
    }
    
    func mark(matrix [][]int, m, n int, zeroRow, zeroCol *bool) {
    	switch {
    	case m == 0 && n == 0:
    		if matrix[m][n] == 0 {
    			*zeroRow, *zeroCol = true, true
    		}
    	case m == 0:
    		if matrix[m][n] == 0 {
    			*zeroRow = true
    		}
    	case n == 0:
    		if matrix[m][n] == 0 {
    			*zeroCol = true
    		}
    	default:
    		if matrix[m][n] == 0 {
    			matrix[m][0] = 0
    			matrix[0][n] = 0
    		}
    	}
    }
    
    func set(matrix [][]int, m, n int, zeroRow, zeroCol bool) {
    	switch {
    	case m == 0 && n == 0:
    		if zeroRow || zeroCol {
    			matrix[m][n] = 0
    		}
    	case m == 0:
    		if zeroRow {
    			matrix[m][n] = 0
    		}
    	case n == 0:
    		if zeroCol {
    			matrix[m][n] = 0
    		}
    	default:
    		if matrix[0][n] == 0 || matrix[m][0] == 0 {
    			matrix[m][n] = 0
    		}
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.