Java Solution - with presum
Intuition\n Describe your first thoughts on how to solve this problem. \nDo what it said\n-- use presum to calculate the sum of a region\n-- when we have a regi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDo what it said\n-- use presum to calculate the sum of a region\n-- when we have a region with n*n, this will have better performance than calculating the sum of a region directly\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nbrute force with presum\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\n    int m;\n    int n;\n    int[][] count;\n    int[][] res;\n    public int[][] resultGrid(int[][] image, int threshold) {\n        m = image.length;\n        n = image[0].length;\n        int[][] presum = new int[m+1][n+1];\n        count = new int[m][n];\n        res = new int[m][n];\n        //calculate presum\n        for(int i=1;i<=m;i++) {\n            for(int j=1;j<=n;j++) {\n                presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1] + image[i-1][j-1];\n            }\n        }\n        //check & update teh region\n        for(int i=2;i<m;i++) {\n            for(int j=2;j<n;j++) {\n                checkRegion(image, threshold, presum, i, j);\n            }\n        }\n        //calculate result\n        for(int i=0;i<m;i++) {\n            for(int j=0;j<n;j++) {\n                //System.out.println("count[" + i + "][" + j + "] = " + count[i][j] + " sum = " + res[i][j]);\n                if(count[i][j]==0) res[i][j] = image[i][j];\n                else res[i][j] = res[i][j] / count[i][j];\n            }\n        }\n        return res;\n    }\n\n    //check if region is valid, if yes, update the count & sum\n    private void checkRegion(int[][] image, int threshold, int[][] presum, int x, int y) {\n        for(int i=0;i<=2;i++) {\n            for(int j=0;j<=2;j++) {\n                if(!checkValid(image, threshold, x-i, y-j, x-2, y-2, x, y)) return; \n            }\n        }\n        int sum = presum[x+1][y+1] - presum[x-2][y+1] - presum[x+1][y-2] + presum[x-2][y-2];\n        for(int i=0;i<=2;i++) {\n            for(int j=0;j<=2;j++) {\n                count[x-i][y-j]++;\n                res[x-i][y-j]+= sum/9;\n            }\n        }\n    }\n\n    //check if current grid is valid\n    private boolean checkValid(int[][] image, int threshold, int i, int j, int x1, int y1, int x2, int y2) {\n        int curr = image[i][j];\n        int up = i - 1 >=0 && i-1>=x1? image[i-1][j] : curr; \n        int down = i + 1 <m && i+1<=x2? image[i+1][j] : curr; \n        int left = j - 1 >=0 && j-1>=y1? image[i][j-1] : curr; \n        int right = j + 1<n && j+1<=y2 ? image[i][j+1] : curr;\n        return (Math.abs(curr-up)<=threshold && Math.abs(curr-down)<=threshold \n            && Math.abs(curr-left)<=threshold && Math.abs(curr-right)<=threshold); \n    }\n}\n```
['Java']