##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2328.html

# 2328. Number of Increasing Paths in a Grid

• Difficulty: Hard.
• Related Topics: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization, Matrix.
• Similar Questions: Longest Increasing Path in a Matrix, All Paths From Source to Target.

## Problem

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return the number of **strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it **modulo 109 + 7.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

Example 1:

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.


Example 2:

Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -> 2].
The total number of paths is 2 + 1 = 3.


Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 1000

• 1 <= m * n <= 105

• 1 <= grid[i][j] <= 105

## Solution

• class Solution {
private int help(int[][] a, int i, int j, int n, int m, int[][] dp) {
if (i < 0 || i >= n || j >= m || j < 0) {
return 0;
}
if (dp[i][j] != 0) {
return dp[i][j];
}
long res = 0;
if (i < n - 1 && a[i + 1][j] > a[i][j]) {
res += 1 + help(a, i + 1, j, n, m, dp);
}
if (i > 0 && a[i - 1][j] > a[i][j]) {
res += 1 + help(a, i - 1, j, n, m, dp);
}
if (j > 0 && a[i][j - 1] > a[i][j]) {
res += 1 + help(a, i, j - 1, n, m, dp);
}
if (j < m - 1 && a[i][j + 1] > a[i][j]) {
res += 1 + help(a, i, j + 1, n, m, dp);
}
dp[i][j] = (int) res % 1000000007;
return dp[i][j];
}

public int countPaths(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
long ans = (long) n * m;
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += help(grid, i, j, n, m, dp) % 1000000007;
}
}
ans = ans % 1000000007;
return (int) ans;
}
}

############

class Solution {
private int m;
private int n;
private int[][] g;
private int[][] f;
private static final int MOD = (int) 1e9 + 7;

public int countPaths(int[][] grid) {
g = grid;
m = g.length;
n = g[0].length;
f = new int[m][n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans = (ans + dfs(i, j)) % MOD;
}
}
return ans;
}

private int dfs(int i, int j) {
if (f[i][j] != 0) {
return f[i][j];
}
int res = 1;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] > g[i][j]) {
res = (res + dfs(x, y)) % MOD;
}
}
f[i][j] = res;
return res;
}
}

• class Solution:
def countPaths(self, grid: List[List[int]]) -> int:
@cache
def dfs(i, j):
res = 1
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:
res += dfs(x, y)
return res

m, n = len(grid), len(grid[0])
mod = 10**9 + 7
return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod

############

# 2328. Number of Increasing Paths in a Grid
# https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/

class Solution:
def countPaths(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
res = 0
M = 10 ** 9 + 7

@cache
def go(x, y):
count = 1

for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] > grid[x][y]:
count += go(dx, dy)
count % M

return count % M

for x in range(rows):
for y in range(cols):
res += go(x, y)
res % M

return res % M


• class Solution {
public:
const int mod = 1e9 + 7;
int countPaths(vector<vector<int>>& grid) {
int ans = 0;
vector<vector<int>> f(grid.size(), vector<int>(grid[0].size()));
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
ans = (ans + dfs(i, j, f, grid)) % mod;
return ans;
}

int dfs(int i, int j, vector<vector<int>>& f, vector<vector<int>>& g) {
if (f[i][j]) return f[i][j];
int res = 1;
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < g.size() && y >= 0 && y < g[0].size() && g[x][y] > g[i][j])
res = (res + dfs(x, y, f, g)) % mod;
}
f[i][j] = res;
return res;
}
};

• func countPaths(grid [][]int) int {
m, n := len(grid), len(grid[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
mod := int(1e9) + 7
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
var dfs func(int, int) int
dfs = func(i, j int) int {
if f[i][j] > 0 {
return f[i][j]
}
res := 1
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > grid[i][j] {
res = (res + dfs(x, y)) % mod
}
}
f[i][j] = res
return res
}
for i, row := range grid {
for j := range row {
ans = (ans + dfs(i, j)) % mod
}
}
return ans
}

• function countPaths(grid: number[][]): number {
const mod = BigInt(10 ** 9 + 7);
const dirs = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
const m = grid.length,
n = grid[0].length;
const dp = Array.from({ length: m }, v => new Array(n).fill(-1n));

function dfs(x, y) {
if (dp[x][y] != -1) return dp[x][y];
let count = 1n;
for (let [dx, dy] of dirs) {
let i = x + dx,
j = y + dy;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= grid[x][y])
continue;
count = (count + dfs(i, j)) % mod;
}
dp[x][y] = count;
return count;
}

let sum = 0n;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
sum = (sum + dfs(i, j)) % mod;
}
}
return Number(sum);
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).