How hard is LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?

LeetCode 2245. Maximum Trailing Zeros in a Cornered Path is rated Medium on LeetCode.

What is the time complexity of LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?

The Python solution on this page uses O(m \times n), where m and n are the number of rows and columns of the `grid` array, respectively auxiliary space.

What topics does LeetCode 2245. Maximum Trailing Zeros in a Cornered Path cover?

LeetCode 2245. Maximum Trailing Zeros in a Cornered Path is tagged Array, Matrix and Prefix Sum on LeetCode.

Maximum Trailing Zeros in a Cornered Path — LeetCode 2245 Python Solution

MediumArrayMatrixPrefix Sum

Problem: #2245
Pattern: Prefix Sum
Reading time: 6 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n), where m and n are the number of rows and columns of the `grid` array, respectively auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2245. Maximum Trailing Zeros in a Cornered Path is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?: LeetCode 2245. Maximum Trailing Zeros in a Cornered Path is rated Medium on LeetCode.
What is the time complexity of LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 2245. Maximum Trailing Zeros in a Cornered Path?: The Python solution on this page uses O(m \times n), where m and n are the number of rows and columns of the `grid` array, respectively auxiliary space.
What topics does LeetCode 2245. Maximum Trailing Zeros in a Cornered Path cover?: LeetCode 2245. Maximum Trailing Zeros in a Cornered Path is tagged Array, Matrix and Prefix Sum on LeetCode.