Python organized implementation O(m*n).
I didn\'t get this problem during the contest. I was almost done with this but the clock ended.\n\n# Intuition\n Describe your first thoughts on how to solve th
I didn\'t get this problem during the contest. I was almost done with this but the clock ended.\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor each `image[i][j]` have a corresponding `cntArr[i][j]` storing the number of times that cell is inside of a region, and a `sumArr[i][i]` where it stores the running sum of the average of the thresholds in that region.\n\nGo through each of these arrays, and for whichever ones have a `cntArr[i][j]` value that is greater than 0, set the resulting array `res[i][j]` to the `sumArr[i][j] // cntArr[i][j]`. \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThis is a tedious implementation problem. To solve this one, make sure to tidy up your code and use plenty of helper functions.\n\n# Complexity\n- Time complexity: $$O(m*n)$$ where m is the rows and n is the columns\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m*n)$$ since I created several 2D grids of the same dimension as the input array.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:\n        ROWS, COLS = len(image), len(image[0])\n        res = [[0 for c in range(COLS)] for r in range(ROWS)]\n        \n        sumArr = [[0 for c in range(COLS)] for r in range(ROWS)]\n        cntArr = [[0 for c in range(COLS)] for r in range(ROWS)]\n        \n        def isRegion(r, c):\n            directions = [\n                (0, 1), # right \n                (0, -1), # left\n                (1, 0), # up \n                (-1, 0) # down\n            ]\n            \n            for i in range(r - 2, r + 1):\n                for j in range(c - 2, c + 1):\n                    for dR, dC in directions:\n                        adjR = i + dR \n                        adjC = j + dC\n                        if r - 2 <= adjR <= r and c - 2 <= adjC <= c:\n                            if abs(image[i][j] - image[adjR][adjC]) <= threshold:\n                                continue\n                            else:\n                                return False\n            return True\n        \n        def findAverage(r, c):\n            runningSum = 0\n            for i in range(r - 2, r + 1):\n                for j in range(c - 2, c + 1):\n                    runningSum += image[i][j]\n            return runningSum // 9\n            \n        for r in range(2, ROWS):\n            for c in range(2, COLS):\n                if isRegion(r, c):\n                    avg = findAverage(r, c)\n                    for i in range(r, r - 3, -1):\n                        for j in range(c, c - 3, -1):\n                            sumArr[i][j] += avg\n                            cntArr[i][j] += 1\n        \n        for r in range(ROWS):\n            for c in range(COLS):\n                if cntArr[r][c] > 0:\n                    res[r][c] = sumArr[r][c] // cntArr[r][c]\n                else:\n                    res[r][c] = image[r][c]\n\n        return res\n```
['Python3']