C# - O(N * M) using prefix sums along horizontal and vertical paths
csharp\npublic int MaxTrailingZeros(int[][] grid)\n{\n\t(int twos, int fives)[,] horizontal = new (int, int)[grid.Length, grid[0].Length];\n\t(int twos, int fiv
```csharp\npublic int MaxTrailingZeros(int[][] grid)\n{\n\t(int twos, int fives)[,] horizontal = new (int, int)[grid.Length, grid[0].Length];\n\t(int twos, int fives)[,] vertical = new (int, int)[grid.Length, grid[0].Length];\n\n\tint rows = grid.Length, columns = grid[0].Length;\n\n\tfor (int i = 0; i < rows; i++)\n\t{\n\t\tfor (int j = 0; j < columns; j++)\n\t\t{\n\t\t\t(int twos, int fives) = getTwosAndFives(grid[i][j]);    \n\n\t\t\tif(j > 0)\n\t\t\t{\n\t\t\t\thorizontal[i, j] = (horizontal[i, j - 1].twos + twos, horizontal[i, j - 1].fives + fives);    \n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\thorizontal[i, j] = (twos, fives);    \n\t\t\t}\n\n\t\t\tif(i > 0)\n\t\t\t{\n\t\t\t\tvertical[i, j] = (vertical[i - 1, j].twos + twos, vertical[i - 1, j].fives + fives);    \n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\tvertical[i, j] = (twos, fives);    \n\t\t\t}\n\t\t}\n\t}\n\n\tint result = 0;\n\tfor (int i = 0; i < rows; i++)\n\t{\n\t\tfor (int j = 0; j < columns; j++)\n\t\t{  \n\t\t\tint current1 = Math.Min(vertical[i, j].fives + (horizontal[i, columns - 1].fives - horizontal[i, j].fives),\n\t\t\t\t\t\t\t\t\tvertical[i, j].twos + (horizontal[i, columns - 1].twos - horizontal[i, j].twos));\n\n\t\t\t(int twos, int fives) = horizontal[i, j];                                                                 \n\t\t\tint current2 = 0;\n\t\t\tif(j > 0)\n\t\t\t{\n\t\t\t\ttwos -= horizontal[i, j - 1].twos;\n\t\t\t\tfives -= horizontal[i, j - 1].fives;\n\n\t\t\t\tcurrent2 = Math.Min(vertical[i, j].fives + horizontal[i, j - 1].fives,\n\t\t\t\t\t\t\t\t\tvertical[i, j].twos + horizontal[i, j - 1].twos);                        \n\t\t\t}\n\n\t\t\tint current3 = Math.Min(horizontal[i, j].fives + (vertical[rows - 1, j].fives - vertical[i, j].fives),\n\t\t\t\t\t\t\t\t\thorizontal[i, j].twos + (vertical[rows - 1, j].twos - vertical[i, j].twos));                        \n\n\t\t\tint current4 = Math.Min((horizontal[i, columns - 1].fives - horizontal[i, j].fives)\n\t\t\t\t\t\t\t\t\t\t+ (vertical[rows - 1, j].fives - vertical[i, j].fives) + fives,\n\t\t\t\t\t\t\t\t\t(horizontal[i, columns - 1].twos - horizontal[i, j].twos)\n\t\t\t\t\t\t\t\t\t\t+ (vertical[rows - 1, j].twos - vertical[i, j].twos) + twos);             \n\n\t\t\tint max = (new int[]{current1, current2, current3, current4}).Max();\n\t\t\tresult = Math.Max(result, max);\n\t\t}\n\t}        \n\n\treturn result;\n}\n\nprivate (int twos, int fives) getTwosAndFives(int n)\n{\n\tint twos = 0, fives = 0;\n\n\twhile (n % 5 == 0)\n\t{\n\t\tn /= 5;\n\t\tfives++;\n\t}\n\n\twhile (n % 2 == 0)\n\t{\n\t\tn /= 2;\n\t\ttwos++;\n\t}\n\n\treturn (twos, fives);\n}\n```
[]