✔ Lazy Coding 😃 | Idea Explained + Code
Lets try to visulaise our solution , the solution will always be an "L" so what we can do is iterate on every index of the matrix and assume this point to be th
Lets try to visulaise our solution , the solution will always be an **"L"** so what we can do is iterate on every index of the matrix and assume this point to be the intersection of the vertical and horizontal lines.\n\nNow , as we have asssumed (i , j ) to be our answer , we have to find number of trailing zeroes . So for the horizontal and vertical lines , we can have a prefix array that stores number of 2\'s and 5\'s from\n(0 , i ) , (i , n-1) , (0 , j-1) , (j+1 , m) \nNow , we can greedily calculate the answer. It\'s easy just implementing takes some effort. If you dont understand any part please do comment , i will be happy to explain . \n\nPlease do upvote , it motivates me , i will surely add more explanations further \uD83D\uDE03\n \n \n \n grid \n23 | 17 | 15 | 03   | 20 |     \n08   | 01   | 20 | 27 | 11 | \n09   | 04   | 06   | 02   | 21 | \n40 | 09   | 01   | 10 | 06   | \n22 | 07   | 04   | 05   | 03   | \n\n\nPrefix Arrays \n\n prefixhorizontal \n0 0 | 0 0 | 1 0 | 1 0 | 2 2 | \n0 3 | 0 3 | 1 5 | 1 5 | 1 5 | \n0 0 | 0 2 | 0 3 | 0 4 | 0 4 | \n1 3 | 1 3 | 1 3 | 2 4 | 2 5 | \n0 1 | 0 1 | 0 3 | 1 3 | 1 3 | \n\n prefixvertical \n0 0 | 0 0 | 1 0 | 0 0 | 1 2 | \n0 3 | 0 0 | 2 2 | 0 0 | 1 2 | \n0 3 | 0 2 | 2 3 | 0 1 | 1 2 | \n1 6 | 0 2 | 2 3 | 1 2 | 1 3 | \n1 7 | 0 2 | 2 5 | 2 2 | 1 3 | \n\n\n```\nclass Solution {\n    \n        int count(int num , int val)\n        {\n            int cnt = 0 ;\n            while(num>0 && num%val == 0)\n                cnt++ , num/=val ;\n            \n            return cnt ;\n                \n        }\n    \n        int solve(pair<int , int> &p1 , pair<int , int> &p2)\n        {\n            return min(p1.first + p2.first , p1.second + p2.second) ;\n        }\n    \npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        \n        int n = grid.size() , m = grid[0].size() ;\n        vector<vector<pair<int , int>> > preHorizontal(n , vector<pair<int, int>>(m , {0 , 0})) ;\n        vector<vector<pair<int , int>> > preVertical(n , vector<pair<int, int>>(m , {0, 0})) ;\n\n        for(int i=0 ; i<n ; i++)\n        {\n            for(int j=0; j<m ; j++)\n            {\n                if(j == 0) preHorizontal[i][j] = { count(grid[i][j] , 5) , count(grid[i][j] , 2) } ; \n                else{\n                    int cnt5 = preHorizontal[i][j-1].first + count(grid[i][j] , 5) ;\n                    int cnt2 = preHorizontal[i][j-1].second + count(grid[i][j] , 2) ;\n                    preHorizontal[i][j] = { cnt5 , cnt2 } ;\n                }\n            }\n        }\n        \n          for(int i=0 ; i<m ; i++)\n        {\n            for(int j=0; j<n ; j++)\n            {\n                if(j == 0) preVertical[j][i] = { count(grid[j][i] , 5) , count(grid[j][i] , 2) } ; \n                else{\n                    int cnt5 = preVertical[j-1][i].first + count(grid[j][i] , 5) ;\n                    int cnt2 = preVertical[j-1][i].second + count(grid[j][i] , 2) ;\n                    preVertical[j][i] = { cnt5 , cnt2 } ;\n                }\n            }\n        }\n\n        int ans = 0;\n        \n        for(int i=0; i<n ; i++)\n        {\n            for(int j=0; j<m ; j++)\n            {\n                pair<int , int > cnthor1 = {0 , 0} , cnthor2 = {0 , 0} , cntver1 = {0 , 0} , cntver2 = {0 , 0} ;\n                cnthor1 = { preHorizontal[i][m-1].first - preHorizontal[i][j].first , preHorizontal[i][m-1].second - preHorizontal[i][j].second } ;\n                cnthor2 = j > 0 ? preHorizontal[i][j-1] : cnthor2 ;\n                \n        cntver1 =  i>0 ? make_pair(preVertical[n-1][j].first - preVertical[i-1][j].first , preVertical[n-1][j].second - preVertical[i-1][j].second ) : preVertical[n-1][j] ;\n                cntver2 = preVertical[i][j] ;\n                \n                ans = max(ans , solve(cnthor1 , cntver1)) ;\n                ans = max(ans , solve(cnthor2 , cntver1)) ;\n                ans = max(ans , solve(cnthor1 , cntver2)) ;\n                ans = max(ans , solve(cnthor2 , cntver2)) ;\n\n            }\n        }\n\n        return ans;\n\n    }\n};\n
['Dynamic Programming', 'Matrix', 'Prefix Sum']