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 _themaximum 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.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|c|c|} \hline 23 & 17 & \colorbox{green} {15} & 3 & 20 \\hline 8 & 1 & \colorbox{green} {20} & 27 & 11 \\hline 9 & 4 & \colorbox{green} {6} & 2 & 21 \\hline 40 & 9 & \colorbox{green} {1} & \colorbox{green} {10} & 6 \\hline 22 & 7 & 4 & 5 & 3 \\hline \end{array}

\text{ }

\Huge \begin{array}{|c|c|c|c|c|} \hline 23 & 17 & \colorbox{red} {15} & 3 & 20 \\hline 8 & 1 & \colorbox{red} {20} & 27 & 11 \\hline 9 & 4 & \colorbox{red} {6} & 2 & 21 \\hline 40 & 9 & \colorbox{red} {1} & \colorbox{red} {10} & 6 \\hline 22 & 7 & 4 & \colorbox{red} 5 & 3 \\hline \end{array}

\text{ }

\Huge \begin{array}{|c|c|c|c|c|} \hline 23 & 17 & \colorbox{red} {15} & 3 & 20 \\hline 8 & 1 & \colorbox{red} {20} & 27 & 11 \\hline 9 & 4 & \colorbox{red} {6} & 2 & 21 \\hline \colorbox{red} 40 & \colorbox{red} 9 & \colorbox{red} {1} & \colorbox{red} {10} & 6 \\hline 22 & 7 & 4 & 5 & 3 \\hline \end{array} $$

1
2
3
4
5
6
7
8

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

$$ \Huge \begin{array}{|c|c|c|} \hline 4 & 3 & 2 \\hline 7 & 6 & 1 \\hline 8 & 8 & 8 \\hline \end{array} $$

1
2
3
4

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 <= 10^5
  • 1 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 1000

Solution

Method 1 – Prefix Sums for Factors of 2 and 5

Intuition

Trailing zeros in a product are determined by the minimum number of times 2 and 5 appear in its prime factorization. For each path, we need to count the total number of 2s and 5s in the product. By precomputing prefix sums for factors of 2 and 5 in all rows and columns, we can efficiently calculate the number of trailing zeros for any cornered path.

Approach

  1. For each cell, count the number of 2s and 5s in its value.
  2. Build prefix sums for factors of 2 and 5 for each row and column.
  3. For each cell, consider all four possible cornered paths (up+right, up+left, down+right, down+left) and calculate the total number of 2s and 5s in the path using prefix sums.
  4. The number of trailing zeros for a path is the minimum of the total number of 2s and 5s.
  5. Track the maximum trailing zeros found.

Complexity

  • ⏰ Time complexity: O(mn) — Each cell and each path is checked in constant time using prefix sums.
  • 🧺 Space complexity: O(mn) — For prefix sum arrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    int maxTrailingZeros(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> twos(m, vector<int>(n)), fives(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x = grid[i][j];
                while (x % 2 == 0) { twos[i][j]++; x /= 2; }
                x = grid[i][j];
                while (x % 5 == 0) { fives[i][j]++; x /= 5; }
            }
        }
        vector<vector<int>> row2(m+1, vector<int>(n)), row5(m+1, vector<int>(n)), col2(m, vector<int>(n+1)), col5(m, vector<int>(n+1));
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
            row2[i+1][j] = row2[i][j] + twos[i][j];
            row5[i+1][j] = row5[i][j] + fives[i][j];
            col2[i][j+1] = col2[i][j] + twos[i][j];
            col5[i][j+1] = col5[i][j] + fives[i][j];
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
            int a = row2[i+1][j] + col2[i][n] - col2[i][j+1];
            int b = row5[i+1][j] + col5[i][n] - col5[i][j+1];
            ans = max(ans, min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1];
            ans = max(ans, min(a, b));
            a = row2[i+1][j] + col2[i][j+1];
            b = row5[i+1][j] + col5[i][j+1];
            ans = max(ans, min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][j+1];
            ans = max(ans, min(a, b));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

