LeetCode Solutions Blog

Maximum Trailing Zeros in a Cornered Path

Number: 2363

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n grid of positive integers, a cornered path is defined as a continuous set of cells that moves in one direction (either horizontally or vertically) and then optionally makes one turn to move in the alternate direction. The product of a path is the multiplication of all numbers in the path. The goal is to find a cornered path whose product has the maximum number of trailing zeros. Trailing zeros are determined by the minimum count of prime factors 2 and 5 in the product.

Key Insights

The number of trailing zeros in a product equals the minimum of the total exponents of 2 and 5 in its factorization.
For each grid cell, precompute the count of factors 2 and 5.
Precompute prefix sums for counts in all four directions (left-to-right, right-to-left, top-to-bottom, and bottom-to-top) to quickly query the sum of counts along any segment.
Consider each cell as the potential turning point, and then combine prefix sum values in four different L-shaped paths: up+left, up+right, down+left, and down+right.
Adjust for the overlap at the turning cell (since it gets added twice) by subtracting its own factor counts once.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) (for storing the factor counts and prefix sums)

Solution

We first preprocess each cell by computing its factor counts for 2 and 5. Then, we build prefix sum matrices for rows and columns separately such that we can quickly sum up counts along any horizontal or vertical segment.

For every cell in the grid considered as a turning point, we compute the total factor counts on the four candidate L-shaped paths:

Going left then up.
Going left then down.
Going right then up.
Going right then down.

For each candidate, we add the horizontal and vertical segments’ counts (retrieved via the prefix sums) and subtract the turning cell’s double count. We then take the minimum of the two factor counts (2s and 5s) to get the trailing zero count for that path. The maximum trailing zero count across all cells and candidate paths is our answer.

Code Solutions

# Python solution with detailed comments
class Solution:
    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # Helper function to count factors of 2 and 5 for a given number.
        def count_factors(x):
            count2, count5 = 0, 0
            while x % 2 == 0:
                count2 += 1
                x //= 2
            while x % 5 == 0:
                count5 += 1
                x //= 5
            return count2, count5

        # Precompute the factor counts for each cell.
        cnt2 = [[0]*n for _ in range(m)]
        cnt5 = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                cnt2[i][j], cnt5[i][j] = count_factors(grid[i][j])
                
        # Build prefix sum arrays for 2s and 5s in four directions.
        # Left prefix sum: for each row, cumulative counts from left to right.
        left2 = [[0]*n for _ in range(m)]
        left5 = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if j == 0:
                    left2[i][j] = cnt2[i][j]
                    left5[i][j] = cnt5[i][j]
                else:
                    left2[i][j] = left2[i][j-1] + cnt2[i][j]
                    left5[i][j] = left5[i][j-1] + cnt5[i][j]
                    
        # Right prefix sum: cumulative counts from right to left.
        right2 = [[0]*n for _ in range(m)]
        right5 = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n-1, -1, -1):
                if j == n-1:
                    right2[i][j] = cnt2[i][j]
                    right5[i][j] = cnt5[i][j]
                else:
                    right2[i][j] = right2[i][j+1] + cnt2[i][j]
                    right5[i][j] = right5[i][j+1] + cnt5[i][j]
                    
        # Top prefix sum: for each column, cumulative counts from top to bottom.
        top2 = [[0]*n for _ in range(m)]
        top5 = [[0]*n for _ in range(m)]
        for j in range(n):
            for i in range(m):
                if i == 0:
                    top2[i][j] = cnt2[i][j]
                    top5[i][j] = cnt5[i][j]
                else:
                    top2[i][j] = top2[i-1][j] + cnt2[i][j]
                    top5[i][j] = top5[i-1][j] + cnt5[i][j]
        
        # Bottom prefix sum: cumulative counts from bottom to top.
        bottom2 = [[0]*n for _ in range(m)]
        bottom5 = [[0]*n for _ in range(m)]
        for j in range(n):
            for i in range(m-1, -1, -1):
                if i == m-1:
                    bottom2[i][j] = cnt2[i][j]
                    bottom5[i][j] = cnt5[i][j]
                else:
                    bottom2[i][j] = bottom2[i+1][j] + cnt2[i][j]
                    bottom5[i][j] = bottom5[i+1][j] + cnt5[i][j]
        
        maxZeros = 0
        
        # For each cell, consider it as the turning point and evaluate 4 cornered paths.
        for i in range(m):
            for j in range(n):
                # Retrieve counts for each direction.
                # left: from start of row to j.
                totalLeft2 = left2[i][j]
                totalLeft5 = left5[i][j]
                # right: from j to end of row.
                totalRight2 = right2[i][j]
                totalRight5 = right5[i][j]
                # top: from start of column to i.
                totalTop2 = top2[i][j]
                totalTop5 = top5[i][j]
                # bottom: from i to end of column.
                totalBottom2 = bottom2[i][j]
                totalBottom5 = bottom5[i][j]
                
                # For the turning point, we add one directional segment and one vertical.
                # Note: When combining two segments both include the turning cell, subtract its count once.
                
                # 1. Left then Top.
                comb2 = totalLeft2 + totalTop2 - cnt2[i][j]
                comb5 = totalLeft5 + totalTop5 - cnt5[i][j]
                maxZeros = max(maxZeros, min(comb2, comb5))
                
                # 2. Left then Bottom.
                comb2 = totalLeft2 + totalBottom2 - cnt2[i][j]
                comb5 = totalLeft5 + totalBottom5 - cnt5[i][j]
                maxZeros = max(maxZeros, min(comb2, comb5))
                
                # 3. Right then Top.
                comb2 = totalRight2 + totalTop2 - cnt2[i][j]
                comb5 = totalRight5 + totalTop5 - cnt5[i][j]
                maxZeros = max(maxZeros, min(comb2, comb5))
                
                # 4. Right then Bottom.
                comb2 = totalRight2 + totalBottom2 - cnt2[i][j]
                comb5 = totalRight5 + totalBottom5 - cnt5[i][j]
                maxZeros = max(maxZeros, min(comb2, comb5))
        
        return maxZeros