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.
This approach involves computing prefix sums of factors of 2 and 5 for each row and column in the grid. By doing so, we align ourselves to quickly calculate the number of trailing zeros of any path by examining differences between these sums.
We precompute the number of factors of 2 and 5 present in numbers from the start of each row and column to each position. This allows us to quickly determine the number of such factors in any horizontal or vertical path segment.
Python
JavaScript
Time Complexity: O(m * n)
Space Complexity: O(m * n)
This approach involves direct enumeration of potential cornered paths and computing their trailing zeroes by counting factor contributions at each step. Although computationally more extensive, this method provides stepwise clarity.
This C++ solution explores every potential path explicitly, counting the contributions of each number in the path to the trailing zero count. It manages paths by unwinding horizontal and vertical segments from each start position.
Time Complexity: O(m * n) for small grids (dependent on stepping and checks)
Space Complexity: O(1)
Firstly, we need to understand that for a product, the number of trailing zeros depends on the smaller count of 2 and 5 in its factors. Also, each corner path should cover as many numbers as possible, so it must start from a boundary, reach a turning point, and then reach another boundary.
Therefore, we can create four two-dimensional arrays r2, c2, r5, c5 to record the counts of 2 and 5 in each row and column. Where:
r2[i][j] represents the count of 2 from the first column to the j-th column in the i-th row;c2[i][j] represents the count of 2 from the first row to the i-th row in the j-th column;r5[i][j] represents the count of 5 from the first column to the j-th column in the i-th row;c5[i][j] represents the count of 5 from the first row to the i-th row in the j-th column.Next, we traverse the two-dimensional array grid. For each number, we calculate its counts of 2 and 5, and then update the four two-dimensional arrays.
Then, we enumerate the turning point (i, j). For each turning point, we calculate four values:
a represents the smaller count of 2 and 5 in the path that moves right from (i, 1) to (i, j), then turns and moves up to (1, j);b represents the smaller count of 2 and 5 in the path that moves right from (i, 1) to (i, j), then turns and moves down to (m, j);c represents the smaller count of 2 and 5 in the path that moves left from (i, n) to (i, j), then turns and moves up to (1, j);d represents the smaller count of 2 and 5 in the path that moves left from (i, n) to (i, j), then turns and moves down to (m, j).Each time we enumerate, we take the maximum of these four values, and then update the answer.
Finally, we return the answer.
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n are the number of rows and columns of the grid array, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum Approach for Factor Counts | Time Complexity: O(m * n) |
| Direct Path Enumeration | Time Complexity: O(m * n) for small grids (dependent on stepping and checks) |
| Prefix Sum + Enumerate Turning Point | — |
| 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 |
2245. Maximum Trailing Zeros in a Cornered Path || Leetcode Weekly Contest 289 || Leetcode 2245 • Bro Coders • 2,472 views views
Watch 5 more video solutions →Practice Maximum Trailing Zeros in a Cornered Path with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor