Reuse matrix grid Extra space O(1) MaxPooling vs Sliding window||3ms Beats 99.54%
Intuition\n Describe your first thoughts on how to solve this problem. \nThat is the max computation for 3x3 submatrix.\nmax pool with 3x3 window & stride 1 wit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThat is the max computation for 3x3 submatrix.\nmax pool with 3x3 window & stride 1 without padding\n\n2nd approach using the sliding window to reduce the amount of computations with 3ms Beating 99.54%\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/kiG_jJmFtzU?si=hmldrhvI7XTs0Qif](https://youtu.be/kiG_jJmFtzU?si=hmldrhvI7XTs0Qif)\nReuse the 2d vector grid\n![2373_maxPool.png](https://assets.leetcode.com/users/images/780d009a-60b6-4b9f-a382-e4f27c378814_1715485097.594414.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(9n^2)\\to O(6n^2)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nextra: $O(1)$\n# C++ Code\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {\n        const int n=grid.size();\n        for(int i=1; i<n-1; i++){           \n            for(int j=1; j<n-1; j++){\n                for(int r=i-1; r<=i+1; r++)\n                    for( int c=j-1; c<=j+1; c++)\n                        grid[i-1][j-1]=max(grid[i-1][j-1], grid[r][c]);\n            }\n            grid[i-1].resize(n-2);\n        }\n        grid.resize(n-2);\n        return grid;\n    }\n};\n\n```\n# Python code\n```\nclass Solution:\n    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n        # max pool with 3x3 window & stride 1 without padding\n        n=len(grid)\n        ans=[[0]*(n-2) for _ in range(n-2)]\n        for i in range(1, n-1):\n            for j in range(1, n-1):\n                ans[i-1][j-1]=0\n                for r in range(i-1, i+2):\n                    for c in range (j-1, j+2):\n                        ans[i-1][j-1]=max(ans[i-1][j-1], grid[r][c])\n        return ans\n        \n```\n#  2nd C++ using sliding window reducing  computations||3ms Beats 99.54%\nUse a sized 3 extra array `maxC` to compute the max for 3x1 submatrices. In each row, moving `j` & compute the next `maxC[(j+1)%3]`, i.e. sliding window,  computational amount is reduced.\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    static vector<vector<int>> largestLocal(vector<vector<int>>& grid) {\n        const int n=grid.size();\n        int maxC[3]={0};\n        for(int i=1; i<n-1; i++){   \n            for(int j=1; j<n-1; j++){\n                if (j==1){\n                    maxC[0]=max({grid[i-1][0], grid[i][0], grid[i+1][0]});\n                    maxC[1]=max({grid[i-1][1], grid[i][1], grid[i+1][1]});\n                }\n                maxC[(j+1)%3]=max({grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]});      \n                grid[i-1][j-1]=max({maxC[0], maxC[1], maxC[2]});\n            }\n            grid[i-1].resize(n-2);\n        }\n        grid.resize(n-2);\n        return grid;\n    }\n};\n\n\n```
['Sliding Window', 'Matrix', 'C++', 'Python3']