Find the Grid of Region Average
You are given an m x n grid image which represents a grayscale image, where image[i][j] represents a pixel with intensity in the range [0..255]. You are also given a non-negative integer threshold.
Two pixels are adjacent if they share an edge.
A region is a 3 x 3 subgrid where the absolute difference in intensity between any two adjacent pixels is less than or equal to threshold.
All pixels in a region belong to that region. A pixel can belong to multiple regions.
You need to calculate an m x n grid result, where:
result[i][j]is the average intensity of the regions to whichimage[i][j]belongs, rounded down to the nearest integer.- If
image[i][j]belongs to multiple regions,result[i][j]is the average of the rounded-down average intensities of these regions, rounded down to the nearest integer. - If
image[i][j]does not belong to any region,result[i][j]is equal toimage[i][j].
Return the grid result.
Example 1
5 6 7 10 8 9 10 10 11 12 13 10
Input
image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3Output
[[9,9,9,9],[9,9,9,9],[9,9,9,9]]There are two valid regions, both have rounded-down average intensity 9, and every pixel belongs to at least one of them, so every result value is 9.
Example 2
10 20 30 15 25 35 20 30 40 25 35 45
Input
image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12Output
[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]The first valid region has average 25 and the second has average 30, so pixels in both regions get floor((25 + 30) / 2) = 27 while pixels in only one region get that region's average.
Constraints
- 3 <= n, m <= 500
- 0 <= image[i][j] <= 255
- 0 <= threshold <= 255
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.