func maxTrailingZeros(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    twos := make([][]int, m)
    fives := make([][]int, m)
    for i := range grid {
        twos[i] = make([]int, n)
        fives[i] = make([]int, n)
        for j := range grid[i] {
            x := grid[i][j]
            for x%2 == 0 { twos[i][j]++; x /= 2 }
            x = grid[i][j]
            for x%5 == 0 { fives[i][j]++; x /= 5 }
        }
    }
    row2 := make([][]int, m+1)
    row5 := make([][]int, m+1)
    col2 := make([][]int, m)
    col5 := make([][]int, m)
    for i := range row2 { row2[i] = make([]int, n); row5[i] = make([]int, n) }
    for i := range col2 { col2[i] = make([]int, n+1); col5[i] = make([]int, n+1) }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            row2[i+1][j] = row2[i][j] + twos[i][j]
            row5[i+1][j] = row5[i][j] + fives[i][j]
            col2[i][j+1] = col2[i][j] + twos[i][j]
            col5[i][j+1] = col5[i][j] + fives[i][j]
        }
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            a := row2[i+1][j] + col2[i][n] - col2[i][j+1]
            b := row5[i+1][j] + col5[i][n] - col5[i][j+1]
            if min(a, b) > ans { ans = min(a, b) }
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1]
            if min(a, b) > ans { ans = min(a, b) }
            a = row2[i+1][j] + col2[i][j+1]
            b = row5[i+1][j] + col5[i][j+1]
            if min(a, b) > ans { ans = min(a, b) }
            a = row2[m][j] - row2[i][j] + col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][j+1]
            if min(a, b) > ans { ans = min(a, b) }
        }
    }
    return ans
}
func min(a, b int) int { if a < b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] twos = new int[m][n], fives = new int[m][n];
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
            int x = grid[i][j];
            while (x % 2 == 0) { twos[i][j]++; x /= 2; }
            x = grid[i][j];
            while (x % 5 == 0) { fives[i][j]++; x /= 5; }
        }
        int[][] row2 = new int[m+1][n], row5 = new int[m+1][n], col2 = new int[m][n+1], col5 = new int[m][n+1];
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
            row2[i+1][j] = row2[i][j] + twos[i][j];
            row5[i+1][j] = row5[i][j] + fives[i][j];
            col2[i][j+1] = col2[i][j] + twos[i][j];
            col5[i][j+1] = col5[i][j] + fives[i][j];
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
            int a = row2[i+1][j] + col2[i][n] - col2[i][j+1];
            int b = row5[i+1][j] + col5[i][n] - col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[i+1][j] + col2[i][j+1];
            b = row5[i+1][j] + col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    fun maxTrailingZeros(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val twos = Array(m) { IntArray(n) }
        val fives = Array(m) { IntArray(n) }
        for (i in 0 until m) for (j in 0 until n) {
            var x = grid[i][j]
            while (x % 2 == 0) { twos[i][j]++; x /= 2 }
            x = grid[i][j]
            while (x % 5 == 0) { fives[i][j]++; x /= 5 }
        }
        val row2 = Array(m+1) { IntArray(n) }
        val row5 = Array(m+1) { IntArray(n) }
        val col2 = Array(m) { IntArray(n+1) }
        val col5 = Array(m) { IntArray(n+1) }
        for (i in 0 until m) for (j in 0 until n) {
            row2[i+1][j] = row2[i][j] + twos[i][j]
            row5[i+1][j] = row5[i][j] + fives[i][j]
            col2[i][j+1] = col2[i][j] + twos[i][j]
            col5[i][j+1] = col5[i][j] + fives[i][j]
        }
        var ans = 0
        for (i in 0 until m) for (j in 0 until n) {
            var a = row2[i+1][j] + col2[i][n] - col2[i][j+1]
            var b = row5[i+1][j] + col5[i][n] - col5[i][j+1]
            ans = maxOf(ans, minOf(a, b))
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1]
            ans = maxOf(ans, minOf(a, b))
            a = row2[i+1][j] + col2[i][j+1]
            b = row5[i+1][j] + col5[i][j+1]
            ans = maxOf(ans, minOf(a, b))
            a = row2[m][j] - row2[i][j] + col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][j+1]
            ans = maxOf(ans, minOf(a, b))
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def max_trailing_zeros(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)]
    for i in range(m):
        for j in range(n):
            x = grid[i][j]
            while x % 2 == 0:
                twos[i][j] += 1
                x //= 2
            x = grid[i][j]
            while x % 5 == 0:
                fives[i][j] += 1
                x //= 5
    row2 = [[0]*n for _ in range(m+1)]
    row5 = [[0]*n for _ in range(m+1)]
    col2 = [[0]*(n+1) for _ in range(m)]
    col5 = [[0]*(n+1) for _ in range(m)]
    for i in range(m):
        for j in range(n):
            row2[i+1][j] = row2[i][j] + twos[i][j]
            row5[i+1][j] = row5[i][j] + fives[i][j]
            col2[i][j+1] = col2[i][j] + twos[i][j]
            col5[i][j+1] = col5[i][j] + fives[i][j]
    ans = 0
    for i in range(m):
        for j in range(n):
            a = row2[i+1][j] + col2[i][n] - col2[i][j+1]
            b = row5[i+1][j] + col5[i][n] - col5[i][j+1]
            ans = max(ans, min(a, b))
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1]
            ans = max(ans, min(a, b))
            a = row2[i+1][j] + col2[i][j+1]
            b = row5[i+1][j] + col5[i][j+1]
            ans = max(ans, min(a, b))
            a = row2[m][j] - row2[i][j] + col2[i][j+1]
            b = row5[m][j] - row5[i][j] + col5[i][j+1]
            ans = max(ans, min(a, b))
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

