Skip to content

3030. Find the Grid of Region Average 👎

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
 public:
  vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
    const int m = image.size();
    const int n = image[0].size();
    vector<vector<int>> sums(m, vector<int>(n));
    vector<vector<int>> counts(m, vector<int>(n));

    for (int i = 0; i < m - 2; ++i)
      for (int j = 0; j < n - 2; ++j)
        if (isRegion(image, i, j, threshold)) {
          const int subgridSum = getSubgridSum(image, i, j);
          for (int x = i; x < i + 3; ++x)
            for (int y = j; y < j + 3; ++y) {
              sums[x][y] += subgridSum / 9;
              counts[x][y] += 1;
            }
        }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (counts[i][j] > 0)
          image[i][j] = sums[i][j] / counts[i][j];

    return image;
  }

 private:
  // Returns true if image[i..i + 2][j..j + 2] is a region.
  bool isRegion(const vector<vector<int>>& image, int i, int j, int threshold) {
    for (int x = i; x < i + 3; ++x)
      for (int y = j; y < j + 3; ++y) {
        if (x > i && abs(image[x][y] - image[x - 1][y]) > threshold)
          return false;
        if (y > j && abs(image[x][y] - image[x][y - 1]) > threshold)
          return false;
      }
    return true;
  }

  // Returns the sum of image[i..i + 2][j..j + 2].
  int getSubgridSum(const vector<vector<int>>& image, int i, int j) {
    int subgridSum = 0;
    for (int x = i; x < i + 3; ++x)
      for (int y = j; y < j + 3; ++y)
        subgridSum += image[x][y];
    return subgridSum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
  public int[][] resultGrid(int[][] image, int threshold) {
    final int m = image.length;
    final int n = image[0].length;
    int[][] sums = new int[m][n];
    int[][] counts = new int[m][n];

    for (int i = 0; i < m - 2; ++i)
      for (int j = 0; j < n - 2; ++j)
        if (isRegion(image, i, j, threshold)) {
          final int subgridSum = getSubgridSum(image, i, j);
          for (int x = i; x < i + 3; ++x)
            for (int y = j; y < j + 3; ++y) {
              sums[x][y] += subgridSum / 9;
              counts[x][y] += 1;
            }
        }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (counts[i][j] > 0)
          image[i][j] = sums[i][j] / counts[i][j];

    return image;
  }

  // Returns true if image[i..i + 2][j..j + 2] is a region.
  private boolean isRegion(int[][] image, int i, int j, int threshold) {
    for (int x = i; x < i + 3; ++x)
      for (int y = j; y < j + 3; ++y) {
        if (x > i && Math.abs(image[x][y] - image[x - 1][y]) > threshold)
          return false;
        if (y > j && Math.abs(image[x][y] - image[x][y - 1]) > threshold)
          return false;
      }
    return true;
  }

  // Returns the sum of image[i..i + 2][j..j + 2].
  private int getSubgridSum(int[][] image, int i, int j) {
    int subgridSum = 0;
    for (int x = i; x < i + 3; ++x)
      for (int y = j; y < j + 3; ++y)
        subgridSum += image[x][y];
    return subgridSum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
  def resultGrid(
      self,
      image: list[list[int]],
      threshold: int,
  ) -> list[list[int]]:
    m = len(image)
    n = len(image[0])
    sums = [[0] * n for _ in range(m)]
    counts = [[0] * n for _ in range(m)]

    for i in range(m - 2):
      for j in range(n - 2):
        if self._isRegion(image, i, j, threshold):
          subgridSum = sum(image[x][y]
                           for x in range(i, i + 3)
                           for y in range(j, j + 3))
          for x in range(i, i + 3):
            for y in range(j, j + 3):
              sums[x][y] += subgridSum // 9
              counts[x][y] += 1

    for i in range(m):
      for j in range(n):
        if counts[i][j] > 0:
          image[i][j] = sums[i][j] // counts[i][j]

    return image

  def _isRegion(
      self,
      image: list[list[int]],
      i: int,
      j: int,
      threshold: int,
  ) -> bool:
    """Returns True if image[i..i + 2][j..j + 2] is a region."""
    for x in range(i, i + 3):
      for y in range(j, j + 3):
        if x > i and abs(image[x][y] - image[x - 1][y]) > threshold:
          return False
        if y > j and abs(image[x][y] - image[x][y - 1]) > threshold:
          return False
    return True