Problem Description

You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.

A cornered path is a path through the grid that follows these rules:

• The path consists of adjacent cells
• The path can have at most one turn (it can also have no turns)
• Before the turn (if there is one), the path moves exclusively in one direction - either horizontally (left/right) or vertically (up/down)
• After the turn, the path must move exclusively in the alternate direction - if it was moving horizontally before, it must move vertically after, and vice versa
• The path cannot revisit any cell

The product of a path is calculated by multiplying all the values in the cells along that path.

The trailing zeros of a number are the consecutive zeros at the end of the number. For example, 1200 has 2 trailing zeros, and 5040 has 1 trailing zero.

Your task is to find the maximum number of trailing zeros that can be obtained from the product of any valid cornered path in the grid.

Key Points:

• Horizontal movement means moving left or right
• Vertical movement means moving up or down
• A cornered path can be a straight line (0 turns) or have exactly 1 turn
• You want to maximize the trailing zeros in the product, not the product itself

For example, if a path covers cells with values [2, 5, 10], the product would be 2 × 5 × 10 = 100, which has 2 trailing zeros.

Intuition

To understand how to maximize trailing zeros, we need to recognize that trailing zeros come from factors of 10, and 10 = 2 × 5. Therefore, the number of trailing zeros in a product equals min(count of 2s, count of 5s) in the prime factorization.

For example, if we have factors containing three 2s and two 5s, we can form two 10s, giving us 2 trailing zeros.

Now, let's think about the cornered path structure. A cornered path has at most one turn, which means it can only have these shapes:

• Straight line (no turn): horizontal or vertical
• L-shaped path (one turn): starts horizontally then turns vertically, or starts vertically then turns horizontally

The key insight is that any cornered path that maximizes the product should start from a boundary and end at another boundary. Why? Because we want to include as many cells as possible to accumulate more factors of 2 and 5.

This leads us to realize that for any cell (i, j) that serves as a turning point, there are exactly 4 possible L-shaped paths:

1. Start from the left boundary, move right to (i, j), then turn up to the top boundary
2. Start from the left boundary, move right to (i, j), then turn down to the bottom boundary
3. Start from the right boundary, move left to (i, j), then turn up to the top boundary
4. Start from the right boundary, move left to (i, j), then turn down to the bottom boundary

To efficiently calculate the factors of 2 and 5 for any path segment, we can use prefix sums. We precompute:

• Row-wise prefix sums for counts of 2 and 5 (to handle horizontal segments)
• Column-wise prefix sums for counts of 2 and 5 (to handle vertical segments)

With these prefix sums, for any turning point (i, j), we can quickly calculate the total count of 2s and 5s for each of the 4 possible L-shaped paths, take the minimum of the two counts to get trailing zeros, and track the maximum across all possibilities.

Learn more about Prefix Sum patterns.

Solution Approach

Based on our intuition, let's implement the solution step by step:

Step 1: Initialize Prefix Sum Arrays

We create four 2D arrays with dimensions (m+1) × (n+1) to store prefix sums:

• r2[i][j]: count of factor 2 from column 1 to column j in row i
• r5[i][j]: count of factor 5 from column 1 to column j in row i
• c2[i][j]: count of factor 2 from row 1 to row i in column j
• c5[i][j]: count of factor 5 from row 1 to row i in column j

We use 1-indexed arrays (with size m+1 and n+1) to simplify calculations and avoid boundary checks.

Step 2: Build Prefix Sums

For each cell grid[i-1][j-1] (using 1-based indexing in our arrays):

1. Count the factors of 2 and 5 in the current value:

   while x % 2 == 0:
       x //= 2
       s2 += 1
   while x % 5 == 0:
       x //= 5
       s5 += 1

2. Update the prefix sums:

   • Row prefix: r2[i][j] = r2[i][j-1] + s2 and r5[i][j] = r5[i][j-1] + s5
   • Column prefix: c2[i][j] = c2[i-1][j] + s2 and c5[i][j] = c5[i-1][j] + s5

Step 3: Enumerate Turning Points

For each cell (i, j) as a potential turning point, calculate the trailing zeros for all 4 possible L-shaped paths:

1. Path a: Left boundary → (i,j) → Top boundary

   • Horizontal segment: r2[i][j] and r5[i][j] (from column 1 to j in row i)
   • Vertical segment: c2[i-1][j] and c5[i-1][j] (from row 1 to i-1 in column j)
   • Total: min(r2[i][j] + c2[i-1][j], r5[i][j] + c5[i-1][j])

2. Path b: Left boundary → (i,j) → Bottom boundary

   • Horizontal segment: r2[i][j] and r5[i][j]
   • Vertical segment: c2[m][j] - c2[i][j] and c5[m][j] - c5[i][j] (from row i+1 to m)
   • Total: min(r2[i][j] + c2[m][j] - c2[i][j], r5[i][j] + c5[m][j] - c5[i][j])

