[Java] O(mn) solution, use prefix sum to calculate number of factors (2 and 5) with explanation
The idea: for each cornered path, let\'s call its product is p. We can always rewrite p  as follows\np = a * 10^n\n\nNumber of trailing zeros will be maximum va
**The idea**: for each cornered path, let\'s call its product is `p`. We can always rewrite `p`  as follows\n`p = a * 10^n`\n\nNumber of trailing zeros will be maximum value of n in all ways to rewrite `p`. We have\n\n`number of trailing zeros of p = max(n) = min(number of 2 in prime factorization of p, number of 5 in prime factorization of p)`\n\n**Greedy strategy**: we will just consider the paths that start with a point on border of grid (first row or last row or first col or last col) and end with a point on border of grid because these paths will always have number of trailing zeros greater than (or equal) its sub paths.\n\nBelow is the implementation for this problem in Java. \n\n```\nclass Solution {\n    public int maxTrailingZeros(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n        int[][][] count25 = new int[m][n][2];\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                // number of 2 in prime factorization of grid[i][j]\n                count25[i][j][0] = countFactor(grid[i][j], 2);\n                // number of 5 in prime factorization of grid[i][j]\n                count25[i][j][1] = countFactor(grid[i][j], 5);\n            }\n        }\n        \n        // countUp[i][j][0]: number of 2 in prime factorization of numbers from grid[0][j] to grid[i][j]\n        // countUp[i][j][1]: number of 5 in prime factorization of numbers from grid[0][j] to grid[i][j]\n        // the same definition for countDown, countLeft and countRight\n        // we will use prefix sum to caculate them\n        int[][][] countUp = new int[m][n][2];\n        int[][][] countDown = new int[m][n][2];\n        int[][][] countLeft = new int[m][n][2];\n        int[][][] countRight = new int[m][n][2];\n        \n        for (int i = 0; i < m; ++i) {\n            countLeft[i][0][0] = count25[i][0][0];\n            countLeft[i][0][1] = count25[i][0][1];\n            countRight[i][n-1][0] = count25[i][n-1][0];\n            countRight[i][n-1][1] = count25[i][n-1][1];\n        }\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 1; j < n; ++j) {\n                countLeft[i][j][0] = countLeft[i][j-1][0] + count25[i][j][0];\n                countLeft[i][j][1] = countLeft[i][j-1][1] + count25[i][j][1];\n            }\n        }\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = n - 2; j >= 0; --j) {\n                countRight[i][j][0] = countRight[i][j+1][0] + count25[i][j][0];\n                countRight[i][j][1] = countRight[i][j+1][1] + count25[i][j][1];\n            }\n        }\n        \n        for (int j = 0; j < n; ++j) {\n            countUp[0][j][0] = count25[0][j][0];\n            countUp[0][j][1] = count25[0][j][1];\n            countDown[m-1][j][0] = count25[m-1][j][0];\n            countDown[m-1][j][1] = count25[m-1][j][1];\n        }\n        \n        for (int j = 0; j < n; ++j) {\n            for (int i = 1; i < m; ++i) {\n                countUp[i][j][0] = countUp[i-1][j][0] + count25[i][j][0];\n                countUp[i][j][1] = countUp[i-1][j][1] + count25[i][j][1];\n            }\n        }\n        \n        for (int j = 0; j < n; ++j) {\n            for (int i = m-2; i >= 0; --i) {\n                countDown[i][j][0] = countDown[i+1][j][0] + count25[i][j][0];\n                countDown[i][j][1] = countDown[i+1][j][1] + count25[i][j][1];                \n            }\n        }\n        \n        int result = 0;\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                result = Math.max(result, \n                                  Math.min(countUp[i][j][0] + countRight[i][j][0] - count25[i][j][0], countUp[i][j][1] + countRight[i][j][1] - count25[i][j][1])\n                                 );\n                result = Math.max(result, \n                                  Math.min(countUp[i][j][0] + countLeft[i][j][0] - count25[i][j][0], countUp[i][j][1] + countLeft[i][j][1] - count25[i][j][1])\n                                 );\n                result = Math.max(result, \n                                  Math.min(countDown[i][j][0] + countRight[i][j][0] - count25[i][j][0], countDown[i][j][1] + countRight[i][j][1] - count25[i][j][1])\n                                 );\n                result = Math.max(result, \n                                  Math.min(countDown[i][j][0] + countLeft[i][j][0] - count25[i][j][0], countDown[i][j][1] + countLeft[i][j][1] - count25[i][j][1])\n                                 );\n            }\n        }\n        \n        return result;\n    }\n\n    \n    \n    private int countFactor(int a, int factor) {\n        int result = 0;\n        while (a % factor == 0) {\n            a /= factor;\n            result++;\n        }\n        return result;\n    }\n    \n}\n```\nTime complexity: O(mn).\nSpace complexity: O(mn).\n\nPlease upvote if it is helpful to you. If there is any questions/suggestion, please comment, I will reply as soon as possible.
[]