Maximum trailing zeros in a cornered path

Array Matrix Prefix Sum

37.5% acceptance

Feb 25, 2026

202

407

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_trailing_zeros(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    let count_factor = |mut v: i32, p: i32| -> i32 {
      let mut c = 0;
      while v % p == 0 { v /= p; c += 1; }
      c
    };

    // f2[r][c] and f5[r][c]: factor counts for each cell
    let mut f2 = vec![vec![0i32; n]; m];
    let mut f5 = vec![vec![0i32; n]; m];
    for r in 0..m {
      for c in 0..n {
        f2[r][c] = count_factor(grid[r][c], 2);
        f5[r][c] = count_factor(grid[r][c], 5);
      }
    }

    // Row prefix sums: rf2[r][c] = sum of f2 in row r from col 0..=c
    let mut rf2 = vec![vec![0i32; n]; m];
    let mut rf5 = vec![vec![0i32; n]; m];
    for r in 0..m {
      rf2[r][0] = f2[r][0];
      rf5[r][0] = f5[r][0];
      for c in 1..n {
        rf2[r][c] = rf2[r][c-1] + f2[r][c];
        rf5[r][c] = rf5[r][c-1] + f5[r][c];
      }
    }

    // Col prefix sums: cf2[r][c] = sum of f2 in col c from row 0..=r
    let mut cf2 = vec![vec![0i32; n]; m];
    let mut cf5 = vec![vec![0i32; n]; m];
    for c in 0..n {
      cf2[0][c] = f2[0][c];
      cf5[0][c] = f5[0][c];
      for r in 1..m {
        cf2[r][c] = cf2[r-1][c] + f2[r][c];
        cf5[r][c] = cf5[r-1][c] + f5[r][c];
      }
    }

    let mut ans = 0;
    for r in 0..m {
      for c in 0..n {
        let cell_f2 = f2[r][c];
        let cell_f5 = f5[r][c];

        let left2 = rf2[r][c];
        let left5 = rf5[r][c];
        let right2 = rf2[r][n-1] - if c > 0 { rf2[r][c-1] } else { 0 };
        let right5 = rf5[r][n-1] - if c > 0 { rf5[r][c-1] } else { 0 };
        let up2 = cf2[r][c];
        let up5 = cf5[r][c];
        let down2 = cf2[m-1][c] - if r > 0 { cf2[r-1][c] } else { 0 };
        let down5 = cf5[m-1][c] - if r > 0 { cf5[r-1][c] } else { 0 };

        // 4 L-shapes, subtract cell once (counted in both row and col)
        for &(row2, row5, col2, col5) in &[
          (left2, left5, up2, up5),
          (right2, right5, up2, up5),
          (left2, left5, down2, down5),
          (right2, right5, down2, down5),
        ] {
          let total2 = row2 + col2 - cell_f2;
          let total5 = row5 + col5 - cell_f5;
          ans = ans.max(total2.min(total5));
        }
      }
    }
    ans
  }
}