LeetCode 2328 - Number of Increasing Paths in a Grid

In this problem, we are given a two dimensional matrix called grid. Each cell contains a positive integer. From any cell, we may move in four directions: up, down, left, or right. Diagonal movement is not allowed.

leetcodehardarraydynamic-programmingdepth-first-searchbreadth-first-searchgraph-theorytopological-sortmemoizationmatrix

LeetCode Problem 2328

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort, Memoization, Matrix

Solution

Problem Understanding

In this problem, we are given a two dimensional matrix called grid. Each cell contains a positive integer. From any cell, we may move in four directions: up, down, left, or right. Diagonal movement is not allowed.

The goal is to count how many strictly increasing paths exist in the entire grid. A path is considered strictly increasing if every next cell in the path contains a larger value than the current cell.

A path can:

  • Start from any cell
  • End at any cell
  • Have length 1, meaning a single cell by itself counts as a valid path

Two paths are considered different if their sequences of visited cells differ in any position.

The answer can become extremely large because the number of possible paths grows quickly, so we must return the result modulo:

$10^9 + 7$

The constraints are important:

  • m * n <= 100000
  • Each cell value is between 1 and 100000

This immediately tells us that an exponential brute force search will not work. Even though each cell has at most four neighbors, the number of increasing paths can explode combinatorially.

A key observation is that strictly increasing movement creates a directed acyclic graph, abbreviated as DAG. Since values must strictly increase, we can never return to a previously visited value through a cycle. This acyclic structure makes dynamic programming and memoization possible.

Several edge cases are important:

  • A grid with only one cell should return 1
  • A grid where all values are equal should return exactly the number of cells, since no multi-cell increasing path exists
  • Long increasing chains must be handled efficiently without recomputation
  • Large grids near the maximum constraint require near linear complexity

Approaches

Brute Force Approach

A naive solution is to start a depth first search from every cell and recursively explore all strictly increasing neighbors.

For every path, we extend the search in all valid directions. Every time we visit a cell sequence, we count it as one valid path.

This approach is correct because it explicitly enumerates every increasing path. However, it is far too slow.

The major problem is overlapping subproblems. Suppose many paths eventually reach the same cell. From that cell onward, the remaining increasing paths are identical, but the brute force solution recomputes them repeatedly.

In the worst case, the number of increasing paths grows exponentially, making this approach infeasible for grids with up to 100000 cells.

Optimal Approach, DFS + Memoization

The key insight is that the number of increasing paths starting from a cell depends only on its larger neighbors.

Define:

  • dp[r][c] = number of increasing paths starting from cell (r, c)

Every cell contributes at least one path, the cell itself.

Then we try all four directions. If a neighboring cell contains a larger value, we may extend the path into that neighbor.

This gives the recurrence:

$dp(r,c)=1+\sum dp(nr,nc)$

where the sum is over all strictly larger neighboring cells.

Because increasing moves can never form cycles, memoization guarantees that each cell is computed only once.

This transforms an exponential search into a linear dynamic programming solution over the grid.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(path length) Recomputes the same subproblems many times
Optimal O(m * n) O(m * n) DFS with memoization computes each cell once

Algorithm Walkthrough

  1. Create a memoization table called memo with the same dimensions as the grid.

Each entry stores the number of increasing paths starting from that cell. Initially, all entries are uncomputed. 2. Define the four movement directions.

We need to check:

  • Up
  • Down
  • Left
  • Right
  1. Write a DFS function dfs(r, c).

This function returns the number of strictly increasing paths starting from cell (r, c). 4. Check whether the current cell has already been computed.

If memo[r][c] is nonzero, immediately return the stored result.

This avoids recomputing the same subproblem multiple times. 5. Initialize the answer for the current cell as 1.

Every cell itself forms a valid path of length 1. 6. Explore all four neighboring cells.

For each neighbor:

  • Verify it lies inside the grid
  • Verify its value is strictly larger than the current cell

If both conditions hold, recursively compute the number of paths starting from that neighbor and add them to the current answer. 7. Apply modulo arithmetic after every addition.

Since the number of paths may become extremely large, we always compute values modulo:

