661. Image Smoother #

Problem #

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:

1. The value in the given matrix is in the range of [0, 255].
2. The length and width of the given matrix are in the range of [1, 150].

Problem Summary #

A 2D integer matrix M represents the grayscale of an image. You need to design a smoother so that the grayscale of each cell becomes the average grayscale (rounded down). The average grayscale is calculated by averaging the values of the 8 surrounding cells and the cell itself. If there are fewer than 8 surrounding cells, use as many as possible.

Note:

• The integer values in the given matrix are in the range [0, 255].
• The length and width of the matrix are both in the range [1, 150].

Solution Approach #

• Change each element in the 2D array to the average of the 9 surrounding elements.
• This is an easy problem; just calculate the average according to the problem statement. Note the boundary issues: for the four corners and the elements on the edges, there are fewer than 9 elements when calculating the average.

Code #

package leetcode

func imageSmoother(M [][]int) [][]int {
	res := make([][]int, len(M))
	for i := range M {
		res[i] = make([]int, len(M[0]))
	}
	for y := 0; y < len(M); y++ {
		for x := 0; x < len(M[0]); x++ {
			res[y][x] = smooth(x, y, M)
		}
	}
	return res
}

func smooth(x, y int, M [][]int) int {
	count, sum := 1, M[y][x]
	// Check bottom
	if y+1 < len(M) {
		sum += M[y+1][x]
		count++
	}
	// Check Top
	if y-1 >= 0 {
		sum += M[y-1][x]
		count++
	}
	// Check left
	if x-1 >= 0 {
		sum += M[y][x-1]
		count++
	}
	// Check Right
	if x+1 < len(M[y]) {
		sum += M[y][x+1]
		count++
	}
	// Check Coners
	// Top Left
	if y-1 >= 0 && x-1 >= 0 {
		sum += M[y-1][x-1]
		count++
	}
	// Top Right
	if y-1 >= 0 && x+1 < len(M[0]) {
		sum += M[y-1][x+1]
		count++
	}
	// Bottom Left
	if y+1 < len(M) && x-1 >= 0 {
		sum += M[y+1][x-1]
		count++
	}
	//Bottom Right
	if y+1 < len(M) && x+1 < len(M[0]) {
		sum += M[y+1][x+1]
		count++
	}
	return sum / count
}