Scale Engineer

Maximum Trailing Zeros in a Cornered Path

Med
#2045Time: O(m^2 * n^2). There are `O(m*n)` choices for the corner cell. For each corner, there are `O(m*n)` choices for the endpoints of the two arms. Calculating factors for each path takes `O(1)` with prefix sums.Space: O(m * n) to store the factor grid and the prefix sum grids.
Patterns
Prefix Sum
Data structures
ArrayMatrix

Prompt

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:

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.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible cornered path. It iterates through each cell (i, j) as a potential corner. For each corner, it then considers all possible start and end points for the vertical and horizontal segments that form the 'L' shape. To avoid re-calculating the product and factors for each path from scratch, it pre-computes prefix sums of the factor counts (2s and 5s) for every row and column. This allows for O(1) lookup of the total factors for any given segment. Finally, it compares the results from all possible paths to find the maximum number of trailing zeros.

Algorithm

  • Define a helper function countFactors(n) that computes the number of factors of 2 and 5 in an integer n and returns them as a pair (c2, c5).
  • Create a factorsGrid of size m x n by applying countFactors to each element of the input grid.
  • Create two prefix sum grids, prefixRow and prefixCol, both of size m x n. Each cell will store a pair of factor counts.
    • prefixRow[i][j] will store the sum of factors for cells (i, 0) through (i, j).
    • prefixCol[i][j] will store the sum of factors for cells (0, j) through (i, j).
  • Initialize a variable maxZeros to 0.
  • Iterate through every cell (i, j) in the grid, considering it as a potential corner for an L-shaped path.
  • For each corner (i, j), iterate through all possible starting points for the vertical arm (k from 0 to m-1) and horizontal arm (l from 0 to n-1).
  • For each combination of (i, j, k, l), determine the path segments (e.g., vertical from k to i, horizontal from l to j).
  • Use the pre-computed prefix sum grids to calculate the total factors (total_c2, total_c5) for the formed path in O(1) time. Remember to subtract the factors of the corner cell (i, j) once as it's included in both row and column sums.
  • Update maxZeros = max(maxZeros, min(total_c2, total_c5)).
  • Separately, handle straight paths by iterating through all possible start and end indices for every row and column, calculating their zeros using prefix sums, and updating maxZeros.
  • Return maxZeros.

Walkthrough

The core idea is to exhaustively explore all valid paths. A cornered path is defined by its corner cell and the extents of its two arms (one vertical, one horizontal).

  1. Factor Pre-computation: First, we realize that the number of trailing zeros is determined by min(count_of_2s, count_of_5s) in the prime factorization of the path's product. We pre-process the grid to create a factorsGrid where each cell (i, j) stores the counts of factors 2 and 5 for grid[i][j].

  2. Prefix Sums: To quickly calculate the total factors for any path segment, we use prefix sums. We build two grids:

    • prefixRow[i][j]: Sum of factors from (i, 0) to (i, j).
    • prefixCol[i][j]: Sum of factors from (0, j) to (i, j). This allows us to find the factors for any sub-segment like (i, c1) to (i, c2) in O(1) time by subtracting prefix sums.

  3. Path Iteration: The main loop iterates through every cell (i, j) as the corner. For each corner, it tries all four L-shape orientations (e.g., Top-Left, where the path comes from above and turns left). For a Top-Left L-shape at (i, j), we would iterate through all possible vertical segments (k, j) to (i, j) (where 0 <= k <= i) and all horizontal segments (i, l) to (i, j) (where 0 <= l <= j).

  4. Calculate and Update: For each of these (i+1) * (j+1) paths for a Top-Left corner at (i,j), we use the prefix sum grids to find the total factor counts, calculate the number of zeros, and update a global maximum. This process is repeated for all four orientations and all possible corners.

  5. Straight Paths: A similar exhaustive check is required for straight paths (paths with no turns), which involves checking every possible sub-array of every row and column.

// This is a conceptual representation. A full implementation would be very long and inefficient.class Solution {    public int maxTrailingZeros(int[][] grid) {        int m = grid.length;        int n = grid[0].length;         int[][][] factorsGrid = new int[m][n][2];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                factorsGrid[i][j] = countFactors(grid[i][j]);            }        }         int[][][] prefixRow = new int[m][n][2];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                prefixRow[i][j][0] = factorsGrid[i][j][0] + (j > 0 ? prefixRow[i][j - 1][0] : 0);                prefixRow[i][j][1] = factorsGrid[i][j][1] + (j > 0 ? prefixRow[i][j - 1][1] : 0);            }        }         int[][][] prefixCol = new int[m][n][2];        for (int j = 0; j < n; j++) {            for (int i = 0; i < m; i++) {                prefixCol[i][j][0] = factorsGrid[i][j][0] + (i > 0 ? prefixCol[i - 1][j][0] : 0);                prefixCol[i][j][1] = factorsGrid[i][j][1] + (i > 0 ? prefixCol[i - 1][j][1] : 0);            }        }         int maxZeros = 0;         // Incomplete: Iterating all paths is too complex to write out fully        // and would be O(m^2 * n^2).        // For each corner (i, j):        //   For each vertical start k:        //     For each horizontal start l:        //       Calculate path factors using prefix sums.        //       Update maxZeros.         // Also handle straight paths...         return maxZeros; // Placeholder for the result    }     private int[] countFactors(int num) {        int count2 = 0;        int count5 = 0;        while (num > 0 && num % 2 == 0) {            count2++;            num /= 2;        }        while (num > 0 && num % 5 == 0) {            count5++;            num /= 5;        }        return new int[]{count2, count5};    }}

Complexity

Time

O(m^2 * n^2). There are `O(m*n)` choices for the corner cell. For each corner, there are `O(m*n)` choices for the endpoints of the two arms. Calculating factors for each path takes `O(1)` with prefix sums.

Space

O(m * n) to store the factor grid and the prefix sum grids.

Trade-offs

Pros

  • It is a direct translation of the problem definition, making it relatively easy to conceptualize.

  • It guarantees finding the correct answer by checking every single possibility.

Cons

  • The time complexity of O(m^2 * n^2) is too high for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem