Leetcode 2245: Maximum Trailing Zeros in a Cornered Path
You are given a 2D integer array called
grid of size m x n, where each cell contains a positive integer. A cornered path is a specific path in the grid with at most one directional change. The path must move either horizontally or vertically up to a single turn and then continue in the alternate direction. The product of a path is the product of all integers in that path. The task is to find the maximum number of trailing zeros in the product of a cornered path.Problem
Approach
Steps
Complexity
Input: The input consists of a 2D integer array `grid` of size `m x n`, where each element is a positive integer.
Example: grid = [[5, 2, 8], [3, 4, 7], [9, 6, 1]]
Constraints:
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= grid[i][j] <= 1000
Output: Return an integer representing the maximum number of trailing zeros in the product of any cornered path in the grid.
Example: Output: 2
Constraints:
Goal: To calculate the maximum number of trailing zeros in the product of a valid cornered path in the grid.
Steps:
• Traverse the grid to calculate the number of factors of 2 and 5 for each cell.
• Precompute prefix sums for horizontal and vertical movements in the grid.
• For each cell, compute possible cornered paths in all four directions and calculate the product.
• Count trailing zeros by finding the minimum of the factors of 2 and 5 in the product.
Goal: The grid and operations are subject to the following constraints:
Steps:
• The grid size is limited to a maximum of 10^5 elements.
• All grid values are between 1 and 1000.
• Only paths with at most one directional change are considered.
Assumptions:
• Grid dimensions are positive integers.
• The product of any path will not overflow standard data types.
• Input: grid = [[10, 5, 2], [2, 20, 4], [8, 7, 6]]
• Explanation: One possible cornered path is [10 -> 5 -> 20 -> 4], which produces a product of 4000, with 3 trailing zeros.
• Input: grid = [[3, 7], [8, 9]]
• Explanation: All paths produce products without trailing zeros.
Approach: The solution involves factorizing the grid values and using precomputed prefix sums to efficiently calculate the factors of 2 and 5 for potential paths.
Observations:
• Trailing zeros in a number are determined by the minimum of the number of factors of 2 and 5 in its product.
• Cornered paths allow at most one change in direction.
• Factorize each cell and compute cumulative sums for each direction to evaluate paths efficiently.
Steps:
• Precompute the number of factors of 2 and 5 for each cell in the grid.
• Use prefix sums for horizontal and vertical movements to quickly calculate the cumulative factors for any segment.
• Iterate over all grid cells and evaluate cornered paths originating from the cell in all four possible directions.
• Calculate the trailing zeros for each path and update the maximum.
Empty Inputs:
• The grid is guaranteed to be non-empty.
Large Inputs:
• Handle grids with dimensions close to 10^5 efficiently.
Special Values:
• Grid cells with value 1 contribute no factors of 2 or 5.
• Cells with large multiples of 10 might have high trailing zeros.
Constraints:
• Grid values must remain within the range [1, 1000].
int fact(int i, int j) {
return i % j ? 0 : 1 + fact(i/j, j);
}
int maxTrailingZeros(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<array<int, 2>>> h(m, vector<array<int, 2>>(n + 1)), v(m+1, vector<array<int, 2>>(n));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int t = grid[i][j];
array<int, 2> node = { fact(t, 2), fact(t, 5) };
h[i][j + 1] = h[i][j] + node;
v[i + 1][j] = v[i][j] + node;
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
array<int, 2> h1 = h[i][j],
h2 = h[i][n] - h[i][j+1],
v1 = v[i+1][j],
v2 = v[m][j] - v[i][j];
res = max({res, pairs(v1+h1), pairs(v1+h2), pairs(v2+h1), pairs(v2+h2)});
}
}
return res;
}
1 : Function Definition
int fact(int i, int j) {
The 'fact' function is defined here, which computes the number of times 'j' divides 'i'. It is used to calculate factors of 2 and 5 for trailing zero calculation.
2 : Base Case
return i % j ? 0 : 1 + fact(i/j, j);
This is a recursive base case for the 'fact' function. If 'i' is divisible by 'j', it keeps dividing 'i' by 'j', adding 1 each time.
3 : Main Function Definition
int maxTrailingZeros(vector<vector<int>>& grid) {
This defines the 'maxTrailingZeros' function, which aims to calculate the maximum number of trailing zeros from any submatrix in a given 2D grid of integers.
4 : Variable Initialization
int m = grid.size(), n = grid[0].size(), res = 0;
Initializes the variables: 'm' is the number of rows in the grid, 'n' is the number of columns, and 'res' stores the result for the maximum number of trailing zeros.
5 : 2D Array Initialization
vector<vector<array<int, 2>>> h(m, vector<array<int, 2>>(n + 1)), v(m+1, vector<array<int, 2>>(n));
Two 2D arrays 'h' and 'v' are initialized to store the cumulative factors of 2 and 5 for each cell in the grid, which will be used to compute trailing zeros.
6 : First Loop (Grid Iteration)
for(int i = 0; i < m; i++) {
This loop iterates over each row of the grid.
7 : Second Loop (Grid Iteration)
for(int j = 0; j < n; j++) {
This nested loop iterates over each column of the grid.
8 : Grid Value Assignment
int t = grid[i][j];
The value of the grid at position (i, j) is assigned to the variable 't'.
9 : Factor Calculation
array<int, 2> node = { fact(t, 2), fact(t, 5) };
The 'node' array stores the factors of 2 and 5 for the current grid value 't'. These factors will help in calculating trailing zeros.
10 : Cumulative Horizontal Update
h[i][j + 1] = h[i][j] + node;
The cumulative horizontal factors (2 and 5) are updated for the current position (i, j) in the 'h' array.
11 : Cumulative Vertical Update
v[i + 1][j] = v[i][j] + node;
The cumulative vertical factors (2 and 5) are updated for the current position (i, j) in the 'v' array.
12 : Second Loop (Max Calculation)
for(int i = 0; i < m; i++) {
This loop iterates again over each row of the grid, this time to calculate the maximum trailing zeros.
13 : Second Nested Loop (Max Calculation)
for(int j = 0; j < n; j++) {
This nested loop iterates again over each column to compute the maximum trailing zeros.
14 : Array Assignment for Calculation
array<int, 2> h1 = h[i][j],
This line extracts the horizontal factors (2 and 5) for the current cell (i, j) from the 'h' array.
15 : Array Assignment for Calculation
h2 = h[i][n] - h[i][j+1],
This line calculates the difference in horizontal factors to handle the rest of the row beyond (i, j).
16 : Array Assignment for Calculation
v1 = v[i+1][j],
This line extracts the vertical factors (2 and 5) for the current cell (i, j) from the 'v' array.
17 : Array Assignment for Calculation
v2 = v[m][j] - v[i][j];
This line calculates the difference in vertical factors to handle the rest of the column beyond (i, j).
18 : Max Calculation
res = max({res, pairs(v1+h1), pairs(v1+h2), pairs(v2+h1), pairs(v2+h2)});
The maximum trailing zeros are calculated by considering all possible combinations of horizontal and vertical factors.
19 : Return Result
return res;
Returns the final result, which is the maximum number of trailing zeros found.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: Each cell is processed once, and prefix sums allow efficient range queries.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space is used for prefix sum arrays and factorization storage.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus