Daily LeetCode Problems: Problem 2328. Number of Increasing Paths in a Grid
Solving LeetCode Problem 2328: Number of Increasing Paths in a Grid
Welcome to another daily article on LeetCode problems! In today’s article, we will discuss problem 2328, “Number of Increasing Paths in a Grid”. We will carefully examine the problem statement, discuss an approach to solving it, provide pseudocode for the solution, and discuss some implementation details. Let’s get started!
Problem Statement
The problem requires us to count the number of strictly increasing paths in a given matrix grid. We can move from a cell to any adjacent cell in all four directions. Two paths are considered different if they do not have exactly the same sequence of visited cells.
Our task is to calculate the number of strictly increasing paths in the grid, starting from any cell and ending at any cell. Since the answer may be very large, we need to return it modulo 10⁹ + 7.
Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].
- Paths with length 3: [1 -> 3 -> 4].
The total number of paths is 4 + 3 + 1 = 8.Approach
To solve this problem, we will use a dynamic programming approach. We will create a separate 2D grid to store the count of increasing paths for each cell. We will perform the following steps:
- Initialize an m x n 2D grid
dpwith all cells set to 0. - Iterate through each cell in the grid, starting from the top-left cell.
- For each cell, calculate the number of increasing paths by considering the adjacent cells. We will add the counts of the cells from which we can reach the current cell while maintaining the strictly increasing condition.
- Update the
dpgrid with the calculated count for each cell. - Finally, the bottom-right cell of the
dpgrid will contain the total count of strictly increasing paths in the original grid. - Return the count modulo 10⁹ + 7.
Pseudocode
Let’s express the solution steps in pseudocode:
function countIncreasingPaths(grid):
Initialize m and n as the number of rows and columns in the grid.
Initialize dp as an m x n 2D grid with all cells set to 0.
For i from 0 to m-1:
For j from 0 to n-1:
Set dp[i][j] to the count of increasing paths considering adjacent cells.
For each valid adjacent cell (x, y):
If grid[x][y] < grid[i][j], increment dp[i][j] by dp[x][y].
Return dp[m-1][n-1] modulo 10^9 + 7 as the count of strictly increasing paths.Implementation Details
Implementing the countIncreasingPaths function in your preferred programming language should be straightforward. You can use nested loops to iterate through the cells of the grid and calculate the count of increasing paths.
Keep in mind that the count may become very large, so it’s important to take modulo 10⁹ + 7 after each addition to avoid integer overflow.
Make sure to handle edge cases, such as when the grid is empty or when it has different numbers of rows or columns.
Full Solution
Python
class Solution:
def countPaths(self, grid: List[List[int]]) -> int:
kMod = 1_000_000_007
m = len(grid)
n = len(grid[0])
dirs = [0, 1, 0, -1, 0]
# dp(i, j) := # of increasing paths starting from (i, j)
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
ans = 1 # Current cell contributes 1 length
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if grid[x][y] <= grid[i][j]:
continue
ans += dp(x, y)
ans %= kMod
return ans
return sum(dp(i, j)
for i in range(m)
for j in range(n)) % kModJava
class Solution {
public int countPaths(int[][] grid) {
m = grid.length;
n = grid[0].length;
int ans = 0;
// dp[i][j] := # of increasing paths starting from (i, j)
dp = new int[m][n];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
ans += dfs(grid, i, j);
ans %= kMod;
}
return ans;
}
private static final int kMod = 1_000_000_007;
private final int[] dirs = {0, 1, 0, -1, 0};
private int m;
private int n;
private int[][] dp;
private int dfs(int[][] grid, int i, int j) {
if (dp[i][j] != -1)
return dp[i][j];
dp[i][j] = 1; // Current cell contributes 1 length
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] <= grid[i][j])
continue;
dp[i][j] += dfs(grid, x, y);
dp[i][j] %= kMod;
}
return dp[i][j];
}
}C++
class Solution {
public:
int countPaths(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
int ans = 0;
// dp[i][j] := # of increasing paths starting from (i, j)
dp.resize(m, vector<int>(n, -1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
ans += dfs(grid, i, j);
ans %= kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
const vector<int> dirs{0, 1, 0, -1, 0};
int m;
int n;
vector<vector<int>> dp;
int dfs(const vector<vector<int>>& grid, int i, int j) {
if (dp[i][j] != -1)
return dp[i][j];
dp[i][j] = 1; // Current cell contributes 1 length
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] <= grid[i][j])
continue;
dp[i][j] += dfs(grid, x, y);
dp[i][j] %= kMod;
}
return dp[i][j];
}
};Conclusion
In this article, we explored LeetCode problem 2328, “Number of Increasing Paths in a Grid”. We carefully examined the problem statement, discussed an approach to count the number of strictly increasing paths in the grid, provided pseudocode for the solution, and discussed some implementation details.
Remember, consistent practice and problem-solving are key to improving your coding skills. So, make it a habit to challenge yourself with more LeetCode problems regularly. Happy coding!
