Sponsored
Sponsored
This approach involves iterating over each cell and calculating the sum and count of valid neighbors in the 3x3 neighborhood range. For each cell, we consider neighboring cells that exist and are within bounds.
The time complexity is O(m * n * 9), which simplifies to O(m * n) because we are only performing a fixed amount of work per cell. The space complexity is O(m * n) for storing the result matrix.
1public class Solution {
2 public int[][] ImageSmoother(int[][] M) {
3 int m = M.Length, n = M[0].Length;
4 int[][] res = new int[m][];
5 for (int i = 0; i < m; i++) res[i] = new int[n];
6 int[][] dirs = { new int[]{ -1, -1 }, new int[]{ -1, 0 }, new int[]{ -1, 1 }, new int[]{ 0, -1 }, new int[]{ 0, 0 }, new int[]{ 0, 1 }, new int[]{ 1, -1 }, new int[]{ 1, 0 }, new int[]{ 1, 1 } };
7
8 for (int i = 0; i < m; ++i) {
9 for (int j = 0; j < n; ++j) {
10 int sum = 0, count = 0;
11 foreach (var d in dirs) {
12 int ni = i + d[0], nj = j + d[1];
13 if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
14 sum += M[ni][nj];
15 ++count;
16 }
17 }
18 res[i][j] = sum / count;
19 }
20 }
21 return res;
22 }
23}The C# solution similarly iterates over each pixel and the potential neighbors, using an array of direction vectors to simplify the checking of valid neighbors.
This approach leverages a sliding window technique within the 3x3 area, minimizing redundant calculations by reusing previously computed sums and counts from prior cells wherever applicable.
The time and space complexities remain as O(m * n) due to the sliding optimization remaining bounded per cell, though potentially with reduced constant factor.
1// Currently not provided for C# due to technical difficulty of efficiently implementing the sliding technique.A full C# implementation accounting for efficient in-memory sliding is deferred due to technical reasons.