Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[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]]
[[4,3,2],[7,6,1],[8,8,8]]
factorial-trailing-zeroes)bomb-enemy)abbreviating-the-product-of-a-range)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2245: Maximum Trailing Zeros in a Cornered Path
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;
}
}
// Accepted solution for LeetCode #2245: Maximum Trailing Zeros in a Cornered Path
func maxTrailingZeros(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
r2 := get(m+1, n+1)
c2 := get(m+1, n+1)
r5 := get(m+1, n+1)
c5 := get(m+1, n+1)
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
x := grid[i-1][j-1]
s2, s5 := 0, 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
}
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
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, max(a, max(b, max(c, d))))
}
}
return
}
func get(m, n int) [][]int {
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
return f
}
# Accepted solution for LeetCode #2245: Maximum Trailing Zeros in a Cornered Path
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
// Accepted solution for LeetCode #2245: Maximum Trailing Zeros in a Cornered Path
/**
* [2245] Maximum Trailing Zeros in a Cornered Path
*
* 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:
* <img alt="" src="https://assets.leetcode.com/uploads/2022/03/23/ex1new2.jpg" style="width: 577px; height: 190px;" />
* 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:
* <img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/ex2.jpg" style="width: 150px; height: 157px;" />
* 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
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/
// discuss: https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
pub fn max_trailing_zeros(grid: Vec<Vec<i32>>) -> i32 {
0
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[ignore]
fn test_2245_example_1() {
let grid = vec![
vec![23, 17, 15, 3, 20],
vec![8, 1, 20, 27, 11],
vec![9, 4, 6, 2, 21],
vec![40, 9, 1, 10, 6],
vec![22, 7, 4, 5, 3],
];
let result = 3;
assert_eq!(Solution::max_trailing_zeros(grid), result);
}
#[test]
#[ignore]
fn test_2245_example_2() {
let grid = vec![vec![4, 3, 2], vec![7, 6, 1], vec![8, 8, 8]];
let result = 0;
assert_eq!(Solution::max_trailing_zeros(grid), result);
}
}
// Accepted solution for LeetCode #2245: Maximum Trailing Zeros in a Cornered Path
function maxTrailingZeros(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const r2 = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
const c2 = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
const r5 = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
const c5 = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
let x = grid[i - 1][j - 1];
let s2 = 0;
let s5 = 0;
for (; x % 2 == 0; x = Math.floor(x / 2)) {
++s2;
}
for (; x % 5 == 0; x = Math.floor(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;
}
}
let ans = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
const a = Math.min(r2[i][j] + c2[i - 1][j], r5[i][j] + c5[i - 1][j]);
const b = Math.min(r2[i][j] + c2[m][j] - c2[i][j], r5[i][j] + c5[m][j] - c5[i][j]);
const c = Math.min(r2[i][n] - r2[i][j] + c2[i][j], r5[i][n] - r5[i][j] + c5[i][j]);
const 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, a, b, c, d);
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.