Java ☕ | Brute Force with BFS Validation
Intuition and Approach\ncheck all possible 3x3 rectangles\ncheck if a rectangle is valid (With BFS)\nif it is valid update the sum and element count for the cur
# Intuition and Approach\ncheck all possible 3x3 rectangles\ncheck if a rectangle is valid (With BFS)\nif it is valid update the sum and element count for the current cell (stored in array map)\ncalculate final result (if cell count is zero set with original value, else perform average)\n\n\n# Complexity\n- Time complexity:\nI think:\nO(rowxcolx2constant) where "constant" is the cost of checking if the rectangle is valid;\n\n- Space complexity:\nI think:\nO(rxc)\n\n# Comments\n- I couldn\'t come up with a simpler way of validating the rectangle\n- Lost a lot of time optimizing the solution to pass, namely in the bfs part. Having a visited array of n*m size resulted in TLE\n\n# Code\n```\nclass Solution {\n        public int[][] resultGrid(int[][] img, int threshold) {\n            int id = 0;\n            int n = img.length;\n            int m = img[0].length;\n            int[][] map = new int[n*m][2];\n            for (int r = 0; r < img.length-2; r++){\n                for(int c = 0; c <img[0].length-2; c++){\n                    //check region\n                    int regionResult = isValid(r,c,img,threshold);\n                    //if valid region increase count and sum in array map\n                    if (regionResult != -1){\n                        for(int i = r; i < r+3; i++){\n                            for(int j = c; j < c+3; j++){\n                                id = code(i,j,m);\n                                map[id][0] += regionResult;\n                                map[id][1] ++;\n                            }\n                        }\n                    }\n                }\n            }\n\n            int [][] result = new int [n][m];\n            for (int i = 0; i < n; i++){\n                for(int j = 0; j < m; j++){\n                    //if cell has count zero use original value\n                    id = code(i,j,m);\n                    if (map[id][1] == 0){\n                        result [i][j] = img[i][j];\n                    }\n                    //else calculate average\n                    else{\n                        result[i][j] = map[id][0]/map[id][1];\n                    }\n                }\n            }\n            return result;\n        }\n\n        //Calculate valid rectangle with BFS\n        public int isValid(int r, int c, int[][] img, int threshold){\n            int m = img[0].length;\n            int n = img.length;\n            Queue<Point> q = new ArrayDeque<>();\n            q.add(new Point(img[r][c],r, c, 0));\n            //img[i][j] maps to visited[discoveryId]; 0 <= discoveryId < 9\n            boolean [] visited = new boolean[9];\n            Point cur;\n            int sum = 0;\n            while (!q.isEmpty()){\n                cur = q.poll();\n                sum += cur.val;\n                //check down\n                if (cur.r+1 < img.length && cur.r+1 - r < 3){\n                    if (Math.abs(cur.val - img[cur.r+1][cur.c]) > threshold){\n                        sum = -1;\n                        break;\n                    }\n\n                    if( !visited[cur.id+3] ){\n                        q.add(new Point(img[cur.r+1][cur.c], cur.r+1, cur.c,cur.id+3));\n                        visited[cur.id+3] = true;\n                    }\n                }\n                //check right\n                if (cur.c+1 < img[0].length && cur.c+1 - c < 3){\n                    if (Math.abs(cur.val - img[cur.r][cur.c+1]) > threshold){\n                        sum = -1;\n                        break;\n                    }\n                    if(!visited[cur.id+1] ){\n                        q.add(new Point(img[cur.r][cur.c+1], cur.r, cur.c+1, cur.id+1));\n                        visited[cur.id+1] = true;\n                    }\n                }\n            }\n            return sum == -1 ? sum : sum / 9;\n        }\n        public int code(int r, int c, int cLen){\n            return r * cLen + c;\n        }\n    }\n    public class Point{\n        //cell value\n        int val;\n        //cell row\n        int r;\n        //cell column\n        int c;\n        //cell virtual id\n        //I use this to map "image" array of size n*m to visited of size 9\n        int id;\n\n        public Point(int v, int ro, int co, int i){\n            val = v;\n            r = ro;\n            c = co;\n            id = i;\n        }\n    }\n```
['Array', 'Breadth-First Search', 'Matrix', 'Java']