Direct simple solution, Brute force, O(n)
Intuition\nUse brute force.\n\n# Approach\nAt first create an auxiliary 2-d array of lists of integers:\n\nvar aux = InitImageResultAux(image);\n\nThe type of e
# Intuition\nUse brute force.\n\n# Approach\nAt first create an auxiliary 2-d array of lists of integers:\n```\nvar aux = InitImageResultAux(image);\n```\nThe type of each item in this array is `List<int>` and will contain the list of averages for all regions, which contains cell (i, j).\nThen go through the array `image` and fill the array `aux` with averages values:\n```\nfor (int j = 1; j < image[i].Length - 1; j++)\n{\n    if (IsRegion(i, j, image, threshold))\n    {\n        var aver = GetAver(i, j, image);\n        FillAux(aver, i, j, aux);\n    }\n}\n```\nFinally construct the result from the auxiliary array `aux`:\n```\nfor (int i = 0; i < aux.Length; i++)\n{\n    for (int j = 0; j < aux[i].Length; j++)\n    {\n        if (aux[i][j].Count == 0)\n        {\n            rs[i][j] = image[i][j];\n        }\n        else\n        {\n            var sum = aux[i][j].Sum();\n            rs[i][j] = sum / aux[i][j].Count;\n        }\n    }\n}\n```\n\n# Complexity\n- Time complexity:\n$$O(n)$$, where n is image.Length * image[i].Length\n\n- Space complexity:\n$$O(n)$$, where n is image.Length * image[i].Length\n\n# Code\n```\npublic class Solution {\n    public int[][] ResultGrid(int[][] image, int threshold) {\n        var aux = InitImageResultAux(image);\n        for (int i = 1; i < image.Length - 1; i++)\n        {\n            for (int j = 1; j < image[i].Length - 1; j++)\n            {\n                if (IsRegion(i, j, image, threshold))\n                {\n                    var aver = GetAver(i, j, image);\n                    FillAux(aver, i, j, aux);\n                }\n            }\n        }\n        var rs = InitImageResult(image);\n        for (int i = 0; i < aux.Length; i++)\n        {\n            for (int j = 0; j < aux[i].Length; j++)\n            {\n                if (aux[i][j].Count == 0)\n                {\n                    rs[i][j] = image[i][j];\n                }\n                else\n                {\n                    var sum = aux[i][j].Sum();\n                    rs[i][j] = sum / aux[i][j].Count;\n                }\n            }\n        }\n        return rs;\n    }\n    private void FillAux(int aver, int row, int col, List<int>[][] aux)\n    {\n        for (int i = row - 1; i <= row + 1; i++)\n        {\n            for (int j = col - 1; j <= col + 1; j++)\n            {\n                aux[i][j].Add(aver);\n            }\n        }\n    }\n    private int GetAver(int row, int col, int[][] image)\n    {\n        var rs = 0;\n        var sum = 0;\n        for (int i = row - 1; i <= row + 1; i++)\n        {\n            for (int j = col - 1; j <= col + 1; j++)\n            {\n                sum += image[i][j];\n            }\n        }\n        rs = sum / 9;\n        return rs;\n    }\n    private bool IsRegion(int row, int col, int[][] image, int threshold)\n    {\n        for (int i = row - 1; i <= row + 1; i++)\n        {\n            for (int j = col - 1; j <= col + 1; j++)\n            {\n                if (i != row + 1)\n                {\n                    if (Math.Abs(image[i][j] - image[i + 1][j]) > threshold) return false;\n                }\n                if (j != col + 1)\n                {\n                    if (Math.Abs(image[i][j] - image[i][j + 1]) > threshold) return false;\n                }\n            }\n        }\n        return true;\n    }\n    private List<int>[][] InitImageResultAux(int[][] image)\n    {\n        var rs = new List<int>[image.Length][];\n        for (int i = 0; i < rs.Length; i++)\n        {\n            rs[i] = new List<int>[image[i].Length];\n            for (int j = 0; j < rs[i].Length; j++)\n            {\n                rs[i][j] = new List<int>();\n            }\n        }\n        return rs;\n    }\n    private int[][] InitImageResult(int[][] image)\n    {\n        var rs = new int[image.Length][];\n        for (int i = 0; i < rs.Length; i++)\n        {\n            rs[i] = new int[image[i].Length];\n        }\n        return rs;\n    }\n}\n```
['C#']