3. Path c: Right boundary → (i,j) → Top boundary

   • Horizontal segment: r2[i][n] - r2[i][j] and r5[i][n] - r5[i][j] (from column j+1 to n)
   • Vertical segment: c2[i][j] and c5[i][j] (from row 1 to i)
   • Total: min(r2[i][n] - r2[i][j] + c2[i][j], r5[i][n] - r5[i][j] + c5[i][j])

4. Path d: Right boundary → (i,j) → Bottom boundary

   • Horizontal segment: r2[i][n] - r2[i][j-1] and r5[i][n] - r5[i][j-1] (from column j to n, inclusive)
   • Vertical segment: c2[m][j] - c2[i][j] and c5[m][j] - c5[i][j]
   • Total: 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])

Note that for path d, we use r2[i][j-1] instead of r2[i][j] to include cell (i,j) in the horizontal segment.

Step 4: Track Maximum

For each turning point, we take the maximum of all four path values and update our answer. The final answer is the maximum trailing zeros across all possible cornered paths in the grid.

The time complexity is O(m × n) for building prefix sums and enumerating turning points, with O(m × n) space for the prefix sum arrays.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 3×3 grid:

grid = [[4,  5,  2],
        [10, 3,  6],
        [2,  25, 8]]

Step 1: Count factors of 2 and 5 for each cell

First, let's break down each cell into its factors of 2 and 5:

• 4 = 2² → 2 twos, 0 fives
• 5 = 5¹ → 0 twos, 1 five
• 2 = 2¹ → 1 two, 0 fives
• 10 = 2¹×5¹ → 1 two, 1 five
• 3 = 3¹ → 0 twos, 0 fives
• 6 = 2¹×3 → 1 two, 0 fives
• 2 = 2¹ → 1 two, 0 fives
• 25 = 5² → 0 twos, 2 fives
• 8 = 2³ → 3 twos, 0 fives

Step 2: Build prefix sum arrays

Row prefix sums for factors of 2 (r2):

r2 = [[0, 0, 0, 0],
      [0, 2, 2, 3],    // row 1: accumulate 2, 0, 1
      [0, 1, 1, 2],    // row 2: accumulate 1, 0, 1
      [0, 1, 1, 4]]    // row 3: accumulate 1, 0, 3

Row prefix sums for factors of 5 (r5):

r5 = [[0, 0, 0, 0],
      [0, 0, 1, 1],    // row 1: accumulate 0, 1, 0
      [0, 1, 1, 1],    // row 2: accumulate 1, 0, 0
      [0, 0, 2, 2]]    // row 3: accumulate 0, 2, 0

Column prefix sums for factors of 2 (c2):

c2 = [[0, 0, 0, 0],
      [0, 2, 0, 1],    // col accumulations
      [0, 3, 0, 2],
      [0, 4, 0, 5]]

Column prefix sums for factors of 5 (c5):

c5 = [[0, 0, 0, 0],
      [0, 0, 1, 0],    // col accumulations
      [0, 1, 1, 0],
      [0, 1, 3, 0]]

Step 3: Calculate L-shaped paths for turning point (2,2)

Let's examine cell (2,2) with value 3 as a turning point. Using 1-based indexing in our prefix arrays, this is position (2,2).

Path a: Left boundary → (2,2) → Top boundary

• Horizontal: cells [10, 3] give r2[2][2] = 1 and r5[2][2] = 1
• Vertical: cell [5] gives c2[1][2] = 0 and c5[1][2] = 1
• Total factors: 1+0 = 1 two, 1+1 = 2 fives
• Trailing zeros: min(1, 2) = 1

Path b: Left boundary → (2,2) → Bottom boundary

• Horizontal: cells [10, 3] give r2[2][2] = 1 and r5[2][2] = 1
• Vertical: cell [25] gives c2[3][2] - c2[2][2] = 0-0 = 0 and c5[3][2] - c5[2][2] = 3-1 = 2
• Total factors: 1+0 = 1 two, 1+2 = 3 fives
• Trailing zeros: min(1, 3) = 1

Path c: Right boundary → (2,2) → Top boundary

• Horizontal: cell [6] gives r2[2][3] - r2[2][2] = 2-1 = 1 and r5[2][3] - r5[2][2] = 1-1 = 0
• Vertical: cells [5, 3] give c2[2][2] = 0 and c5[2][2] = 1
• Total factors: 1+0 = 1 two, 0+1 = 1 five
• Trailing zeros: min(1, 1) = 1

Path d: Right boundary → (2,2) → Bottom boundary

• Horizontal: cells [3, 6] give r2[2][3] - r2[2][1] = 2-1 = 1 and r5[2][3] - r5[2][1] = 1-1 = 0
• Vertical: cell [25] gives c2[3][2] - c2[2][2] = 0-0 = 0 and c5[3][2] - c5[2][2] = 3-1 = 2
• Total factors: 1+0 = 1 two, 0+2 = 2 fives
• Trailing zeros: min(1, 2) = 1

