[Python] Prefix Sum, O(m * n)
Intuition\nStore the prefix sum matrices of rows and columns, where each entry is [a, b] representing the cumulative count of (1) the factors of 2 and (2) the f
**Intuition**\nStore the prefix sum matrices of rows and columns, where each entry is `[a, b]` representing the cumulative count of (1) the factors of 2 and (2) the factors of 5.\n\n\n**Complexity**\nTime: `O(m * n)`\nSpace: `O(m * n)`\n\nBelow is my slightly-modified in-contest solution. Please upvote if you find this solution helpful. Thanks!\n```\nclass Solution:\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n        ans = 0\n        m, n = len(grid), len(grid[0])\n        prefixH = [[[0] * 2 for _ in range(n + 1)] for __ in range(m)]\n        prefixV = [[[0] * 2 for _ in range(n)] for __ in range(m + 1)]\n        for i in range(m):\n            for j in range(n):\n                temp= grid[i][j]\n                while temp % 2 == 0:\n                    prefixH[i][j + 1][0] += 1\n                    prefixV[i + 1][j][0] += 1\n                    temp //= 2\n                while temp % 5 == 0:\n                    prefixH[i][j + 1][1] += 1\n                    prefixV[i + 1][j][1] += 1\n                    temp //= 5\n                for k in range(2):\n                    prefixH[i][j + 1][k] += prefixH[i][j][k]\n                    prefixV[i + 1][j][k] += prefixV[i][j][k]\n        for i in range(m):\n            for j in range(n):\n                left = prefixH[i][j]\n                up = prefixV[i][j]\n                right, down, center = [0] * 2, [0] * 2, [0] * 2\n                for k in range(2):\n                    right[k] = prefixH[i][n][k] - prefixH[i][j + 1][k]\n                    down[k] = prefixV[m][j][k] - prefixV[i + 1][j][k]\n                    center[k] = prefixH[i][j + 1][k] - prefixH[i][j][k]\n                LU, LD, RU, RD = [0] * 2, [0] * 2, [0] * 2, [0] * 2\n                for k in range(2):\n                    LU[k] += left[k] + up[k] + center[k]\n                    LD[k] += left[k] + down[k] + center[k]\n                    RU[k] += right[k] + up[k] + center[k]\n                    RD[k] += right[k] + down[k] + center[k]\n                ans = max(ans,\n                          min(LU[0], LU[1]),\n                          min(LD[0], LD[1]),\n                          min(RU[0], RU[1]),\n                          min(RD[0], RD[1]))\n        return ans\n```
['Prefix Sum', 'Python', 'Python3']