impl Solution {
    pub fn max_trailing_zeros(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut twos = vec![vec![0; n]; m];
        let mut fives = vec![vec![0; n]; m];
        for i in 0..m {
            for j in 0..n {
                let mut x = grid[i][j];
                while x % 2 == 0 { twos[i][j] += 1; x /= 2; }
                x = grid[i][j];
                while x % 5 == 0 { fives[i][j] += 1; x /= 5; }
            }
        }
        let mut row2 = vec![vec![0; n]; m+1];
        let mut row5 = vec![vec![0; n]; m+1];
        let mut col2 = vec![vec![0; n+1]; m];
        let mut col5 = vec![vec![0; n+1]; m];
        for i in 0..m {
            for j in 0..n {
                row2[i+1][j] = row2[i][j] + twos[i][j];
                row5[i+1][j] = row5[i][j] + fives[i][j];
                col2[i][j+1] = col2[i][j] + twos[i][j];
                col5[i][j+1] = col5[i][j] + fives[i][j];
            }
        }
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                let mut a = row2[i+1][j] + col2[i][n] - col2[i][j+1];
                let mut b = row5[i+1][j] + col5[i][n] - col5[i][j+1];
                ans = ans.max(a.min(b));
                a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1];
                b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1];
                ans = ans.max(a.min(b));
                a = row2[i+1][j] + col2[i][j+1];
                b = row5[i+1][j] + col5[i][j+1];
                ans = ans.max(a.min(b));
                a = row2[m][j] - row2[i][j] + col2[i][j+1];
                b = row5[m][j] - row5[i][j] + col5[i][j+1];
                ans = ans.max(a.min(b));
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    maxTrailingZeros(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        const twos = Array.from({length: m}, () => Array(n).fill(0));
        const fives = Array.from({length: m}, () => Array(n).fill(0));
        for (let i = 0; i < m; ++i) for (let j = 0; j < n; ++j) {
            let x = grid[i][j];
            while (x % 2 === 0) { twos[i][j]++; x /= 2; }
            x = grid[i][j];
            while (x % 5 === 0) { fives[i][j]++; x /= 5; }
        }
        const row2 = Array.from({length: m+1}, () => Array(n).fill(0));
        const row5 = Array.from({length: m+1}, () => Array(n).fill(0));
        const col2 = Array.from({length: m}, () => Array(n+1).fill(0));
        const col5 = Array.from({length: m}, () => Array(n+1).fill(0));
        for (let i = 0; i < m; ++i) for (let j = 0; j < n; ++j) {
            row2[i+1][j] = row2[i][j] + twos[i][j];
            row5[i+1][j] = row5[i][j] + fives[i][j];
            col2[i][j+1] = col2[i][j] + twos[i][j];
            col5[i][j+1] = col5[i][j] + fives[i][j];
        }
        let ans = 0;
        for (let i = 0; i < m; ++i) for (let j = 0; j < n; ++j) {
            let a = row2[i+1][j] + col2[i][n] - col2[i][j+1];
            let b = row5[i+1][j] + col5[i][n] - col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][n] - col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][n] - col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[i+1][j] + col2[i][j+1];
            b = row5[i+1][j] + col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
            a = row2[m][j] - row2[i][j] + col2[i][j+1];
            b = row5[m][j] - row5[i][j] + col5[i][j+1];
            ans = Math.max(ans, Math.min(a, b));
        }
        return ans;
    }
}