Brute Force O(n) hashmap solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution:\n    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:\n        \n        def is_region(i: int, j: int):\n            for di in range(3): # right\n                for dj in range(2):\n                    if abs(image[i+di][j+dj] - image[i+di][j+dj+1]) > threshold:\n                        return False\n            for di in range(3): # left\n                for dj in range(1, 3):\n                    if abs(image[i+di][j+dj] - image[i+di][j+dj-1]) > threshold:\n                        return False\n            for di in range(1, 3): # top\n                for dj in range(3):\n                    if abs(image[i+di][j+dj] - image[i+di-1][j+dj]) > threshold:\n                        return False\n            for di in range(2): # down\n                for dj in range(3):\n                    if abs(image[i+di][j+dj] - image[i+di+1][j+dj]) > threshold:\n                        return False\n            return True\n        \n        def grid_in_region(i: int, j: int):\n            for x in range(i, i+3):\n                for y in range(j, j+3):\n                    yield (x, y)\n        \n        m = len(image)\n        n = len(image[0])\n\n        r = 0\n        grid2region = collections.defaultdict(list)\n        averages = []\n        for i in range(m - 2):\n            for j in range(n - 2):\n                if is_region(i, j):\n                    total = 0\n                    for grid in grid_in_region(i, j):\n                        grid2region[grid].append(r)\n                        total += image[grid[0]][grid[1]]\n                    averages.append(total // 9)\n                    r += 1\n        for i in range(m):\n            for j in range(n):\n                if (i, j) in grid2region:\n                    region_list = grid2region[(i, j)]\n                    image[i][j] = sum(averages[i] for i in region_list) // len(region_list)\n        return image\n                    \n                \n                \n                \n```
['Python3']