2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution
In this guide, you will get 2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution with the best time and space complexity. The solution to Maximum Trailing Zeros in a Cornered Path problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Trailing Zeros in a Cornered Path
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.
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
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution in C++
class Solution {
public:
int maxTrailingZeros(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
// leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
// topPrefix2[i][j] := the number of 2 in grid[0..i][j]
// topPrefix5[i][j] := the number of 5 in grid[0..i][j]
vector<vector<int>> leftPrefix2(m, vector<int>(n));
vector<vector<int>> leftPrefix5(m, vector<int>(n));
vector<vector<int>> topPrefix2(m, vector<int>(n));
vector<vector<int>> topPrefix5(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
leftPrefix2[i][j] = getCount(grid[i][j], 2);
leftPrefix5[i][j] = getCount(grid[i][j], 5);
if (j > 0) {
leftPrefix2[i][j] += leftPrefix2[i][j - 1];
leftPrefix5[i][j] += leftPrefix5[i][j - 1];
}
}
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i) {
topPrefix2[i][j] = getCount(grid[i][j], 2);
topPrefix5[i][j] = getCount(grid[i][j], 5);
if (i > 0) {
topPrefix2[i][j] += topPrefix2[i - 1][j];
topPrefix5[i][j] += topPrefix5[i - 1][j];
}
}
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
const int curr2 = getCount(grid[i][j], 2);
const int curr5 = getCount(grid[i][j], 5);
const int l2 = leftPrefix2[i][j];
const int l5 = leftPrefix5[i][j];
const int r2 = leftPrefix2[i][n - 1] - (j ? leftPrefix2[i][j - 1] : 0);
const int r5 = leftPrefix5[i][n - 1] - (j ? leftPrefix5[i][j - 1] : 0);
const int t2 = topPrefix2[i][j];
const int t5 = topPrefix5[i][j];
const int d2 = topPrefix2[m - 1][j] - (i ? topPrefix2[i - 1][j] : 0);
const int d5 = topPrefix5[m - 1][j] - (i ? topPrefix5[i - 1][j] : 0);
ans = max({ans, min(l2 + t2 - curr2, l5 + t5 - curr5),
min(r2 + t2 - curr2, r5 + t5 - curr5),
min(l2 + d2 - curr2, l5 + d5 - curr5),
min(r2 + d2 - curr2, r5 + d5 - curr5)});
}
return ans;
}
private:
int getCount(int num, int factor) {
int count = 0;
while (num % factor == 0) {
num /= factor;
++count;
}
return count;
}
}; /* code provided by PROGIEZ */
2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution in Java
class Solution {
public int maxTrailingZeros(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
// leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
// leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
// topPrefix2[i][j] := the number of 2 in grid[0..i][j]
// topPrefix5[i][j] := the number of 5 in grid[0..i][j]
int[][] leftPrefix2 = new int[m][n];
int[][] leftPrefix5 = new int[m][n];
int[][] topPrefix2 = new int[m][n];
int[][] topPrefix5 = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
leftPrefix2[i][j] = getCount(grid[i][j], 2);
leftPrefix5[i][j] = getCount(grid[i][j], 5);
if (j > 0) {
leftPrefix2[i][j] += leftPrefix2[i][j - 1];
leftPrefix5[i][j] += leftPrefix5[i][j - 1];
}
}
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i) {
topPrefix2[i][j] = getCount(grid[i][j], 2);
topPrefix5[i][j] = getCount(grid[i][j], 5);
if (i > 0) {
topPrefix2[i][j] += topPrefix2[i - 1][j];
topPrefix5[i][j] += topPrefix5[i - 1][j];
}
}
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
final int curr2 = getCount(grid[i][j], 2);
final int curr5 = getCount(grid[i][j], 5);
final int l2 = leftPrefix2[i][j];
final int l5 = leftPrefix5[i][j];
final int r2 = leftPrefix2[i][n - 1] - (j > 0 ? leftPrefix2[i][j - 1] : 0);
final int r5 = leftPrefix5[i][n - 1] - (j > 0 ? leftPrefix5[i][j - 1] : 0);
final int t2 = topPrefix2[i][j];
final int t5 = topPrefix5[i][j];
final int d2 = topPrefix2[m - 1][j] - (i > 0 ? topPrefix2[i - 1][j] : 0);
final int d5 = topPrefix5[m - 1][j] - (i > 0 ? topPrefix5[i - 1][j] : 0);
ans = Math.max(ans, Math.max(Math.max(Math.min(l2 + t2 - curr2, l5 + t5 - curr5),
Math.min(r2 + t2 - curr2, r5 + t5 - curr5)),
Math.max(Math.min(l2 + d2 - curr2, l5 + d5 - curr5),
Math.min(r2 + d2 - curr2, r5 + d5 - curr5))));
}
return ans;
}
private int getCount(int num, int factor) {
int count = 0;
while (num % factor == 0) {
num /= factor;
++count;
}
return count;
}
} // code provided by PROGIEZ
2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution in Python
class Solution:
def maxTrailingZeros(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
# leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
# leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
# topPrefix2[i][j] := the number of 2 in grid[0..i][j]
# topPrefix5[i][j] := the number of 5 in grid[0..i][j]
leftPrefix2 = [[0] * n for _ in range(m)]
leftPrefix5 = [[0] * n for _ in range(m)]
topPrefix2 = [[0] * n for _ in range(m)]
topPrefix5 = [[0] * n for _ in range(m)]
def getCount(num: int, factor: int) -> int:
count = 0
while num % factor == 0:
num //= factor
count += 1
return count
for i in range(m):
for j in range(n):
leftPrefix2[i][j] = getCount(grid[i][j], 2)
leftPrefix5[i][j] = getCount(grid[i][j], 5)
if j:
leftPrefix2[i][j] += leftPrefix2[i][j - 1]
leftPrefix5[i][j] += leftPrefix5[i][j - 1]
for j in range(n):
for i in range(m):
topPrefix2[i][j] = getCount(grid[i][j], 2)
topPrefix5[i][j] = getCount(grid[i][j], 5)
if i:
topPrefix2[i][j] += topPrefix2[i - 1][j]
topPrefix5[i][j] += topPrefix5[i - 1][j]
ans = 0
for i in range(m):
for j in range(n):
curr2 = getCount(grid[i][j], 2)
curr5 = getCount(grid[i][j], 5)
l2 = leftPrefix2[i][j]
l5 = leftPrefix5[i][j]
r2 = leftPrefix2[i][n - 1] - (0 if j == 0 else leftPrefix2[i][j - 1])
r5 = leftPrefix5[i][n - 1] - (0 if j == 0 else leftPrefix5[i][j - 1])
t2 = topPrefix2[i][j]
t5 = topPrefix5[i][j]
d2 = topPrefix2[m - 1][j] - (0 if i == 0 else topPrefix2[i - 1][j])
d5 = topPrefix5[m - 1][j] - (0 if i == 0 else topPrefix5[i - 1][j])
ans = max(ans,
min(l2 + t2 - curr2, l5 + t5 - curr5),
min(r2 + t2 - curr2, r5 + t5 - curr5),
min(l2 + d2 - curr2, l5 + d5 - curr5),
min(r2 + d2 - curr2, r5 + d5 - curr5))
return ans # code by PROGIEZ
