Pure Python 4200ms faster than 100%
This solution is not DRY but should be easy to understand. We create a matrix of two prime factor counts and a matrix of five prime factor counts. This is becau
This solution is not DRY but should be easy to understand. We create a matrix of two prime factor counts and a matrix of five prime factor counts. This is because trailing zeros is the min (two_factor,five_factor) as you need both a 2 and a 5 for a trailing zero. \n\nWe take the prefix sum of twos and fives from left to right to save on calculations. \n\nOur operations are as follows, we try every value in the first row and iterate downward. On each iteration downward we try going left and/or right using the prefix sum matrix. Then we do the same going upward from the last row. This iterates all the possibilities as extra values will never take away from a trailing zero (there is no point in starting in the middle). \n\n```\nclass Solution:\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n        \n        @lru_cache(None)\n        def sieve_algo(n):\n            ans = []\n            factor = 2\n            for factor in [2,5]:\n                while n%factor == 0:\n                    n = n//factor\n                    ans.append(factor)\n            return ans.count(2),ans.count(5)\n    \n        best_ans = 0\n                    \n        twos = [[0]*len(grid[0]) for _ in range(len(grid))]\n        fives= [[0]*len(grid[0]) for _ in range(len(grid))]\n        \n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                new_two,new_five = sieve_algo(grid[i][j])\n                twos[i][j] = new_two\n                fives[i][j] = new_five\n        \n        left_twos = [list(itertools.accumulate(row)) for row in twos]\n        left_fives = [list(itertools.accumulate(row)) for row in fives]\n        \n        best_ans = 0\n        for j in range(len(grid[0])):\n            curr_twos,curr_fives = 0,0\n            for i in range(len(grid)):\n                curr_twos += twos[i][j]\n                curr_fives += fives[i][j]\n                best_ans = max(best_ans,min(curr_twos,curr_fives))\n                \n                if j < len(grid[0])-1:\n                    left_two_turn = curr_twos + left_twos[i][-1]-left_twos[i][j]\n                    left_five_turn = curr_fives + left_fives[i][-1]-left_fives[i][j]\n                    best_ans = max(best_ans,min(left_two_turn,left_five_turn))\n                \n                if j > 0:\n                    right_two_turn = curr_twos + left_twos[i][j-1]\n                    right_five_turn = curr_fives + left_fives[i][j-1]\n                    best_ans = max(best_ans,min(right_two_turn,right_five_turn))\n                    \n                    \n            curr_twos,curr_fives = 0,0\n            for i in range(len(grid)-1,-1,-1):\n                curr_twos += twos[i][j]\n                curr_fives += fives[i][j]\n                best_ans = max(best_ans,min(curr_twos,curr_fives))\n                \n                if j < len(grid[0])-1:\n                    left_two_turn = curr_twos + left_twos[i][-1]-left_twos[i][j]\n                    left_five_turn = curr_fives + left_fives[i][-1]-left_fives[i][j]\n                    best_ans = max(best_ans,min(left_two_turn,left_five_turn))\n                \n                if j > 0:\n                    right_two_turn = curr_twos + left_twos[i][j-1]\n                    right_five_turn = curr_fives + left_fives[i][j-1]\n                    best_ans = max(best_ans,min(right_two_turn,right_five_turn))\n\n        return best_ans
[]