# Maximum Trailing Zeros in a Cornered Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path)
Canonical: https://scaleengineer.com/dsa/problems/maximum-trailing-zeros-in-a-cornered-path
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
You are given a 2D integer array `grid` of size `m x n`, where each cell contains a positive integer.

A **cornered path** is defined as a set of adjacent cells with **at most** one turn. More specifically, the path should exclusively move either **horizontally** or **vertically** up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the **alternate** direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.

The **product** of a path is defined as the product of all the values in the path.

Return _the **maximum** number of **trailing zeros** in the product of a cornered path found in_ `grid`.

Note:

* **Horizontal** movement means moving in either the left or right direction.
* **Vertical** movement means moving in either the up or down direction.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-trailing-zeros-in-a-cornered-path/image0.jpg) 

**Input:** grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
**Output:** 3
**Explanation:** The grid on the left shows a valid cornered path.
It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros.
It can be shown that this is the maximum trailing zeros in the product of a cornered path.

The grid in the middle is not a cornered path as it has more than one turn.
The grid on the right is not a cornered path as it requires a return to a previously visited cell.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-trailing-zeros-in-a-cornered-path/image1.jpg) 

**Input:** grid = [[4,3,2],[7,6,1],[8,8,8]]
**Output:** 0
**Explanation:** The grid is shown in the figure above.
There are no cornered paths in the grid that result in a product with a trailing zero.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 105`
* `1 <= m * n <= 105`
* `1 <= grid[i][j] <= 1000`

# Approaches
## Brute Force with Prefix Sums
This approach systematically checks every possible cornered path. It iterates through each cell `(i, j)` as a potential corner. For each corner, it then considers all possible start and end points for the vertical and horizontal segments that form the 'L' shape. To avoid re-calculating the product and factors for each path from scratch, it pre-computes prefix sums of the factor counts (2s and 5s) for every row and column. This allows for `O(1)` lookup of the total factors for any given segment. Finally, it compares the results from all possible paths to find the maximum number of trailing zeros.
**Time:** O(m^2 * n^2). There are `O(m*n)` choices for the corner cell. For each corner, there are `O(m*n)` choices for the endpoints of the two arms. Calculating factors for each path takes `O(1)` with prefix sums. · **Space:** O(m * n) to store the factor grid and the prefix sum grids.
**Pros:** It is a direct translation of the problem definition, making it relatively easy to conceptualize.; It guarantees finding the correct answer by checking every single possibility.
**Cons:** The time complexity of `O(m^2 * n^2)` is too high for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is to exhaustively explore all valid paths. A cornered path is defined by its corner cell and the extents of its two arms (one vertical, one horizontal).

1.  **Factor Pre-computation**: First, we realize that the number of trailing zeros is determined by `min(count_of_2s, count_of_5s)` in the prime factorization of the path's product. We pre-process the grid to create a `factorsGrid` where each cell `(i, j)` stores the counts of factors 2 and 5 for `grid[i][j]`.

2.  **Prefix Sums**: To quickly calculate the total factors for any path segment, we use prefix sums. We build two grids:
    *   `prefixRow[i][j]`: Sum of factors from `(i, 0)` to `(i, j)`.
    *   `prefixCol[i][j]`: Sum of factors from `(0, j)` to `(i, j)`.
    This allows us to find the factors for any sub-segment like `(i, c1)` to `(i, c2)` in `O(1)` time by subtracting prefix sums.

3.  **Path Iteration**: The main loop iterates through every cell `(i, j)` as the corner. For each corner, it tries all four L-shape orientations (e.g., Top-Left, where the path comes from above and turns left). For a Top-Left L-shape at `(i, j)`, we would iterate through all possible vertical segments `(k, j)` to `(i, j)` (where `0 <= k <= i`) and all horizontal segments `(i, l)` to `(i, j)` (where `0 <= l <= j`).

4.  **Calculate and Update**: For each of these `(i+1) * (j+1)` paths for a Top-Left corner at `(i,j)`, we use the prefix sum grids to find the total factor counts, calculate the number of zeros, and update a global maximum. This process is repeated for all four orientations and all possible corners.

5.  **Straight Paths**: A similar exhaustive check is required for straight paths (paths with no turns), which involves checking every possible sub-array of every row and column.

```java
// This is a conceptual representation. A full implementation would be very long and inefficient.
class Solution {
    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][][] factorsGrid = new int[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                factorsGrid[i][j] = countFactors(grid[i][j]);
            }
        }

        int[][][] prefixRow = new int[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixRow[i][j][0] = factorsGrid[i][j][0] + (j > 0 ? prefixRow[i][j - 1][0] : 0);
                prefixRow[i][j][1] = factorsGrid[i][j][1] + (j > 0 ? prefixRow[i][j - 1][1] : 0);
            }
        }

        int[][][] prefixCol = new int[m][n][2];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                prefixCol[i][j][0] = factorsGrid[i][j][0] + (i > 0 ? prefixCol[i - 1][j][0] : 0);
                prefixCol[i][j][1] = factorsGrid[i][j][1] + (i > 0 ? prefixCol[i - 1][j][1] : 0);
            }
        }

        int maxZeros = 0;

        // Incomplete: Iterating all paths is too complex to write out fully
        // and would be O(m^2 * n^2).
        // For each corner (i, j):
        //   For each vertical start k:
        //     For each horizontal start l:
        //       Calculate path factors using prefix sums.
        //       Update maxZeros.

        // Also handle straight paths...

        return maxZeros; // Placeholder for the result
    }

    private int[] countFactors(int num) {
        int count2 = 0;
        int count5 = 0;
        while (num > 0 && num % 2 == 0) {
            count2++;
            num /= 2;
        }
        while (num > 0 && num % 5 == 0) {
            count5++;
            num /= 5;
        }
        return new int[]{count2, count5};
    }
}
```
### Algorithm
*   Define a helper function `countFactors(n)` that computes the number of factors of 2 and 5 in an integer `n` and returns them as a pair `(c2, c5)`.
*   Create a `factorsGrid` of size `m x n` by applying `countFactors` to each element of the input `grid`.
*   Create two prefix sum grids, `prefixRow` and `prefixCol`, both of size `m x n`. Each cell will store a pair of factor counts.
    *   `prefixRow[i][j]` will store the sum of factors for cells `(i, 0)` through `(i, j)`.
    *   `prefixCol[i][j]` will store the sum of factors for cells `(0, j)` through `(i, j)`.
*   Initialize a variable `maxZeros` to 0.
*   Iterate through every cell `(i, j)` in the grid, considering it as a potential corner for an L-shaped path.
*   For each corner `(i, j)`, iterate through all possible starting points for the vertical arm (`k` from `0` to `m-1`) and horizontal arm (`l` from `0` to `n-1`).
*   For each combination of `(i, j, k, l)`, determine the path segments (e.g., vertical from `k` to `i`, horizontal from `l` to `j`).
*   Use the pre-computed prefix sum grids to calculate the total factors `(total_c2, total_c5)` for the formed path in `O(1)` time. Remember to subtract the factors of the corner cell `(i, j)` once as it's included in both row and column sums.
*   Update `maxZeros = max(maxZeros, min(total_c2, total_c5))`.
*   Separately, handle straight paths by iterating through all possible start and end indices for every row and column, calculating their zeros using prefix sums, and updating `maxZeros`.
*   Return `maxZeros`.

## Optimized Prefix Sum Calculation
This approach significantly optimizes the calculation by leveraging a key insight: for any given path, extending its segments can only increase or maintain the number of trailing zeros. This is because all grid values are positive, so extending a path means multiplying by more integers, which cannot decrease the counts of prime factors 2 and 5.

This insight implies we don't need to check every possible path length. For any cell `(i, j)` acting as a corner, the L-shaped path that will yield the maximum number of zeros is the one whose arms extend all the way to the boundaries of the grid. The same logic applies to straight paths; the full row or column path is optimal among all its subpaths.

Therefore, the problem simplifies to: for each cell `(i, j)`, calculate the zeros for the four L-shaped paths that have `(i, j)` as a corner and arms extending to the boundaries. The overall maximum among these `4 * m * n` paths will be the answer. This can be done efficiently by pre-calculating prefix and suffix sums of factors from all four directions (top, bottom, left, right).
**Time:** O(m * n). The pre-computation of factors and all four prefix/suffix sum grids takes `O(m*n)`. The final loop to check every cell as a corner also takes `O(m*n)`. The overall complexity is dominated by these linear scans. · **Space:** O(m * n). We need to store five grids of size `m x n`: one for the initial factor counts and four for the prefix/suffix sums.
**Pros:** Extremely efficient with a linear time complexity relative to the grid size.; Provides an optimal solution that passes the given constraints.
**Cons:** Requires significant auxiliary space (`O(m*n)`) to store the five helper grids.; The core insight that only boundary-extended paths need to be checked is non-trivial and requires careful reasoning.
### Explanation
This method is built upon dynamic programming and a crucial observation about the problem's properties.

**1. The Insight:**
The product of a path `P'` which is a superset of another path `P` (i.e., `P'` contains all cells of `P` plus some others) will have at least as many factors of 2 and 5 as the product of `P`. This is because `product(P') = product(P) * K`, where `K` is the product of the additional positive integers. Thus, `zeros(P') >= zeros(P)`. This means we only need to consider the 'longest' possible paths. For an L-path with corner `(i,j)`, the longest versions are those whose arms stretch to the grid boundaries. For a straight path, it's the full row or column. An L-path check inherently covers the straight path cases as well, so we only need to check the L-paths.

**2. Algorithm Steps:**
First, we pre-calculate the number of factors of 2 and 5 for each number in the grid. Let's store this in `factorsGrid[i][j] = {count2, count5}`.

Next, we create four DP tables (prefix/suffix sum grids) to store cumulative factor counts from four directions:
*   `fromLeft[i][j]`: Cumulative factors from `(i,0)` to `(i,j)`. `fromLeft[i][j] = fromLeft[i][j-1] + factorsGrid[i][j]`.
*   `fromRight[i][j]`: Cumulative factors from `(i,n-1)` to `(i,j)`. `fromRight[i][j] = fromRight[i][j+1] + factorsGrid[i][j]`.
*   `fromTop[i][j]`: Cumulative factors from `(0,j)` to `(i,j)`. `fromTop[i][j] = fromTop[i-1][j] + factorsGrid[i][j]`.
*   `fromBottom[i][j]`: Cumulative factors from `(m-1,j)` to `(i,j)`. `fromBottom[i][j] = fromBottom[i+1][j] + factorsGrid[i][j]`.

These four grids can be populated in `O(m*n)` time.

Finally, we iterate through every cell `(i, j)` and treat it as a corner. For each cell, we test four path combinations:
1.  Top arm + Left arm: Total factors are `fromTop[i][j] + fromLeft[i][j] - factorsGrid[i][j]`. The corner's factors are subtracted because they are counted in both sums.
2.  Top arm + Right arm: `fromTop[i][j] + fromRight[i][j] - factorsGrid[i][j]`.
3.  Bottom arm + Left arm: `fromBottom[i][j] + fromLeft[i][j] - factorsGrid[i][j]`.
4.  Bottom arm + Right arm: `fromBottom[i][j] + fromRight[i][j] - factorsGrid[i][j]`.

For each combination, we find `min(total_c2, total_c5)` and keep track of the maximum value found across all `m*n` cells and their four path combinations.

```java
class Solution {
    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][][] factors = new int[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                factors[i][j] = countFactors(grid[i][j]);
            }
        }

        int[][][] fromLeft = new int[m][n][2];
        int[][][] fromTop = new int[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                fromLeft[i][j][0] = factors[i][j][0] + (j > 0 ? fromLeft[i][j - 1][0] : 0);
                fromLeft[i][j][1] = factors[i][j][1] + (j > 0 ? fromLeft[i][j - 1][1] : 0);
                fromTop[i][j][0] = factors[i][j][0] + (i > 0 ? fromTop[i - 1][j][0] : 0);
                fromTop[i][j][1] = factors[i][j][1] + (i > 0 ? fromTop[i - 1][j][1] : 0);
            }
        }

        int[][][] fromRight = new int[m][n][2];
        int[][][] fromBottom = new int[m][n][2];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                fromRight[i][j][0] = factors[i][j][0] + (j < n - 1 ? fromRight[i][j + 1][0] : 0);
                fromRight[i][j][1] = factors[i][j][1] + (j < n - 1 ? fromRight[i][j + 1][1] : 0);
                fromBottom[i][j][0] = factors[i][j][0] + (i < m - 1 ? fromBottom[i + 1][j][0] : 0);
                fromBottom[i][j][1] = factors[i][j][1] + (i < m - 1 ? fromBottom[i + 1][j][1] : 0);
            }
        }

        int maxZeros = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int c2, c5;
                // Top-Left
                c2 = fromTop[i][j][0] + fromLeft[i][j][0] - factors[i][j][0];
                c5 = fromTop[i][j][1] + fromLeft[i][j][1] - factors[i][j][1];
                maxZeros = Math.max(maxZeros, Math.min(c2, c5));

                // Top-Right
                c2 = fromTop[i][j][0] + fromRight[i][j][0] - factors[i][j][0];
                c5 = fromTop[i][j][1] + fromRight[i][j][1] - factors[i][j][1];
                maxZeros = Math.max(maxZeros, Math.min(c2, c5));

                // Bottom-Left
                c2 = fromBottom[i][j][0] + fromLeft[i][j][0] - factors[i][j][0];
                c5 = fromBottom[i][j][1] + fromLeft[i][j][1] - factors[i][j][1];
                maxZeros = Math.max(maxZeros, Math.min(c2, c5));

                // Bottom-Right
                c2 = fromBottom[i][j][0] + fromRight[i][j][0] - factors[i][j][0];
                c5 = fromBottom[i][j][1] + fromRight[i][j][1] - factors[i][j][1];
                maxZeros = Math.max(maxZeros, Math.min(c2, c5));
            }
        }
        return maxZeros;
    }

    private int[] countFactors(int num) {
        int count2 = 0;
        int count5 = 0;
        while (num > 0 && num % 2 == 0) {
            count2++;
            num /= 2;
        }
        while (num > 0 && num % 5 == 0) {
            count5++;
            num /= 5;
        }
        return new int[]{count2, count5};
    }
}
```
### Algorithm
*   Define a helper function `countFactors(n)` to count factors of 2 and 5.
*   Create a `factorsGrid[m][n]` where each cell `[i][j]` stores the `(c2, c5)` pair for `grid[i][j]`.
*   Create four prefix/suffix sum grids of size `m x n`:
    *   `fromTop[i][j]`: Sum of factors from `(0, j)` to `(i, j)`.
    *   `fromLeft[i][j]`: Sum of factors from `(i, 0)` to `(i, j)`.
    *   `fromBottom[i][j]`: Sum of factors from `(m-1, j)` to `(i, j)`.
    *   `fromRight[i][j]`: Sum of factors from `(i, n-1)` to `(i, j)`.
*   Populate these four grids. This can be done in `O(m*n)` time.
*   Initialize `maxZeros = 0`.
*   Iterate through every cell `(i, j)` of the grid, considering it as the corner of a path.
*   For each `(i, j)`, calculate the factor counts for the four possible L-shaped paths whose arms extend to the grid boundaries:
    1.  Top arm + Left arm: `factors = fromTop[i][j] + fromLeft[i][j] - factorsGrid[i][j]`
    2.  Top arm + Right arm: `factors = fromTop[i][j] + fromRight[i][j] - factorsGrid[i][j]`
    3.  Bottom arm + Left arm: `factors = fromBottom[i][j] + fromLeft[i][j] - factorsGrid[i][j]`
    4.  Bottom arm + Right arm: `factors = fromBottom[i][j] + fromRight[i][j] - factorsGrid[i][j]`
*   For each of these four resulting factor pairs `(c2, c5)`, update `maxZeros = max(maxZeros, min(c2, c5))`.
*   Return `maxZeros`.

# Solutions
### Java

```java
class Solution {
public
  int maxTrailingZeros(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] r2 = new int[m + 1][n + 1];
    int[][] c2 = new int[m + 1][n + 1];
    int[][] r5 = new int[m + 1][n + 1];
    int[][] c5 = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = grid[i - 1][j - 1];
        int s2 = 0, s5 = 0;
        for (; x % 2 == 0; x /= 2) {
          ++s2;
        }
        for (; x % 5 == 0; x /= 5) {
          ++s5;
        }
        r2[i][j] = r2[i][j - 1] + s2;
        c2[i][j] = c2[i - 1][j] + s2;
        r5[i][j] = r5[i][j - 1] + s5;
        c5[i][j] = c5[i - 1][j] + s5;
      }
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int a = Math.min(r2[i][j] + c2[i - 1][j], r5[i][j] + c5[i - 1][j]);
        int b = Math.min(r2[i][j] + c2[m][j] - c2[i][j],
                         r5[i][j] + c5[m][j] - c5[i][j]);
        int c = Math.min(r2[i][n] - r2[i][j] + c2[i][j],
                         r5[i][n] - r5[i][j] + c5[i][j]);
        int d = Math.min(r2[i][n] - r2[i][j - 1] + c2[m][j] - c2[i][j],
                         r5[i][n] - r5[i][j - 1] + c5[m][j] - c5[i][j]);
        ans = Math.max(ans, Math.max(a, Math.max(b, Math.max(c, d))));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxTrailingZeros(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> r2(m + 1, vector<int>(n + 1));
    vector<vector<int>> c2(m + 1, vector<int>(n + 1));
    vector<vector<int>> r5(m + 1, vector<int>(n + 1));
    vector<vector<int>> c5(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = grid[i - 1][j - 1];
        int s2 = 0, s5 = 0;
        for (; x % 2 == 0; x /= 2) {
          ++s2;
        }
        for (; x % 5 == 0; x /= 5) {
          ++s5;
        }
        r2[i][j] = r2[i][j - 1] + s2;
        c2[i][j] = c2[i - 1][j] + s2;
        r5[i][j] = r5[i][j - 1] + s5;
        c5[i][j] = c5[i - 1][j] + s5;
      }
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int a = min(r2[i][j] + c2[i - 1][j], r5[i][j] + c5[i - 1][j]);
        int b =
            min(r2[i][j] + c2[m][j] - c2[i][j], r5[i][j] + c5[m][j] - c5[i][j]);
        int c =
            min(r2[i][n] - r2[i][j] + c2[i][j], r5[i][n] - r5[i][j] + c5[i][j]);
        int d = min(r2[i][n] - r2[i][j - 1] + c2[m][j] - c2[i][j],
                    r5[i][n] - r5[i][j - 1] + c5[m][j] - c5[i][j]);
        ans = max({ans, a, b, c, d});
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxTrailingZeros(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) r2 = [[0] * (n + 1) for _ in range(m + 1)] c2 = [[0] * (n + 1) for _ in range(m + 1)] r5 = [[0] * (n + 1) for _ in range(m + 1)] c5 = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(grid, 1): for j, x in enumerate(row, 1): s2 = s5 = 0 while x % 2 == 0: x //= 2 s2 += 1 while x % 5 == 0: x //= 5 s5 += 1 r2[i][j] = r2[i][j - 1] + s2 c2[i][j] = c2[i - 1][j] + s2 r5[i][j] = r5[i][j - 1] + s5 c5[i][j] = c5[i - 1][j] + s5 ans = 0 for i in range(1, m + 1): for j in range(1, n + 1): a = min(r2[i][j] + c2[i - 1][j], r5[i][j] + c5[i - 1][j]) b = min(r2[i][j] + c2[m][j] - c2[i][j], r5[i][j] + c5[m][j] - c5[i][j]) c = min(r2[i][n] - r2[i][j] + c2[i][j], r5[i][n] - r5[i][j] + c5[i][j]) d = min(r2[i][n] - r2[i][j - 1] + c2[m][j] - c2[i][j], r5[i][n] - r5[i][j - 1] + c5[m][j] - c5[i][j], ) ans = max(ans, a, b, c, d) return ans

```