My Solutions
1. Use the brute-force method\n\n/**\n * Time Complexity: O(rows * cols)\n * Space Complexity: O(rows * cols)\n * where `rows` is the number of the rows of the 
**1. Use the brute-force method**\n```\n/**\n * Time Complexity: O(rows * cols)\n * Space Complexity: O(rows * cols)\n * where `rows` is the number of the rows of the grid `image`\n *       `cols` is the number of the columns of the grid `image`\n */\nclass Solution {\n private:\n  static constexpr int region_size = 3;\n\n public:\n  vector<vector<int>> resultGrid(const vector<vector<int>> &image, const int threshold) {\n    const int rows = static_cast<int>(image.size());\n    const int cols = static_cast<int>(image.front().size());\n    vector<vector<pair<int, int>>> stats(rows, vector<pair<int, int>>(cols));\n    for (int start_r = 0; start_r + region_size - 1 < rows; ++start_r) {\n      for (int start_c = 0; start_c + region_size - 1 < cols; ++start_c) {\n        const auto [is_region, average] = get_region_stat(image, threshold, start_r, start_c);\n        if (is_region) {\n          apply_average(stats, start_r, start_c, average);\n        }\n      }\n    }\n    \n    vector<vector<int>> ret(rows, vector<int>(cols));\n    for (int r = 0; r < rows; ++r) {\n      for (int c = 0; c < cols; ++c) {\n        const auto [sum, count] = stats[r][c];\n        ret[r][c] = count == 0 ? image[r][c] : (sum / count);\n      }\n    }\n    return ret;\n  }\n  \n private:\n  pair<bool, int> get_region_stat(const vector<vector<int>> &image, const int threshold, const int start_r, const int start_c) {\n    constexpr int directions[] = {0, 1, 0};\n    constexpr int n_directions = 2;\n    const int end_r = start_r + region_size;\n    const int end_c = start_c + region_size;\n    bool is_region = true;\n    int sum = 0;\n    for (int r = start_r; is_region && r < end_r; ++r) {\n      for (int c = start_c; is_region && c < end_c; ++c) {\n        sum += image[r][c];\n        for (int d = 0; d < n_directions; ++d) {\n          const int nr = r + directions[d];\n          const int nc = c + directions[d + 1];\n          if (nr < end_r && nc < end_c && abs(image[r][c] - image[nr][nc]) > threshold) {\n            is_region = false;\n            sum = 0;\n            break;\n          }\n        }\n      }\n    }\n    \n    return make_pair(is_region, sum / (region_size * region_size));\n  }\n  \n  void apply_average(vector<vector<pair<int, int>>> &stats, const int start_r, const int start_c, const int average) {\n    const int end_r = start_r + region_size;\n    const int end_c = start_c + region_size;\n    for (int r = start_r; r < end_r; ++r) {\n      for (int c = start_c; c < end_c; ++c) {\n        stats[r][c].first += average;\n        ++stats[r][c].second;\n      }\n    }\n  }\n};\n```\n**2. Use the presums and the sweep line**\n```\n/**\n * Time Complexity: O(rows * cols)\n * Space Complexity: O(rows * cols)\n * where `rows` is the number of the rows of the grid `image`\n *       `cols` is the number of the columns of the grid `image`\n */\nclass Solution {\n public:\n  vector<vector<int>> resultGrid(const vector<vector<int>> &image, const int threshold) {\n    constexpr int directions[] = {0, 1, 0};\n    constexpr int n_directions = 2;\n    constexpr int end_offsets[] = {0, -1, 0};\n    constexpr int region_size = 3;\n    const int rows = static_cast<int>(image.size());\n    const int cols = static_cast<int>(image.front().size());\n    int presums[rows + 1][cols + 1];\n    memset(presums, 0, sizeof(presums));\n    int validation_presums[n_directions][rows + 1][cols + 1];\n    memset(validation_presums, 0, sizeof(validation_presums));\n    for (int r = 0; r < rows; ++r) {\n      for (int c = 0; c < cols; ++c) {\n        presums[r + 1][c + 1] = presums[r][c + 1] + presums[r + 1][c] + image[r][c] - presums[r][c];\n        for (int d = 0; d < n_directions; ++d) {\n          const int nr = r + directions[d];\n          const int nc = c + directions[d + 1];\n          const int validation = nr < rows && nc < cols && abs(image[r][c] - image[nr][nc]) > threshold ? 1 : 0;\n          validation_presums[d][r + 1][c + 1] = validation_presums[d][r][c + 1] + validation_presums[d][r + 1][c] + validation - validation_presums[d][r][c];\n        }\n      }\n    }\n    \n    int sweep_line_sums[rows + 1][cols + 1];\n    memset(sweep_line_sums, 0, sizeof(sweep_line_sums));\n    int sweep_line_counts[rows + 1][cols + 1];\n    memset(sweep_line_counts, 0, sizeof(sweep_line_counts));\n    for (int start_r = 0; start_r + region_size - 1 < rows; ++start_r) {\n      for (int start_c = 0; start_c + region_size - 1 < cols; ++start_c) {\n        bool valid = true;\n        for (int d = 0; d < n_directions; ++d) {\n          const int end_r = start_r + region_size + end_offsets[d];\n          const int end_c = start_c + region_size + end_offsets[d + 1];\n          if (validation_presums[d][end_r][end_c] - validation_presums[d][start_r][end_c] - validation_presums[d][end_r][start_c] + validation_presums[d][start_r][start_c] != 0) {\n            valid = false;\n            break;\n          }\n        }\n        \n        if (valid) {\n          const int end_r = start_r + region_size;\n          const int end_c = start_c + region_size;\n          const int average = (presums[end_r][end_c] - presums[start_r][end_c] - presums[end_r][start_c] + presums[start_r][start_c]) / (region_size * region_size);\n          sweep_line_sums[start_r][start_c] += average;\n          sweep_line_sums[end_r][start_c] -= average;\n          sweep_line_sums[start_r][end_c] -= average;\n          sweep_line_sums[end_r][end_c] += average;\n          sweep_line_counts[start_r][start_c] += 1;\n          sweep_line_counts[end_r][start_c] -= 1;\n          sweep_line_counts[start_r][end_c] -= 1;\n          sweep_line_counts[end_r][end_c] += 1;\n        }\n      }\n    }\n    \n    int sums[rows + 1][cols + 1];\n    memset(sums, 0, sizeof(sums));\n    int counts[rows + 1][cols + 1];\n    memset(counts, 0, sizeof(counts));\n    vector<vector<int>> ret(rows, vector<int>(cols));\n    for (int r = 0; r < rows; ++r) {\n      for (int c = 0; c < cols; ++c) {\n        sums[r + 1][c + 1] = sums[r][c + 1] + sums[r + 1][c] + sweep_line_sums[r][c] - sums[r][c];\n        counts[r + 1][c + 1] = counts[r][c + 1] + counts[r + 1][c] + sweep_line_counts[r][c] - counts[r][c];\n        ret[r][c] = counts[r + 1][c + 1] == 0 ? image[r][c] : (sums[r + 1][c + 1] / counts[r + 1][c + 1]);\n      }\n    }\n    return ret;\n  }\n};\n```
[]