Sponsored
Sponsored
This approach uses Depth First Search (DFS) combined with memoization to count the number of increasing paths starting from each cell. The main idea is to recursively explore each cell's neighbors, moving to the next cell only if its value is higher, and storing intermediate results to avoid redundant calculations.
Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once.
Space Complexity: O(m*n) due to the memoization table.
1const MOD = 10**9 + 7;
2
3function countPaths(grid) {
4 const m = grid.length;
5 const n = grid[0].length;
6 const dp = Array.from({ length: m }, () => Array(n).fill(-1));
7 const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
8
9 function dfs(x, y) {
10 if (dp[x][y] !== -1) return dp[x][y];
11 let pathCount = 1; // path of length 1 (itself)
12 for (const [dx, dy] of directions) {
13 const nx = x + dx, ny = y + dy;
14 if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
15 pathCount = (pathCount + dfs(nx, ny)) % MOD;
16 }
17 }
18 dp[x][y] = pathCount;
19 return dp[x][y];
20 }
21
22 let totalPaths = 0;
23 for (let i = 0; i < m; i++) {
24 for (let j = 0; j < n; j++) {
25 totalPaths = (totalPaths + dfs(i, j)) % MOD;
26 }
27 }
28 return totalPaths;
29}
30
31// Example Usage
32const grid = [[1, 1], [3, 4]];
33console.log(countPaths(grid)); // Output: 8
34This JavaScript solution follows a similar approach as the Python solution. It uses a depth-first search with memoization to explore possible paths, applying dynamic programming principles to store path counts in a 2D array 'dp' initialized to -1. The solution iterates through each cell, calculating paths and outputting the total modulo 10^9 + 7.
This approach involves sorting the cells of the grid based on their values and then using dynamic programming to calculate the number of increasing paths from each cell. By processing cells in increasing order, we ensure that when calculating the number of paths for a cell, all smaller cells have been processed.
Time Complexity: O(m*n*log(m*n)), primarily due to sorting m*n cells.
Space Complexity: O(m*n) for the paths storage.
1#include <vector>
2#include <algorithm>
3using namespace std;
4const int MOD = 1e9 + 7;
5
int countPaths(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> paths(m, vector<int>(n, 1));
vector<pair<int, int>> cells;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cells.emplace_back(i, j);
}
}
sort(cells.begin(), cells.end(), [&](pair<int, int> a, pair<int, int> b) {
return grid[a.first][a.second] < grid[b.first][b.second];
});
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [x, y] : cells) {
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
paths[nx][ny] = (paths[nx][ny] + paths[x][y]) % MOD;
}
}
}
int total_paths = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
total_paths = (total_paths + paths[i][j]) % MOD;
}
}
return total_paths;
}
// Example Usage
// vector<vector<int>> grid = {{1, 1}, {3, 4}};
// cout << countPaths(grid) << endl; // Output: 8
The C++ solution performs topological sorting based on grid values. It initially sets up each cell with a path count of 1. Cells are processed in value order using a vector of pairs, sorted by their value. For each cell, we explore adjacent cells that contain larger values, updating path counts as we go, ensuring earlier cells' paths are calculated before later ones, thus respecting dependencies.