$10^9 + 7$ 8. Store the computed result in memo[r][c].

Future DFS calls can reuse this value instantly. 9. Iterate through every cell in the grid.

Call dfs(r, c) for each cell and accumulate the results. 10. Return the final total modulo 10^9 + 7.

Why it works

The algorithm works because strictly increasing movement guarantees an acyclic dependency structure. A cell only depends on neighbors with larger values, so recursion always moves toward larger numbers and can never loop infinitely.

Memoization ensures that each cell's result is computed exactly once. Since every increasing path starting from a cell is counted precisely one time, and every cell is processed independently, the final sum correctly counts all increasing paths in the grid.

Python Solution

from typing import List

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7

        rows = len(grid)
        cols = len(grid[0])

        memo = [[0] * cols for _ in range(rows)]

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]

        def dfs(r: int, c: int) -> int:
            if memo[r][c] != 0:
                return memo[r][c]

            total_paths = 1

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if (
                    0 <= nr < rows and
                    0 <= nc < cols and
                    grid[nr][nc] > grid[r][c]
                ):
                    total_paths += dfs(nr, nc)
                    total_paths %= MOD

            memo[r][c] = total_paths
            return total_paths

        answer = 0

        for r in range(rows):
            for c in range(cols):
                answer += dfs(r, c)
                answer %= MOD

        return answer

The implementation begins by defining constants and determining the grid dimensions.

The memo table stores previously computed results. A value of 0 means the cell has not yet been processed.

The directions list simplifies neighbor traversal. Instead of writing separate logic for each direction, we iterate through the directional offsets.

The dfs function performs the core dynamic programming computation. If a cell has already been solved, the stored value is immediately returned.

Every cell contributes at least one valid path, itself, so total_paths starts at 1.

The DFS then checks all neighboring cells. Only neighbors with strictly larger values are explored. For each valid neighbor, we recursively add the number of increasing paths starting there.

After computing the result, it is stored in memo[r][c] so future calls reuse the cached value.

Finally, the outer loops start DFS from every cell and accumulate the total count.

Go Solution

func countPaths(grid [][]int) int {
    const MOD int = 1e9 + 7

    rows := len(grid)
    cols := len(grid[0])

    memo := make([][]int, rows)
    for i := range memo {
        memo[i] = make([]int, cols)
    }

    directions := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(int, int) int

    dfs = func(r int, c int) int {
        if memo[r][c] != 0 {
            return memo[r][c]
        }

        totalPaths := 1

        for _, dir := range directions {
            nr := r + dir[0]
            nc := c + dir[1]

            if nr >= 0 &&
                nr < rows &&
                nc >= 0 &&
                nc < cols &&
                grid[nr][nc] > grid[r][c] {

                totalPaths += dfs(nr, nc)
                totalPaths %= MOD
            }
        }

        memo[r][c] = totalPaths
        return totalPaths
    }

    answer := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            answer += dfs(r, c)
            answer %= MOD
        }
    }

    return answer
}

The Go implementation follows the same logic as the Python version.

The memoization table is created using nested slices. The recursive DFS function is declared using a function variable so it can reference itself recursively.

Modulo arithmetic is performed using Go integers. Since the final values remain bounded by the modulo, standard int is sufficient for LeetCode's constraints.

Go slices are used instead of Python lists, but the dynamic programming structure remains identical.

Worked Examples

Example 1

Input:

grid = [
    [1, 1],
    [3, 4]
]

Initial memo table:

Cell Value Memo
(0,0) 1 0
(0,1) 1 0
(1,0) 3 0
(1,1) 4 0

Start DFS from (1,1):

  • Value = 4
  • No larger neighbors
  • Paths = [4]

So:

memo[1][1] = 1

Now DFS from (1,0):

  • Value = 3
  • Larger neighbor: 4

Paths:

  • [3]
  • [3 -> 4]

So:

memo[1][0] = 2

Now DFS from (0,0):

  • Value = 1

  • Larger neighbors:

  • 3

  • 4

Paths:

  • [1]
  • [1 -> 3]
  • [1 -> 3 -> 4]
  • [1 -> 4]

