Number of Increasing Paths in a Grid

The problem can be solved using dynamic programming with memoization. We’ll break down the solution into simple steps:

  1. Define a recursive function to compute the number of strictly increasing paths from a given cell (x, y).
  2. In the recursive function, for every adjacent cell (i, j) of the current cell (x, y): a. If the value in the adjacent cell (i, j) is greater than the current cell (x, y), call the recursive function for the adjacent cell. b. Add the result to the current count of paths.
  3. Use memoization to store the results of subproblems and avoid redundant computations.
  4. Iterate through all cells and call the recursive function for each cell. Sum the results.
  5. Return the total number modulo (10^9 + 7).

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        # Directions for adjacent cells
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        # Memoization dictionary
        memo = {}

        # Recursive function to compute paths
        def dfs(x, y):
            if (x, y) in memo:
                return memo[(x, y)]
            count = 1 # Path of length 1 (itself)
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > grid[x][y]:
                    count += dfs(nx, ny)
            memo[(x, y)] = count % MOD
            return count % MOD

        total_paths = 0
        # Iterate through all cells and call the recursive function
        for i in range(m):
            for j in range(n):
                total_paths += dfs(i, j)

        return total_paths % MOD

This solution has time complexity (O(m \times n)) and space complexity (O(m \times n)), where (m) and (n) are the dimensions of the grid. It returns the total number of strictly increasing paths in the grid.

10 Prerequisite LeetCode Problems

“2328. Number of Increasing Paths in a Grid” involves dynamic programming and grid traversal. Here are 10 problems to prepare:

  1. “62. Unique Paths”: This is a basic dynamic programming problem to understand grid traversal.

  2. “64. Minimum Path Sum”: An introduction to dynamic programming with grids where you also have to keep track of a sum.

  3. “63. Unique Paths II”: This extends the concept of grid traversal with dynamic programming to include obstacles.

  4. “120. Triangle”: This problem introduces a variant of the grid traversal where the grid is not necessarily rectangular.

  5. “221. Maximal Square”: This problem involves dynamic programming with a grid and understanding local and global optimality.

  6. “931. Minimum Falling Path Sum”: This problem also includes the concept of path sum in a grid traversal.

  7. “174. Dungeon Game”: This problem extends grid traversal to include negative values.

  8. “96. Unique Binary Search Trees”: While not directly relevant, this problem involves dynamic programming and helps with understanding the concept of number of unique paths.

  9. “1143. Longest Common Subsequence”: This problem introduces the concept of dynamic programming with two pointers, which could be useful in more complex grid traversal problems.

  10. “198. House Robber”: This problem introduces the concept of keeping track of two states in dynamic programming, which could also be useful for grid problems.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        noOfRows, noOfCols, res = len(grid), len(grid[0]), 0
        dp = [[-1 for _ in range(noOfCols)] for _ in range(noOfRows)]

        def dfs(row: int, col: int, prev: int, dp: List[List[int]], grid: List[List[int]]) -> int:
            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] <= prev:
                return 0
            if dp[row][col] != -1: 
                return dp[row][col]
            ans = 1
            for direction in directions:
                newRow, newCol = row + direction[0], col + direction[1]
                ans += dfs(newRow, newCol, grid[row][col], dp, grid)
            dp[row][col] = ans
            return ans

        for row in range(noOfRows):
            for col in range(noOfCols):
                res += dfs(row, col, -1, dp, grid)
        return res % (10 ** 9 + 7)

Problem Classification

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

Grid Traversal Pathfinder

Language Agnostic Coding Drills

This is a problem of finding all possible paths in a 2D grid using Depth-First Search (DFS). Here’s a breakdown of the learning concepts involved:

  1. Variable and List Initialization: Understand how to create and initialize variables and lists.

  2. 2D Lists (Matrices): Familiarize yourself with 2D lists (Matrices) operations such as creating a 2D list and accessing elements in it.

  3. Iterating Over a List: Learn how to use loops to iterate over a list or 2D list.

  4. Recursive Functions: Understand the concept of recursion and how to implement a recursive function.

  5. Depth-First Search (DFS) Algorithm: Learn about DFS as a method for traversing or searching tree or graph data structures.

  6. Modulo Operation: Understand the use of the modulo operation to prevent integer overflow in your calculations.

  7. 2D Dynamic Programming: Get the grasp of using 2D dynamic programming to optimize the recursive calls and store intermediate results.

  8. Directions Array for Grid Traversal: Understand the use of a directions array for grid traversal.

  9. Conditional Statements: Learn how to use if-else conditions to control the flow of the program.

  10. Function Arguments: Understand how to pass arguments to a function, especially when passing a data structure like a list or a matrix.

Each of these concepts can be practiced and mastered individually, and once comfortable, they can be combined to understand and solve the overall problem.

Targeted Drills in Python

  1. Variable and List Initialization:
1
2
3
4
5
6
7

# Initializing a variable
x = 5
print(x)

# Initializing a list
lst = [1, 2, 3, 4, 5]
print(lst)
  1. 2D Lists (Matrices):
1
2
3
4
5

# Initializing a 2D list
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# Accessing elements
print(matrix[0][0]) # Output: 1
  1. Iterating Over a List:
1
2
3
4
5
6

# Define a list
lst = [1, 2, 3, 4, 5]

# Iterate over the list
for i in lst:
    print(i)
  1. Recursive Functions:
1
2
3
4
5
6
7
8

# Factorial of a number using recursion
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5)) # Output: 120
  1. Depth-First Search (DFS) Algorithm:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# A simple implementation of DFS
def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

graph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
print(dfs(graph, 'A', [])) # Output: ['A', 'B', 'D', 'E', 'F', 'C']
  1. Modulo Operation:
1
2

# A simple modulo operation
print(10 % 3) # Output: 1
  1. 2D Dynamic Programming:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# Simple 2D Dynamic Programming for finding the length of longest common subsequence
def lcs(X , Y):
    m = len(X)
    n = len(Y)
    dp = [[0]*(n+1) for i in range(m+1)]
 
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0 :
                dp[i][j] = 0
            elif X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j] , dp[i][j-1])
 
    return dp[m][n]

X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y)) # Output: 4
  1. Directions Array for Grid Traversal:
1
2

# Creating a directions array for grid traversal
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  1. Conditional Statements:
1
2
3
4
5
6

# If-else condition
x = 10
if x > 5:
    print("x is greater than 5")
else:
    print("x is less than or equal to 5")
  1. Function Arguments:
1
2
3
4
5
6
7

# Function to add two numbers
def add(a,

 b):
    return a+b

print(add(3, 4)) # Output: 7

Each of these drills can help you practice a specific concept in isolation. Once you are comfortable with each of them, you can start combining them.