Easy to Understand ||  Line by Line Explained || Pure Implementation || C++
Intuition\n1) Calculate prefix sum to fetch the sum of any submatrix in O(1) time..\n2) Calculate all those submatrix which are not a region\n    (i.e :- it con
# Intuition\n1) Calculate prefix sum to fetch the sum of any submatrix in O(1) time..\n2) Calculate all those submatrix which are not a region\n    (i.e :- it contains adjacent pixels with value greater than threshhold).. \n3) Each point (Pixel) can lie minium 1 and maximum 9 (3*3)submatrix \n-- suppose point (pixel) (x,y) lie in k (3 * 3) submatrix..\n     where 1<=k<=9\n4) now check for every point (Pixel) out k how many submatrix is a region and take average of all region add it and divide it by k..\n\n# Approach\n-- Approach is described in details line by line in code section with comment..\n\n# Complexity\n- Time complexity:\nO(9* N * M)\n\n- Space complexity:\nO(N*M)\n\n# Code\n```\n\nusing ll=long long;\n   int row, col;\n    vector<vector<int>> sums;\n// This function calculating sum of submatrix from (0,0)->(i,j) or u can say it calculating the sum of rectagle((0,0),(i,j)) and storing at sum[i+1][j+1].\n    void solve1(vector<vector<int>> &matrix) {\n        row = matrix.size();\n        col = row>0 ? matrix[0].size() : 0;\n        sums = vector<vector<int>>(row+1, vector<int>(col+1, 0));\n        for(int i=1; i<=row; i++) {\n            for(int j=1; j<=col; j++) {\n                sums[i][j] = matrix[i-1][j-1] + \n                             sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] ;\n            }\n        }\n    }\n// This function will give the sum of submaxtrix or rectangle formed by coordinate (row1,col1) and (row2,col2).\n    int solve2(int row1, int col1, int row2, int col2) \n    {\n        return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];\n    }\n\n\nclass Solution {\npublic:\n    vector<vector<int>> resultGrid(vector<vector<int>>& a, int tar) {\n        row=a.size();\n        col=a[0].size();\n        solve1(a);\n        ll n=row;\n        ll m=col;\n      vector<vector<ll>>  b(row,vector<ll>(col,-1));\n// here i am calculating sum of all possible 3*3 submatrix and storing in b[i][j]..\n  // where b[i][j] denotes the sum of 3*3 submatrix or rectangle whose starting coordinates are (i,j) andending coordinates (i+2,j+2)..\n         for(int i=0;i<row-2;i++)\n        {\n           for(int j=0;j<col-2;j++)\n            {\n                b[i][j]=solve2(i,j,i+2,j+2);\n            }\n        }\n// total no of 3*3 submatrix poosible= (n-2)*(m-2)..\n// here des vector of size((n-2)*(m-3)) will be  storing boolean value where 0 detones -->not a region and 1 denotes--> a region..\n// where des[i,j] is denoting the submatrix or rectangle whose starting coordiantes (i,j) and ending coordinates (i+2,j+2) is a region or not..\n        \n// now lets see how decision is taken that a particular submatrix is region or not..\n       vector<vector<ll>>des(row-2,vector<ll>(col-2,1));\n         vector<vector<int>>ans(row,vector<int>(col));\n         for(int i=0;i<row;i++)\n        {\n             // here i am moving from left to right\n           for(int j=0;j<col;j++)\n            {\n            // here i am moving from up to down\n      // every point(i,j) in 2-D matrix can have 2 to 4 neighbours..\n      // since we are moving from left to right and up to down so, we have take care of only two neighbours(down ,right) that is down(i+1,j) & right(i,j+1)..\n                \n                // here i am checking the right neighbour (i,j+1)\n                // if abs((i,j)-(i,j+1)>threshhold) means if abs diff b/w its curr points(pixel) and its right neighbour(pixel) is greater than threshold then all those submatrix  that contains both these points(Pixels) will not be region..\n                if(j+1<m && abs(a[i][j]-a[i][j+1])>tar)\n                {\n                    // now i am checking the points ((i,j) & (i,j+1)) together can lie in how many submatrix \n                    // these point can lie into min=1 and max=6 submatrixes...\n  /*                  1 2 3 4 5 \n                   1 | | | | | |   lets consider a scenario of(5*5) matrix now i am at point p(3,3) denoted by (*) and its right             \n                   2 | | | | | |   neighbour denoted by (#) at q(3,4)..\n                   3 | | |*|#| |   now i can make 6 submatrix containing point (p,q)  \n                   4 | | | | | |   now i will writing starting coordinates of 6 (3*3)submatrix..\n                   5 | | | | | |   1)->(1,3)\n                                   2)->(2,3)\n                                   3)->(3,3)\n                                   4)->(1,2)\n                                   5)->(2,2)\n                                   6)->(3,2)\n                          it is clear from here that a point p and q affect these 6 (3*3) submatrix..   */\n                          for(int i1=max(0,i-2);i1<=i;i1++)\n                        {\n                            for(int j1=max(0,j-1);j1<=j;j1++)\n                           {\n                                // here (i1,j1) denotes submatrix containing  (i,j) & (i,j+1) points\n                                // here if condition is checking that coordinates with starting point(i1,j1) can make a substring of(3*3) or not..\n                                if(i1+2<row && j1+2<col)\n                                {\n    // here we come to conclusion that submatrix with starting coordinates(i1,j1) and ending cordinates(i1+2,j1+2) contains points (i,j)&(i,j+1) whose abs diff is greater than threshhold so particular submatrix can\'t be a region. so do bitwise and(&) with 0 to make it not a region.. \n                                   des[i1][j1]=des[i1][j1]&0; \n                                }\n                           }\n                        }\n                   \n                }\n                \n                // similarly here i am checking the Down neighbour(Pixel) (i+1,j)\n                if(i+1<n && abs(a[i][j]-a[i+1][j])>tar)\n                {\n                     for(int i1=max(0,i-1);i1<=i;i1++)\n                        {\n                            for(int j1=max(0,j-2);j1<=j;j1++)\n                           {\n                                if(i1+2<row && j1+2<col)\n                                {\n                                   des[i1][j1]=des[i1][j1]&0; \n                                }\n                           }\n                        }\n                   \n                }\n            }    \n        }\n    /*     Note --> every point can lie in minimum one(1)-> (3*3)submatrix and maximum nine(9)-> (3*3)submatrix..\n                      1 2 3 4 5 \n                   1 | | | | | |   lets consider a scenario of(5*5) matrix now i am at point p(3,3) denoted by (*) and its right             \n                   2 | | | | | | \n                   3 | | |*| | |   now i can make 9 submatrix containing (p,q)  \n                   4 | | | | | |   now i will writing starting coordinates of 9 (3*3)submatrix..\n                   5 | | | | | |   \n                                   1)-> (1,1)      4)->(1,2)    5)->(1,3)\n                                   2)-> (2,1)      5)->(2,2)    6)->(2,3)\n                                   3)-> (3,1)      6)->(3,2)    7)->(3,3)\n               basically every point lie in submatrix with starting coordinates (i1,j1) where i1 and j1 are given below :-\n                                          (i1>=(i-2) && i1<=i)  , (j1>=(j-2)  && j1<=j)      \n                                          */\n          for(int i=0;i<row;i++)\n         {\n           for(int j=0;j<col;j++)\n            {\n                ll ans1=0,c=0;\n                \n     //           here we are checking all possible 1 to 9 submatrix which are a region and containg point (i,j)...\n                // c is keeping track of out of all possible submatrix containing point (i,j) is a region\n                         for(int i1=max(0,i-2);i1<=i;i1++)\n                        {\n                            for(int j1=max(0,j-2);j1<=j;j1++)\n                           {\n                                // here we  are checking a submatrix with starting coordinates (i1,j1) are region or not..\n                                   if(b[i1][j1]!=-1 && des[i1][j1]==1) \n                                   {\n                                       c++;\n                                       // we are taking avearage of submatrix(i1,j1)...\n                                       ans1+=(b[i1][j1]/9);\n                            \n                                   }\n                                \n                           }\n                         }\n                if(c==0)\n                {\n                    ans[i][j]=a[i][j];\n                }\n                else\n                {\n                ans[i][j]=ans1/c;\n                }\n            }\n             \n        }\n\n        \n        return ans;\n    }\n};\n\n
['Prefix Sum', 'C++']