So:

memo[0][0] = 4

Now DFS from (0,1):

  • Value = 1

  • Larger neighbor:

  • 4

Paths:

  • [1]
  • [1 -> 4]

So:

memo[0][1] = 2

Final memo table:

Cell Paths Starting There
(0,0) 4
(0,1) 2
(1,0) 2
(1,1) 1

Total:

$4 + 2 + 2 + 1 = 8$

Example 2

Input:

grid = [
    [1],
    [2]
]

Start DFS from bottom cell:

  • [2]

So:

memo[1][0] = 1

Now DFS from top cell:

Paths:

  • [1]
  • [1 -> 2]

So:

memo[0][0] = 2

Final total:

$2 + 1 = 3$

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is computed once, and each computation checks at most four neighbors
Space O(m * n) Memoization table plus recursion stack

The DFS computation for each cell is memoized, so repeated calls return instantly. Since every cell processes only four directions, the total work is proportional to the number of cells in the grid.

The recursion stack can grow in the worst case to the length of the longest increasing path, which may reach m * n.

Test Cases

from typing import List

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7

        rows = len(grid)
        cols = len(grid[0])

        memo = [[0] * cols for _ in range(rows)]

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]

        def dfs(r: int, c: int) -> int:
            if memo[r][c]:
                return memo[r][c]

            total = 1

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if (
                    0 <= nr < rows and
                    0 <= nc < cols and
                    grid[nr][nc] > grid[r][c]
                ):
                    total += dfs(nr, nc)
                    total %= MOD

            memo[r][c] = total
            return total

        answer = 0

        for r in range(rows):
            for c in range(cols):
                answer += dfs(r, c)
                answer %= MOD

        return answer

solution = Solution()

assert solution.countPaths([[1,1],[3,4]]) == 8  # provided example
assert solution.countPaths([[1],[2]]) == 3  # vertical increasing path
assert solution.countPaths([[5]]) == 1  # single cell
assert solution.countPaths([[1,1],[1,1]]) == 4  # all equal values
assert solution.countPaths([[1,2],[3,4]]) == 10  # multiple increasing choices
assert solution.countPaths([[4,3],[2,1]]) == 10  # decreasing layout still allows upward paths
assert solution.countPaths([[1,2,3,4]]) == 10  # single row increasing
assert solution.countPaths([[4,3,2,1]]) == 10  # single row decreasing
assert solution.countPaths([[1],[2],[3],[4]]) == 10  # single column increasing
assert solution.countPaths([[7,7,7]]) == 3  # no increasing neighbors
Test Why
[[1,1],[3,4]] Validates the primary example
[[1],[2]] Tests a simple vertical increasing chain
[[5]] Smallest possible grid
[[1,1],[1,1]] Ensures equal values are not considered increasing
[[1,2],[3,4]] Tests branching increasing paths
[[4,3],[2,1]] Verifies traversal depends on adjacency, not ordering
[[1,2,3,4]] Tests long horizontal increasing chain
[[4,3,2,1]] Tests reverse ordered row
[[1],[2],[3],[4]] Tests long vertical chain
[[7,7,7]] Confirms isolated single-cell paths only

Edge Cases

Single Cell Grid

A grid containing only one cell is the smallest valid input. A naive implementation might accidentally return 0 if it only counts paths formed by movement. However, a single cell itself is a valid increasing path of length 1.

The implementation handles this correctly because every DFS starts with:

total_paths = 1

Even if no neighbors exist, the cell contributes one valid path.

All Values Equal

If all cells contain the same value, no movement is allowed because paths must be strictly increasing.

For example:

[
    [2, 2],
    [2, 2]
]

The correct answer is 4, one for each cell.

The implementation correctly checks:

grid[nr][nc] > grid[r][c]

Equal values are rejected, preventing invalid transitions.

Long Increasing Chains

Consider a large snake-like increasing path across many cells. Without memoization, the recursion would repeatedly recompute the same suffix paths many times.

The memoization table prevents this issue. Once a cell's result is computed, every future DFS call immediately reuses the stored value.

This optimization is what reduces the complexity from exponential time to linear time.