Step 4: Check other turning points

Let's check one more promising turning point at (1,2) with value 5:

Path b: Left boundary → (1,2) → Bottom boundary

• Horizontal: cells [4, 5] give r2[1][2] = 2 and r5[1][2] = 1
• Vertical: cells [3, 25] give c2[3][2] - c2[1][2] = 0-0 = 0 and c5[3][2] - c5[1][2] = 3-1 = 2
• Total factors: 2+0 = 2 twos, 1+2 = 3 fives
• Trailing zeros: min(2, 3) = 2

This gives us 2 trailing zeros! After checking all possible turning points and their L-shaped paths, the maximum trailing zeros would be 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main phases:

1. Preprocessing phase: The first nested loop iterates through all m × n cells of the grid. For each cell, it counts the factors of 2 and 5, which takes O(log(max_value)) time per cell. Since the maximum value in the grid is bounded, this is effectively O(1) per cell. The loop also updates the prefix sum arrays r2, c2, r5, and c5 in O(1) time per cell. Therefore, this phase takes O(m × n) time.

2. Computation phase: The second nested loop again iterates through all m × n cells. For each cell (i, j), it computes four possible L-shaped paths using the precomputed prefix sums. Each computation involves constant-time arithmetic operations using the prefix sum arrays. Therefore, this phase also takes O(m × n) time.

The total time complexity is O(m × n) + O(m × n) = O(m × n).

Space Complexity: O(m × n)

The algorithm uses four 2D arrays (r2, c2, r5, c5), each of size (m + 1) × (n + 1). Each array stores prefix sums for either factor 2 or factor 5, either row-wise or column-wise. The space required is 4 × (m + 1) × (n + 1) = O(m × n).

The additional variables (ans, a, b, c, d, s2, s5) use O(1) space.

Therefore, the total space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Path Inclusion at Turning Point

One of the most common mistakes is incorrectly including or excluding the turning point cell when calculating the path segments. This leads to either double-counting the turning point or missing it entirely.

The Problem: When calculating L-shaped paths, the turning point cell (i,j) should be counted exactly once. However, it's easy to make mistakes like:

• Double-counting: Including it in both horizontal and vertical segments
• Missing it: Excluding it from both segments
• Inconsistent handling: Different inclusion logic for different path types

Example of the Bug:

# Incorrect: Path 3 - Right from (i,j) then up
# This excludes the turning point from both segments!
path3_zeros = min(
    row_twos[i][cols] - row_twos[i][j],  # Excludes column j
    col_twos[i-1][j]                      # Excludes row i
)

The Solution: The turning point should be included in exactly one segment. The correct approach:

# Correct: Include turning point in vertical segment
path3_zeros = min(
    row_twos[i][cols] - row_twos[i][j] + col_twos[i][j],
    row_fives[i][cols] - row_fives[i][j] + col_fives[i][j]
)
# Here col_twos[i][j] includes the turning point

2. Confusion with Prefix Sum Boundaries

Another pitfall is misunderstanding what the prefix sum values represent, especially with 1-based indexing.

The Problem: With 1-based indexing:

• row_twos[i][j] represents the sum from column 1 to column j in row i
• col_twos[i][j] represents the sum from row 1 to row i in column j

It's easy to forget whether boundaries are inclusive or exclusive.

Example of the Bug:

# Incorrect: Trying to get sum from column j+1 to n
path3_horizontal = row_twos[i][cols] - row_twos[i][j+1]  # Wrong!

The Solution: Remember that to get the sum from column j+1 to n, you subtract the prefix sum up to column j:

# Correct: Sum from column j+1 to n
path3_horizontal = row_twos[i][cols] - row_twos[i][j]

3. Not Considering Straight Line Paths

The problem states paths can have "at most one turn," meaning straight lines (0 turns) are also valid.

The Problem: The code only considers L-shaped paths with exactly one turn, missing potentially better straight-line paths.

The Solution: Add checks for straight horizontal and vertical paths:

# Add straight line paths
for i in range(1, rows + 1):
    # Horizontal line across entire row
    horizontal_zeros = min(row_twos[i][cols], row_fives[i][cols])
    max_trailing_zeros = max(max_trailing_zeros, horizontal_zeros)

for j in range(1, cols + 1):
    # Vertical line down entire column
    vertical_zeros = min(col_twos[rows][j], col_fives[rows][j])
    max_trailing_zeros = max(max_trailing_zeros, vertical_zeros)

4. Integer Overflow in Factor Counting

While less common in Python, continuously dividing by 2 or 5 without bounds checking could theoretically cause issues with very large numbers.

The Solution: Add a reasonable upper bound or use more efficient factor counting:

def count_factor(n, factor):
    count = 0
    while n > 0 and n % factor == 0:
        n //= factor
        count += 1
    return count