Watch 6 video solutions for Maximum Trailing Zeros in a Cornered Path, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by Bro Coders has 2,472 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Example 1:
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:
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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1051 <= grid[i][j] <= 1000Problem Overview: You are given an m x n grid of positive integers. A valid path starts at any cell, moves in one direction (up, down, left, or right), makes at most one turn, and continues in the new direction. The product of all numbers along the path determines the number of trailing zeros. The goal is to return the maximum trailing zeros obtainable from any such cornered path.
The number of trailing zeros in a number depends on how many times it can be divided by 10. Since 10 = 2 × 5, the trailing zero count equals min(count(2), count(5)) in the prime factorization of the product.
Approach 1: Direct Path Enumeration (O(m*n*(m+n)) time, O(1) extra space)
This approach checks every cell as a potential turning point and explicitly enumerates all four possible corner shapes: up-left, up-right, down-left, and down-right. For each direction, iterate outward while accumulating the number of factors of 2 and 5 from each visited cell. After building the path product factor counts, compute trailing zeros using min(total2, total5). The process repeats for every cell and direction combination. The logic is straightforward and mirrors the definition of the problem, but repeated factor counting makes it slower for large grids.
Approach 2: Prefix Sum Approach for Factor Counts (O(m*n) time, O(m*n) space)
The optimized solution precomputes how many factors of 2 and 5 each grid value contributes. Build row-wise and column-wise prefix sums storing cumulative counts of these factors. With these prefix arrays, you can instantly compute the total factors for any vertical or horizontal segment in constant time.
For each cell treated as the corner, evaluate the four possible L-shaped paths: left+up, left+down, right+up, and right+down. Use prefix sums to get the factor counts of both segments and combine them while avoiding double-counting the corner cell. Compute trailing zeros using min(total2, total5) and track the maximum. Because each cell is processed once and segment queries are O(1), the total runtime becomes linear in the grid size.
This technique relies on efficient cumulative counting using prefix sums and systematic traversal of a matrix. Factor extraction and counting can be viewed as preprocessing on the array values before building prefix structures.
Recommended for interviews: The prefix sum approach is the expected solution. It reduces repeated factor counting and brings the complexity down to O(m*n). Discussing the enumeration approach first shows understanding of the path structure, but implementing prefix sums demonstrates optimization skills interviewers typically look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Path Enumeration | O(m*n*(m+n)) | O(1) | Good for understanding the path structure or small grids where repeated traversal cost is manageable |
| Prefix Sum for Factor Counts | O(m*n) | O(m*n) | Best general solution; avoids recomputation using prefix sums for fast segment queries |