LeetCode 2245 - Maximum Trailing Zeros in a Cornered Path
This problem asks us to find a path in a matrix whose product contains the maximum possible number of trailing zeros. A trailing zero in a number is created by a factor of 10, and every factor of 10 comes from one factor of 2 paired with one factor of 5.
Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum
Solution
Problem Understanding
This problem asks us to find a path in a matrix whose product contains the maximum possible number of trailing zeros.
A trailing zero in a number is created by a factor of 10, and every factor of 10 comes from one factor of 2 paired with one factor of 5. Therefore, the number of trailing zeros in a product is:
$$\min(\text{count of factor 2}, \text{count of factor 5})$$
The grid contains positive integers, and we may construct a path that moves in a straight line or makes exactly one turn. The path cannot revisit cells.
The path shape is therefore one of these:
- straight horizontal
- straight vertical
- L-shape turning once
The movement can occur in any direction:
- left then up
- left then down
- right then up
- right then down
For every valid cornered path, we compute the product of all numbers along the path and determine how many trailing zeros that product contains. We must return the maximum possible value.
The constraints are important:
- $1 \le m \times n \le 10^5$
- each value is at most 1000
A brute-force simulation of every path and every product would be far too expensive because the number of possible paths is very large.
A key observation is that we never need the full product. We only need:
- total number of factors of 2
- total number of factors of 5
Since every number is at most 1000, factorization is very cheap.
Important edge cases include:
- grids with only one row or one column
- paths with no turn
- cells containing no factors of 2 or 5
- values like 1, which contribute nothing
- avoiding double-counting the turning cell
Approaches
Brute Force
A brute-force solution would enumerate every possible cornered path.
For every cell, we could try:
- extending left/right
- extending up/down
- combining segments into L-shaped paths
For each path, we would multiply all values together or maintain prime factor counts dynamically.
This approach is correct because it explicitly evaluates every valid path. However, it is too slow. Even if we avoid large integer multiplication, the number of possible paths is roughly:
$$O(mn(m+n))$$
and recomputing factor counts repeatedly becomes inefficient.
Key Insight
Trailing zeros depend only on counts of 2 and 5.
Instead of dealing with products directly, we transform every cell into:
- number of factors of 2
- number of factors of 5
Then we build prefix sums for rows and columns.
Using prefix sums allows us to compute the total number of 2s and 5s along any horizontal or vertical segment in constant time.
Every cornered path can then be evaluated in constant time by combining:
- one horizontal segment
- one vertical segment
- subtracting the turning cell once because it belongs to both segments
This reduces the problem to checking four L-shaped configurations per cell.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | $O(mn(m+n))$ | $O(1)$ or $O(mn)$ | Enumerates all paths explicitly |
| Optimal | $O(mn)$ | $O(mn)$ | Uses factor counting and prefix sums |
Algorithm Walkthrough
- Precompute the number of factors of 2 and 5 for every cell.
For each value in the grid, repeatedly divide by 2 and 5 to count how many times each prime factor appears.
For example:
- 20 contributes two 2s and one 5
- 40 contributes three 2s and one 5
- Build row prefix sums.
For every row, maintain cumulative counts of:
- factors of 2
- factors of 5
This allows us to query any horizontal segment in constant time. 3. Build column prefix sums.
Similarly, compute cumulative counts vertically for every column.
This allows constant-time vertical segment queries. 4. Treat every cell as the turning point.
Every valid cornered path can be represented by choosing:
- one horizontal direction
- one vertical direction
There are four possibilities:
- up + left
- up + right
- down + left
- down + right
- Compute factor totals for each shape.
For each configuration:
- retrieve horizontal segment counts
- retrieve vertical segment counts
- subtract the turning cell once because it was counted twice
- Compute trailing zeros.
The number of trailing zeros is:
$$\min(\text{total twos}, \text{total fives})$$
Update the global maximum. 7. Return the maximum result.
Why it works
Every cornered path consists of exactly one horizontal segment and one vertical segment intersecting at a turning cell. Prefix sums let us compute both segments exactly and efficiently. Since trailing zeros depend only on counts of 2 and 5, evaluating all four directional combinations for every cell guarantees that we examine every possible valid path. Therefore, the algorithm always finds the optimal answer.
Python Solution
from typing import List
class Solution:
def maxTrailingZeros(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
twos = [[0] * n for _ in range(m)]
fives = [[0] * n for _ in range(m)]
def count_factor(x: int, factor: int) -> int:
count = 0
while x % factor == 0:
x //= factor
count += 1
return count
# Count factors of 2 and 5 for each cell
for r in range(m):
for c in range(n):
value = grid[r][c]
twos[r][c] = count_factor(value, 2)
fives[r][c] = count_factor(value, 5)
# Row prefix sums
row2 = [[0] * (n + 1) for _ in range(m)]
row5 = [[0] * (n + 1) for _ in range(m)]
for r in range(m):
for c in range(n):
row2[r][c + 1] = row2[r][c] + twos[r][c]
row5[r][c + 1] = row5[r][c] + fives[r][c]
# Column prefix sums
col2 = [[0] * n for _ in range(m + 1)]
col5 = [[0] * n for _ in range(m + 1)]
for c in range(n):
for r in range(m):
col2[r + 1][c] = col2[r][c] + twos[r][c]
col5[r + 1][c] = col5[r][c] + fives[r][c]
answer = 0
for r in range(m):
for c in range(n):
cell2 = twos[r][c]
cell5 = fives[r][c]
left2 = row2[r][c + 1]
left5 = row5[r][c + 1]
right2 = row2[r][n] - row2[r][c]
right5 = row5[r][n] - row5[r][c]
up2 = col2[r + 1][c]
up5 = col5[r + 1][c]
down2 = col2[m][c] - col2[r][c]
down5 = col5[m][c] - col5[r][c]
paths = [
(left2 + up2 - cell2, left5 + up5 - cell5),
(left2 + down2 - cell2, left5 + down5 - cell5),
(right2 + up2 - cell2, right5 + up5 - cell5),
(right2 + down2 - cell2, right5 + down5 - cell5),
]
for total2, total5 in paths:
answer = max(answer, min(total2, total5))
return answer
The implementation begins by transforming each grid value into its contribution of factors of 2 and 5. This preprocessing step is essential because trailing zeros depend only on these two primes.
Next, the solution constructs row and column prefix sums. These arrays allow constant-time retrieval of any horizontal or vertical segment total.
For every cell, the code computes:
- left segment totals
- right segment totals
- upward segment totals
- downward segment totals
The current cell belongs to both segments in every L-shape, so its factor counts are subtracted once to avoid double-counting.
Finally, the solution evaluates all four possible corner configurations and updates the maximum number of trailing zeros.
Go Solution
func maxTrailingZeros(grid [][]int) int {
m := len(grid)
n := len(grid[0])
twos := make([][]int, m)
fives := make([][]int, m)
for i := 0; i < m; i++ {
twos[i] = make([]int, n)
fives[i] = make([]int, n)
}
countFactor := func(x int, factor int) int {
count := 0
for x%factor == 0 {
x /= factor
count++
}
return count
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
value := grid[r][c]
twos[r][c] = countFactor(value, 2)
fives[r][c] = countFactor(value, 5)
}
}
row2 := make([][]int, m)
row5 := make([][]int, m)
for i := 0; i < m; i++ {
row2[i] = make([]int, n+1)
row5[i] = make([]int, n+1)
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
row2[r][c+1] = row2[r][c] + twos[r][c]
row5[r][c+1] = row5[r][c] + fives[r][c]
}
}
col2 := make([][]int, m+1)
col5 := make([][]int, m+1)
for i := 0; i <= m; i++ {
col2[i] = make([]int, n)
col5[i] = make([]int, n)
}
for c := 0; c < n; c++ {
for r := 0; r < m; r++ {
col2[r+1][c] = col2[r][c] + twos[r][c]
col5[r+1][c] = col5[r][c] + fives[r][c]
}
}
maxVal := func(a, b int) int {
if a > b {
return a
}
return b
}
minVal := func(a, b int) int {
if a < b {
return a
}
return b
}
answer := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
cell2 := twos[r][c]
cell5 := fives[r][c]
left2 := row2[r][c+1]
left5 := row5[r][c+1]
right2 := row2[r][n] - row2[r][c]
right5 := row5[r][n] - row5[r][c]
up2 := col2[r+1][c]
up5 := col5[r+1][c]
down2 := col2[m][c] - col2[r][c]
down5 := col5[m][c] - col5[r][c]
candidates := [][]int{
{left2 + up2 - cell2, left5 + up5 - cell5},
{left2 + down2 - cell2, left5 + down5 - cell5},
{right2 + up2 - cell2, right5 + up5 - cell5},
{right2 + down2 - cell2, right5 + down5 - cell5},
}
for _, pair := range candidates {
answer = maxVal(answer, minVal(pair[0], pair[1]))
}
}
}
return answer
}
The Go implementation follows the same structure as the Python solution. Since Go does not provide built-in min and max helpers for integers, helper functions are defined explicitly.
Slices are used for all prefix sum arrays. Integer overflow is not a concern because we never compute the actual product, only counts of prime factors.
Worked Examples
Example 1
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]
]
Consider the optimal path:
15 -> 20
|
6
|
1
|
10
Step 1: Factor counts
| Value | Factors of 2 | Factors of 5 |
|---|---|---|
| 15 | 0 | 1 |
| 20 | 2 | 1 |
| 6 | 1 | 0 |
| 1 | 0 | 0 |
| 10 | 1 | 1 |
Step 2: Total counts
| Prime Factor | Total |
|---|---|
| 2 | 4 |
| 5 | 3 |
Trailing zeros:
$$\min(4, 3) = 3$$
So this path contributes 3 trailing zeros.
The algorithm checks all four orientations at every cell and eventually finds this maximum.
Example 2
grid =
[
[4,3,2],
[7,6,1],
[8,8,8]
]
Factor counts
| Value | Factors of 2 | Factors of 5 |
|---|---|---|
| 4 | 2 | 0 |
| 3 | 0 | 0 |
| 2 | 1 | 0 |
| 7 | 0 | 0 |
| 6 | 1 | 0 |
| 1 | 0 | 0 |
| 8 | 3 | 0 |
Every cell has zero factors of 5.
Therefore, every path also has zero factors of 5.
Since trailing zeros are:
$$\min(\text{twos}, \text{fives})$$
every path has:
$$\min(x, 0) = 0$$
So the answer is 0.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(mn)$ | Each cell is processed a constant number of times |
| Space | $O(mn)$ | Prefix sums and factor arrays store one value per cell |
The factorization work is effectively constant because each grid value is at most 1000. Prefix sum construction and path evaluation both scan the grid once, resulting in linear complexity relative to the number of cells.
Test Cases
from typing import List
class Solution:
def maxTrailingZeros(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
twos = [[0] * n for _ in range(m)]
fives = [[0] * n for _ in range(m)]
def count_factor(x: int, factor: int) -> int:
count = 0
while x % factor == 0:
x //= factor
count += 1
return count
for r in range(m):
for c in range(n):
twos[r][c] = count_factor(grid[r][c], 2)
fives[r][c] = count_factor(grid[r][c], 5)
row2 = [[0] * (n + 1) for _ in range(m)]
row5 = [[0] * (n + 1) for _ in range(m)]
for r in range(m):
for c in range(n):
row2[r][c + 1] = row2[r][c] + twos[r][c]
row5[r][c + 1] = row5[r][c] + fives[r][c]
col2 = [[0] * n for _ in range(m + 1)]
col5 = [[0] * n for _ in range(m + 1)]
for c in range(n):
for r in range(m):
col2[r + 1][c] = col2[r][c] + twos[r][c]
col5[r + 1][c] = col5[r][c] + fives[r][c]
answer = 0
for r in range(m):
for c in range(n):
cell2 = twos[r][c]
cell5 = fives[r][c]
left2 = row2[r][c + 1]
left5 = row5[r][c + 1]
right2 = row2[r][n] - row2[r][c]
right5 = row5[r][n] - row5[r][c]
up2 = col2[r + 1][c]
up5 = col5[r + 1][c]
down2 = col2[m][c] - col2[r][c]
down5 = col5[m][c] - col5[r][c]
paths = [
(left2 + up2 - cell2, left5 + up5 - cell5),
(left2 + down2 - cell2, left5 + down5 - cell5),
(right2 + up2 - cell2, right5 + up5 - cell5),
(right2 + down2 - cell2, right5 + down5 - cell5),
]
for total2, total5 in paths:
answer = max(answer, min(total2, total5))
return answer
sol = Solution()
# Example 1
assert sol.maxTrailingZeros([
[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]
]) == 3 # official example
# Example 2
assert sol.maxTrailingZeros([
[4,3,2],
[7,6,1],
[8,8,8]
]) == 0 # no factors of 5 anywhere
# Single cell
assert sol.maxTrailingZeros([
[10]
]) == 1 # single value already has one trailing zero
# Single row
assert sol.maxTrailingZeros([
[10, 20, 25]
]) == 3 # straight horizontal path
# Single column
assert sol.maxTrailingZeros([
[2],
[5],
[10]
]) == 2 # straight vertical path
# All ones
assert sol.maxTrailingZeros([
[1,1],
[1,1]
]) == 0 # no contributing factors
# Large powers of 2 but no 5
assert sol.maxTrailingZeros([
[64,128],
[256,512]
]) == 0 # cannot form trailing zeros
# Balanced factors
assert sol.maxTrailingZeros([
[10,10],
[10,10]
]) == 3 # optimal L-shape includes three cells
# Turn required for optimal answer
assert sol.maxTrailingZeros([
[5,2,2],
[2,2,10]
]) == 2 # best path requires a corner
Test Summary
| Test | Why |
|---|---|
| Official example 1 | Validates general L-shaped behavior |
| Official example 2 | Validates grids without factor 5 |
| Single cell | Smallest possible grid |
| Single row | Tests straight horizontal paths |
| Single column | Tests straight vertical paths |
| All ones | Tests values contributing no factors |
| Powers of 2 only | Ensures both factors are required |
| All 10s | Tests heavy overlap of valid paths |
| Corner-required case | Ensures turning paths are evaluated |
Edge Cases
Single Row or Single Column
A grid with only one row or one column cannot form a traditional L-shape because there is no second dimension for turning. However, straight paths are still valid because the problem allows paths with at most one turn.
This can easily cause bugs if the implementation assumes every path must bend. The prefix sum approach naturally handles these cases because the horizontal or vertical segment may simply have length one.
Double Counting the Turning Cell
When combining horizontal and vertical segments, the turning cell belongs to both segments. Forgetting to subtract it once leads to inflated factor counts and incorrect answers.
The implementation explicitly subtracts the current cell's factor contribution after combining the two segments.
Grids Without Any Factors of 5
A product can only have trailing zeros if it contains both factors of 2 and factors of 5. Some grids may contain many even numbers but no multiples of 5.
A naive implementation focused only on powers of 2 might incorrectly report positive trailing zeros. Since the algorithm always computes:
$$\min(\text{twos}, \text{fives})$$
the result correctly becomes zero whenever one factor type is absent.
Values Equal to 1
The number 1 contributes no factors of 2 or 5. Long paths containing many 1s can still be optimal because they connect useful cells without reducing the total.
The implementation handles this naturally because factor counts for 1 are simply zero.