Brute force, step by step for beginners
Approach\nstep 1: store average of every region into list (-1 otherwise)\nstep 2: if a cell lies in multiple regions store sum of average of regions\nstep 3: al
# Approach\nstep 1: store average of every region into list (-1 otherwise)\nstep 2: if a cell lies in multiple regions store sum of average of regions\nstep 3: also store number of regions in which a cell lies\nstep 4: divide step 2 values by step 3 values\nNote: Kindly suggest code optimizations.\n# Complexity\n- Time complexity:\nO(m*n)\n\n- Space complexity:\n O(m*n)\n\n# Code\n```\nclass Solution {\n    public int[][] resultGrid(int[][] image, int threshold) {\n        int m = image.length;\n        int n = image[0].length;\n        List<Integer> averageList = new ArrayList<>(); // to store average of every region else -1\n        for(int i = 0; i<=m-3; i++){\n            for(int j = 0; j<=n-3; j++){\n                averageList.add(isRegion(i, j, m, n, threshold, image));\n            }\n        }\n       \n        //here we fill the cells with the sum of the average values of the region\n        //and also count in how many regions a cell lies and store it in isUpdated\n        int[][] isUpdated = new int[m][n];\n        int idx = 0;\n        for(int i = 0; i<=m-3; i++){\n            for(int j = 0; j<=n-3; j++){\n                if(averageList.get(idx) != -1) update(i, j, image, isUpdated, averageList.get(idx));\n                idx++;\n            }\n        }\n\n        //to find average value of cell\n        for(int i = 0; i<m; i++){\n            for(int j = 0; j<n; j++){\n                if(isUpdated[i][j] != 0) image[i][j] /= isUpdated[i][j];\n            }\n        }\n\n        return image;\n    }\n\n    //this function stores in how many regions a value lies\n    //stores the number of regions into isUpdated matrix\n    //time complexity -> O(1)\n    private void update(int i, int j, int[][] image, int[][] isUpdated, int avg){\n\n         for(int row = i; row < i+3; row++){\n            for(int col = j; col <j+3; col++){\n\n               \n                if(isUpdated[row][col] == 0){ //if its first region for cell\n                    image[row][col] = avg;\n                }else{ // if its second or greater region for cell\n                    image[row][col] += avg;\n                }\n                isUpdated[row][col]++; \n\n            }\n        }\n    }\n\n    //function to check if 3*3 area is a region or not\n    //if its a region, function returns average of the region\n    //else returns -1\n    //time complexity -> O(1)\n    private int isRegion(int i, int j, int m, int n, int k, int[][] image){\n        int sum = 0;\n        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};\n        for(int row = i; row < i+3; row++){\n            for(int col = j; col <j+3; col++){\n                for(int[]dir : dirs){\n                    int x = row+dir[0];\n                    int y = col+dir[1];\n                    if(x>=i && y>=j && x<i+3 && y <j+3){\n                    \n                        if(Math.abs(image[row][col]-image[x][y]) > k) return -1;\n                    }\n                }\n                sum += image[row][col];\n            }\n        }\n        return sum/9;\n    }\n}\n```
['Java']