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.
1import java.util.*;
2
3
This Java solution follows a similar algorithm to the C++ implementation. It begins by initializing a 'paths' array where each cell starts with a count of 1. It uses a list of cell coordinates, sorted by grid values. Each cell's neighboring cells are then updated based on condition checks of increasing values, ensuring correct path accumulation before summing across the grid.