2328. Number of Increasing Paths in a Grid

HardDepth-First SearchBreadth-First SearchGraphTopological SortMemoizationArrayDynamic ProgrammingMatrix
Leetcode Link

Problem Description

In this problem, we're presented with a 2D matrix grid consisting of integers, with dimensions m x n. The task is to find the total count of strictly increasing paths through the grid. A path is considered strictly increasing if every consecutive pair of numbers in the path has the latter number greater than the former.

We can start from any cell in the grid and move to any adjacent cell (either up, down, left, or right) as long as we respect the strictly increasing condition. Our goal is to determine all such possible paths in the grid.

A few additional points to consider:

  • You can move in one of the four cardinal directions: up, down, left, or right.
  • Two paths are unique if they have a different sequence of visited cells.
  • Because the number of paths might be quite large, the result should be returned modulo 10^9 + 7.

Intuition

When faced with problems involving paths, grids, and conditions on movements, it's common to consider depth-first search (DFS) as it allows us to explore all possible paths from a given starting point. DFS is a recursive algorithm that dives deep into a graph (or grid, in this case) to visit nodes and check for the satisfaction of the given condition before backtracking.

The approach hinges on two key insights:

  1. Start from anywhere, end anywhere: Since we can start and end at any cell, every cell must be considered as a possible start point.
  2. Count each valid path once: Since moving to an adjacent greater cell constitutes a valid path, from any cell (i, j), we should count all paths starting from it.

To implement this, we arrive at a solution that involves recursive DFS, where for each cell (i, j), the function dfs(i, j) calculates the number of strictly increasing paths starting from that cell.

Rather than recalculating paths from each cell multiple times, we employ memoization โ€” a technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again.

The core idea behind the given solution is:

  • Use DFS to explore all adjacent cells.
  • Cache the results to prevent redundant calculations.
  • Sum up the counts of increasing paths starting from all cells.
  • Return the summed count modulo 10^9 + 7 as per the problem's requirement to deal with large numbers.

In essence, for each cell (i, j), dfs is called and checks its 4 neighbors (up, down, left, right). If a neighbor (x, y) is in the bounds of the grid and the value at grid[x][y] is larger than grid[i][j], it is considered part of a strictly increasing path. The counts from all such neighbors are summed up to give the total count of paths starting from (i, j).

The solution sums the counts from all possible starting points and applies the modulus at each step to keep the numbers in the range, finally giving the aggregated result modulo 10^9 + 7.

Learn more about Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

As outlined previously, the solution uses DFS to explore paths starting from each cell, keeping track of the strictly increasing sequences. In addition, memoization ensures that the same computation is not repeated for a cell, thereby optimizing the process significantly. Let's walk through the implementation:

The dfs function is the heart of our solution. It recursively computes the number of increasing paths starting from a cell (i, j). We first check if the answer for this cell is already calculated and stored (memoized). If so, we directly return the stored answer, circumventing repetitive work. This memoization is achieved using the @cache decorator, which stores the result of each unique call based on the arguments (i, j).

If the result for a cell (i, j) is not memoized, we calculate it by initializing ans = 1, accounting for the path that consists only of the starting cell. Then, we move to adjacent cells using computed offsets within the pairwise list (-1, 0, 1, 0, -1), ensuring we stay inside the grid bounds. If an adjacent cell (x, y) contains a greater integer value than current (i, j), it forms a valid strictly increasing path, so we recursively call dfs(x, y) and add the result to ans.

To handle the large counts, every addition operation is done modulo 10^9 + 7. This ensures that intermediate results do not overflow integer limits while maintaining the final count's accuracy in modular arithmetic.

Finally, to obtain the sum of the paths starting from all cells, we iterate over each cell (i, j) of the grid, calling dfs(i, j), and sum the results, applying the modulo operation one last time to get the total count of strictly increasing paths.

The mod = 10**9 + 7 variable defines the modulo value which is used to keep the results within the specified range throughout the calculations. The m and n variables store the dimensions of the grid.

Data structures and patterns used in the implementation:

  • A 2D list (grid) to store the matrix.
  • Recursion for DFS.
  • A cache (implicit from the @cache decorator) to memoize the results for each cell.
  • Pairwise iteration (using a pattern with (-1, 0, 1, 0, -1)) to get the adjacent cells in the grid.

By leveraging recursion, memoization, and modular arithmetic, the provided solution approach efficiently computes the number of strictly increasing paths in a grid.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's take a small 3x3 grid as our example to illustrate the solution approach:

1Grid:
21 2 5
33 2 4
41 3 6

