✅Detailed Explanation🔥🔥Extremely Simple and effective🔥O(n^2) Time and O(n) Space🔥🔥🔥
\uD83C\uDFAFProblem Explanation:\nGiven an n by n matrix, the task is to find the maximum for each 3 by 3 square in this matrix.\n\n# \uD83D\uDCE5Input:\n- grid
# \uD83C\uDFAFProblem Explanation:\nGiven an n by n matrix, the task is to find the maximum for each 3 by 3 square in this matrix.\n\n# \uD83D\uDCE5Input:\n- grid: integer matrix n by n\n\n# \uD83D\uDCE4Output:\nMatrix n - 2 by n - 2 which contain maximums for each square 3 by 3\n\n# \uD83E\uDD14 Intuition\n- Okay, firstly just put up with the fact that this stupid question just doesn\'t have effective approach and brute force just ok\n- I have no idea about what to write here, because all intuition is just **"traverse matrix"**\n\n# \uD83E\uDDE0 Approach\n- Okay, as was said, this problem has nothing but a brute force solution. That is, we will go through each cell, which is potentially the center of some three by three square and will look for the maximum among it and all its neighbors, for this we will write an auxiliary function ```get_maximum```.\n- Further, as stated in the description itself, the centers of the square we need are located from 1 to n - 1 index (not inclusive), that is, the last index that we will see is n - 2, that is, the penultimate index in the matrix.\n- I tried to optimize space complexity, so I tried to reuse the original matrix, but no matter how we get out, we need to reduce its size by 2 - since in Python this can be done mainly by slices, that\u2019s what I did. However, in fact, at the end, we still create a new matrix, so the space complexity should not change and remain O(n^2)\n\n# \uD83D\uDCD2 Complexity\n- \u23F0 Time complexity: O(n^2), we traverse through every of n^2 elements one time, checking also 8 elements around on every step but it\'s still O(n^2) \n- \uD83E\uDDFA Space complexity: O(n^2), we "recreate" the matrix to fit our sizes, but I believe that in some languages this can be done in O(1)\n\n# \uD83E\uDDD1\u200D\uD83D\uDCBB Code\n```\nclass Solution:\n    def largestLocal(self, grid: list[list[int]]) -> list[list[int]]:\n        n: int = len(grid)\n\n        def get_maximum(row_i, col_i) -> int:\n            res = 0\n            for row in range(row_i - 1, row_i + 2, 1):\n                for col in range(col_i - 1, col_i + 2, 1):\n                    if grid[row][col] > res:\n                        res = grid[row][col]\n            return res\n\n        for row_ind in range(1, n - 1):\n            for col_ind in range(1, n - 1):\n                grid[row_ind - 1][col_ind - 1] = get_maximum(row_ind, col_ind)\n\n        grid = [\n            row_ind[: n - 2] for row_ind in grid[: n - 2]\n        ]  # every time we put maximum one to the left and upper, so our result will be from 0 to n - 2 indexes\n\n        return grid\n```\n\n## \uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning! \uD83D\uDCDA\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/5fbeecf2-18f6-4dce-a4a0-f11c859e46ad_1714711173.2665718.png)\n
['Array', 'Sliding Window', 'Matrix', 'Simulation', 'Python', 'Python3']