Go O(mn) time O(n) space, with comments


  • 0
    A
    func findLonelyPixel(picture [][]byte) int {
    	dp := make([]int, len(picture[0]))
    	for i, p := range picture { // For each row
    		z := 0                // location of potentially lonely pixel in this row; -1 = 2+ pixels in this row
    		for j, x := range p { // For each column
    			if x == 'B' {
    				if z == 0 { // This is the first black pixel in this row
    					z = j + 1 // +1 to offset from zero, consistent with zero-intialize of dp
    				} else {
    					z = -1 // This row isn't lonely
    				}
    				if dp[j] > 0 { // In all cases of a black pixel, check the column for an upper neighbor
    					dp[j] = -1 // This column isn't lonely
    				}
    			}
    		}
    		if z > 0 { // If we were lonely in this row
    			j := z - 1      // recover the index
    			if dp[j] == 0 { // If this column is currently lonely
    				dp[j] = i + 1 // Mark this row as the owner of this column
    			}
    		}
    	}
    
    	count := 0
    	for _, v := range dp { // count the columns that are still owned by a lonely pixel
    		if v > 0 {
    			count++
    		}
    	}
    	return count
    }
    

Log in to reply
 

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