We will go through the major steps of DFS and memoization to explain how we determine the total count of strictly increasing paths for each cell in the grid.

  1. Start with the top-left cell (1,1):

    • The starting value is 1.
    • We look for strictly increasing numbers among its neighbors grid[1][2] (which is 2), and grid[2][1] (which is 3).
    • We call dfs(1,2) and dfs(2,1) to continue the path.

  2. Exploring paths from cell (1,2) with value 2:

    • Its neighbors are grid[1][3] (5), and grid[2][2] (2).
    • Since grid[2][2] is not greater than 2, it is not considered.
    • We call dfs(1,3) to continue the path.

  3. Exploring paths from cell (2,1) with value 3:

    • The only neighbor greater than 3 is grid[2][2] (value 2), which is not strictly increasing and thus this path ends here.

  4. Exploring paths from cell (1,3) with value 5:

    • There are no neighbors with a greater value, so this path ends here.

  5. Continue the process for each cell:

    • For this 3x3 grid, we will end up calling the dfs function for each cell respecting the strictly increasing condition.

  6. Apply Memoization:

    • Each calculated path count from dfs(i, j) is stored to avoid redundant calculations.
    • When we encounter the same cell (i, j) during our DFS, we simply retrieve the stored count from our memoization cache.

  7. Aggregate and Modulo:

    • The answer for each cell is added to a global counter.
    • Each addition is taken modulo 10^9 + 7 to deal with large numbers.

For this example, let's simplify and say that dfs(1,1) found 2 paths, dfs(1,2) found 1 path, dfs(1,3) found 1 path, and so on for the remaining cells (imaginary numbers for the purpose of this example). We then add all these up to find the total number of strictly increasing paths in the grid modulo 10^9 + 7.

In this manner, by exploring all paths starting from each cell, using DFS and optimizing our process with memoization, we can calculate the total count of strictly increasing paths in the grid. The final result reported will be the sum of the counts from all cells modulo 10^9 + 7.

Solution Implementation

