C++ | Easy Solution | TC: O(N * M) | SC: O(N * M) ⚡⚡
Intuition\nSay the mid point of sub matrix of size 3x3 is at (i, j)\nthen we can only form the sub matrix at (i, j), when both i and j are not on boundary\n\nwe
# Intuition\nSay the mid point of sub matrix of size 3x3 is at (i, j)\nthen we can only form the sub matrix at (i, j), when both i and j are not on boundary\n\nwe calculate the average of that sub matrix\nand check if any two adjacent element are differ greater than the threshold value or not\n\nif the value is greater then threshold, \nit means we cannot make the all the values of sub matrix whose mid point is at (i, j)\n\nwe calculate it for all the valid mid points (i, j) of sub matrices\nwe store all the avg values for all co ordinates (x, y)\n\nand in the result matrix, for each cell we take the avg of all the values which were part of valid submatrix\n\n\n# Complexity\n- Time complexity: O(N * M * 9 * 9) + 2 * O(N * M) => O(N * M)\n \n- Space complexity: O(N * M)\n\n# Code\n```\nclass Solution {\nprivate:\n    int dx[9] = {-1, -1, -1, 0, 0, 0, +1, +1, +1};\n    int dy[9] = {-1, 0, +1, -1, 0, +1, -1, 0, +1};\npublic:\n    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {\n        int n = image.size(), m = image[0].size();\n        \n        map<pair<int, int>, vector<int>> mpp;\n        for(int i = 1; i < n - 1; i++){\n            for(int j = 1; j < m - 1; j++){\n\n                int avg = 0, flag = 1;\n                for(int k = 0; k < 9; k++){\n                    int x = i + dx[k], y = j + dy[k];\n                    int val = image[x][y];\n\n                    if((y+1 < m) && (y < (j + 1))){\n                        int diff = abs(image[x][y] - image[x][y+1]);\n                        if(diff > threshold)    flag = false;\n                    }\n                    if((x+1 < n) && (x < (i + 1))){\n                        int diff = abs(image[x][y] - image[x+1][y]);\n                        if(diff > threshold)    flag = false;\n                    }\n\n                    avg += image[x][y];\n                }\n                if(!flag)   continue;\n\n                avg /= 9;\n                for(int k = 0; k < 9; k++){\n                    int x = i + dx[k], y = j + dy[k];\n                    mpp[{x, y}].push_back(avg);\n                }\n            }\n        }\n\n        vector<vector<int>> dist(n, vector<int> (m, -1));\n        for(auto it: mpp){\n            int i = it.first.first, j = it.first.second;\n            vector<int> vec = it.second;\n            \n            int sum = accumulate(vec.begin(), vec.end(), 0);\n            int size = vec.size();\n            \n            dist[i][j] = (sum / size);\n        }\n        \n        \n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < m; j++){\n                if(dist[i][j] == -1) {   \n                    dist[i][j] = image[i][j];\n                }\n            }\n        }\n        \n        return dist;\n    }\n};\n\n```
['Ordered Map', 'Matrix', 'C++']