Horizontal & Vertical Prefix sum
For each cell, calculate count of factors of 2 and 5. Then, prepare a horizontal and vertical prefix sum grid. Now, considering each cell as a turning point, ca
For each cell, calculate count of factors of 2 and 5. Then, prepare a horizontal and vertical prefix sum grid. Now, considering each cell as a turning point, calculate maximum number of trailing zeros from the four paths i.e: left-to-top, left to bottom, top to right, and right to bottom. You got the answer. :)\n```\nclass Solution {\n    pair<int,int> getCount(int num) {\n        int c2=0, c5=0;\n        while(num%2 == 0) {\n            num/=2;\n            c2++;\n        }\n        while(num%5 == 0) {\n            num/=5;\n            c5++;\n        }\n        return make_pair(c2,c5);\n    }\n    \npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        vector<vector<pair<int,int>>> aux; // to maintain count of factors of 2 and 5 for each cell element\n        int m=grid.size(), n=grid[0].size();\n        for(int i=0;i<m;i++) {\n            vector<pair<int,int>> temp;\n            for(int j=0;j<n;j++) {\n                temp.push_back(getCount(grid[i][j]));\n            }\n            aux.push_back(temp);\n        }\n        \n        int ans=0;\n        \n        vector<vector<pair<int,int>>> aux1(m, vector<pair<int,int>>(n, {0,0})), aux2(m, vector<pair<int,int>>(n, {0,0})); // array to maintain vertical and horizontal perfix sum\n        \n        for(int i=0;i<m;i++) {\n            aux1[i][0] = aux[i][0];\n        }\n        \n        for(int j=0;j<n;j++) {\n            aux2[0][j] = aux[0][j];\n        }\n        \n        for(int i=0;i<m;i++) {\n            for(int j=1;j<n;j++) {\n                aux1[i][j].first = aux[i][j].first+aux1[i][j-1].first;\n                aux1[i][j].second = aux[i][j].second+aux1[i][j-1].second;\n                ans=max(ans, min(aux1[i][j].first, aux1[i][j].second));\n            }\n        }\n        \n        for(int j=0;j<n;j++) {\n            for(int i=1;i<m;i++) {\n                aux2[i][j].first = aux[i][j].first+aux2[i-1][j].first;\n                aux2[i][j].second = aux[i][j].second+aux2[i-1][j].second;\n                ans=max(ans, min(aux2[i][j].first, aux2[i][j].second));\n            }\n        }\n        \n        \n        for(int i=0;i<m;i++) {\n            for(int j=0;j<n;j++) {\n                                \n                int tl=0,tr=0,tt=0,tb=0; // t stands for two, l for left, f for five, r for right and so on.\n                int fl=0,fr=0,ft=0,fb=0;\n                \n                if(j-1>=0) {\n                    tl=aux1[i][j-1].first;\n                    fl=aux1[i][j-1].second;\n                }\n                \n                if(i-1>=0) {\n                    tt=aux2[i-1][j].first;\n                    ft=aux2[i-1][j].second;\n                }\n                \n                tr=aux1[i][n-1].first-aux1[i][j].first;\n                fr=aux1[i][n-1].second-aux1[i][j].second;\n                \n                tb=aux2[m-1][j].first-aux2[i][j].first;\n                fb=aux2[m-1][j].second-aux2[i][j].second;\n                \n                // top-to-left\n                ans = max(ans, min(tl+tt+aux[i][j].first, fl+ft+aux[i][j].second));\n                // left-to-bottom\n                ans = max(ans, min(tl+tb+aux[i][j].first, fl+fb+aux[i][j].second));\n                // top-to-right\n                ans = max(ans, min(tt+tr+aux[i][j].first, ft+fr+aux[i][j].second));\n                // right-to-bottom\n                ans = max(ans, min(tr+tb+aux[i][j].first, fr+fb+aux[i][j].second));\n                \n                \n            }\n        }\n        \n       \n        return ans;\n    }\n};\n```
['C']