1from functools import cache  # Import necessary decorator for memoization
2from itertools import pairwise  # Import the pairwise utility from itertools
3
4class Solution:
5    def countPaths(self, grid: List[List[int]]) -> int:
6        # Define the DFS function with memoization to search paths
7        @cache
8        def dfs(row: int, col: int) -> int:
9            # Initialize the number of paths with the current cell (1 path)
10            num_paths = 1
11          
12            # Define directions for exploring adjacent cells (up, right, down, left)
13            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
14
15            # Iterate over each pair of directions using pairwise
16            for (delta_row, delta_col) in pairwise(directions + directions[:1]):
17                # Determine the new cell coordinates
18                new_row, new_col = row + delta_row, col + delta_col
19
20                # Check if new cell is in bounds and is greater than current cell
21                if 0 <= new_row < m and 0 <= new_col < n and grid[row][col] < grid[new_row][new_col]:
22                    # If conditions satisfy, recurse on the new cell and update paths count
23                    num_paths = (num_paths + dfs(new_row, new_col)) % MOD
24          
25            # Return the total number of paths from this cell
26            return num_paths
27      
28        # Define constant MOD to prevent overflow (using modulo operation)
29        MOD = 10**9 + 7
30      
31        # Get the dimensions of the grid
32        m, n = len(grid), len(grid[0])
33
34        # Calculate the sum of paths starting from each cell in the grid
35        # The result is the total number of strictly increasing paths
36        total_paths = sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD
37
38        # Return the computed total paths
39        return total_paths
40
1class Solution {
2    private int[][] memoization;
3    private int[][] grid;
4    private int rows;
5    private int cols;
6    private final int MOD = (int) 1e9 + 7; // Using a constant for the modulus value for all operations
7
8    // Count all possible unique paths from each cell
9    public int countPaths(int[][] grid) {
10        rows = grid.length;
11        cols = grid[0].length;
12        this.grid = grid;
13        memoization = new int[rows][cols];
14        int totalPaths = 0;
15
16        // Iterate over each cell of the grid
17        for (int i = 0; i < rows; ++i) {
18            for (int j = 0; j < cols; ++j) {
19                // Sum all paths using depth-first search
20                totalPaths = (totalPaths + dfs(i, j)) % MOD;
21            }
22        }
23        return totalPaths;
24    }
25
26    // Perform a depth-first search to find all unique paths from the current cell
27    private int dfs(int row, int col) {
28        // Return pre-computed value if already processed
29        if (memoization[row][col] != 0) {
30            return memoization[row][col];
31        }
32
33        // At least one path exists starting from this cell (the cell itself)
34        int pathCount = 1;
35
36        // Direction vectors for exploring neighboring cells (up, right, down, left)
37        int[] dx = {-1, 0, 1, 0};
38        int[] dy = {0, 1, 0, -1};
39
40        // Explore all 4 directions
41        for (int direction = 0; direction < 4; ++direction) {
42            int newRow = row + dx[direction];
43            int newCol = col + dy[direction];
44
45            // Continue DFS if the new cell is within the grid and has a larger value
46            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols 
47                    && grid[row][col] < grid[newRow][newCol]) {
48                pathCount = (pathCount + dfs(newRow, newCol)) % MOD; // Add paths from the new cell
49            }
50        }
51
52        // Cache the result before returning
53        return memoization[row][col] = pathCount;
54    }
55}
56
1class Solution {
2public:
3    int countPaths(vector<vector<int>>& grid) {
4        const int MOD = 1e9 + 7;
5        int m = grid.size(), n = grid[0].size();
6      
7        // Initialize memoization table with zeros (dynamic programming cache)
8        vector<vector<int>> dp(m, vector<int>(n, 0));
9      
10        // Internal recursive depth-first search function with memoization
11        function<int(int, int)> dfs = [&](int row, int col) -> int {
12            // If the number of paths from this cell has already been computed, return it
13            if (dp[row][col]) {
14                return dp[row][col];
15            }
16          
17            // Start with a base case of 1 - the path that includes only the current cell
18            int paths = 1;
19          
20            // Directions for exploring adjacent cells: up, right, down, left
21            int dirs[5] = {-1, 0, 1, 0, -1};
22          
23            // Visit all neighboring cells following the increasing-value rule
24            for (int k = 0; k < 4; ++k) {
25                int x = row + dirs[k], y = col + dirs[k + 1];
26                // Check for valid indices and ascending values according to the problem description
27                if (x >= 0 && x < m && y >= 0 && y < n && grid[row][col] < grid[x][y]) {
28                    paths = (paths + dfs(x, y)) % MOD; // Add the number of paths from the neighbor
29                }
30            }
31          
32            // Memoize the number of paths from this cell
33            return dp[row][col] = paths;
34        };
35      
36        // The final answer to store the sum of all paths in the grid
37        int totalPaths = 0;
38      
39        // Iterate over each cell of the grid to compute all paths starting from each cell
40        for (int i = 0; i < m; ++i) {
41            for (int j = 0; j < n; ++j) {
42                // Sum paths from the current cell to the total paths
43                totalPaths = (totalPaths + dfs(i, j)) % MOD;
44            }
45        }
46      
47        // Return the total number of valid paths in the grid, reduced by modulo
48        return totalPaths;
49    }
50};
51
1// Function to count the number of increasing paths in a 2D grid
2// Each path moves to an adjacent cell with a strictly larger value.
3function countPaths(grid: number[][]): number {
4    const MODULO = 1e9 + 7; // The constant to ensure result stays within the bounds
5    const rows = grid.length; // The number of rows
6    const cols = grid[0].length; // The number of columns
7    const pathCounts = new Array(rows).fill(0).map(() => new Array(cols).fill(0)); // Grid to cache path counts
8    const directions: number[] = [-1, 0, 1, 0, -1]; // Direction vectors for exploration
9
10    // Helper function using Depth-First Search to compute increasing path count starting from (i, j)
11    const dfs = (i: number, j: number): number => {
12        if (pathCounts[i][j]) { // If the path count is already computed for (i, j), return it
13            return pathCounts[i][j];
14        }
15        let pathSum = 1; // Start with a path count of 1 for the current cell
16        // Explore all adjacent cells in 4 possible directions (up, right, down, left)
17        for (let k = 0; k < 4; ++k) {
18            const newX = i + directions[k];
19            const newY = j + directions[k + 1];
20            // Check if the next cell is within bounds and has a strictly greater value
21            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[i][j] < grid[newX][newY]) {
22                pathSum = (pathSum + dfs(newX, newY)) % MODULO; // Recursively compute path count for the next cell
23            }
24        }
25        pathCounts[i][j] = pathSum; // Cache the computed path count for (i, j)
26        return pathSum;
27    };
28
29    let totalCount = 0; // Total number of increasing paths
30    // Loop through all cells in the grid to start path computation
31    for (let i = 0; i < rows; ++i) {
32        for (let j = 0; j < cols; ++j) {
33            totalCount = (totalCount + dfs(i, j)) % MODULO; // Add up all path counts using DFS
34        }
35    }
36
37    return totalCount; // Return the total number of increasing paths
38}
39
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The time complexity of this code is not strictly O(m * n) because it employs a recursive depth-first search (DFS) with memoization. Consider that each cell in the grid may potentially be visited from its four neighboring cells, but with memoization, each cell is only computed once. Therefore, the time complexity is O(m * n * 4) due to the DFS traversal, but since we can discount the constant factor, it simplifies to O(m * n).

For space complexity, the memoization @cache will at most store a result for each unique call to dfs(i, j), which equates to each cell in the grid, m * n. Additionally, the recursive calls add to the stack depth, which in the worst case might involve all cells. Therefore, the space complexity is also O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