Number of Increasing Paths in a Grid - Practice Coding Problems

Number of Increasing Paths in a Grid - Problem

Array Dynamic Programming Depth-First Search Breadth-First Search Graph Topological Sort Memoization Matrix Hard

Imagine you're exploring a mountainous terrain represented by a grid where each cell contains an elevation value. You can move to any of the 4 adjacent cells (up, down, left, right), but there's a catch - you can only move to cells with strictly higher elevation!

Given an m x n integer matrix grid, your task is to find the total number of strictly increasing paths possible in this terrain. You can start from any cell and end at any cell, as long as each step takes you to a higher elevation.

Key Points:

Two paths are different if they visit different sequences of cells
A single cell counts as a valid path of length 1
Return the answer modulo 10⁹ + 7 since it can be very large

Example: In a 2x2 grid [[1,1],[3,4]], you have paths like: [1]→[3]→[4], [1]→[3], [3]→[4], and all single cells, totaling 8 different increasing paths.

Input & Output

example_1.py — Basic Grid

$ Input: grid = [[1,1],[3,4]]

› Output: 8

💡 Note: The 8 increasing paths are: [1], [1], [3], [4], [1,3], [1,4], [1,3,4], [3,4]. Note that paths [1,3,4] and [1,4] start from different cells with value 1.

example_2.py — Single Row

$ Input: grid = [[1]]

› Output: 1

💡 Note: There's only one cell, so there's exactly one path consisting of just that single cell [1].

example_3.py — Larger Grid

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 109

💡 Note: This 3x3 grid has many possible increasing paths. Each cell can potentially reach multiple higher-valued cells, creating numerous path combinations.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 1000
1 ≤ grid[i][j] ≤ 10⁵
All values in the grid are unique

Visualization

Tap to expand

Understanding the Visualization

Initialize Grid

Each cell represents an elevation point. We need to find all strictly increasing paths.

DFS with Memoization

From each cell, explore all 4 directions and count paths to higher elevation cells.

Cache Results

Store the number of paths from each cell to avoid recalculation.

Sum All Paths

Add up all possible increasing paths from every starting cell.

Key Takeaway

🎯 Key Insight: Use memoization to transform an exponential brute force solution into an efficient O(m×n) algorithm by caching path counts for each cell.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

The optimal approach uses DFS with memoization to count increasing paths efficiently. By caching results for each cell, we avoid recalculating the same subproblems multiple times, reducing complexity from exponential to O(m×n). Each cell stores the number of increasing paths starting from that position, building up the solution bottom-up.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Memoization (Optimal)	O(m*n)	O(m*n)	Use DFS with memoization to avoid recalculating paths from the same cell
Brute Force DFS (Exponential)	O(4^(m*n))	O(m*n)	Recursively explore all possible increasing paths from every cell

DFS with Memoization (Optimal) — Algorithm Steps

Create a memoization table to store results for each cell
For each cell in the grid, call DFS with memoization
In DFS: if result for current cell exists, return it immediately
Otherwise, calculate paths by exploring all 4 higher-valued neighbors
Store the result in memo table before returning
Sum all results from each starting cell

Visualization

Tap to expand

Step-by-Step Walkthrough

First DFS call

Calculate paths from cell and store result in memo table

Subsequent calls

When same cell is visited again, return cached result immediately

Build up results

Results build up from cells with no outgoing paths to starting cells

Final summation

Sum all cached results for complete answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_CELLS 10000

int** grid;
int m, n;
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// Simple hash table for memoization
struct MemoEntry {
    int row, col, value;
    int used;
} memo[MAX_CELLS];

int getMemo(int row, int col) {
    int hash = (row * n + col) % MAX_CELLS;
    if (memo[hash].used && memo[hash].row == row && memo[hash].col == col) {
        return memo[hash].value;
    }
    return -1;
}

void setMemo(int row, int col, int value) {
    int hash = (row * n + col) % MAX_CELLS;
    memo[hash].row = row;
    memo[hash].col = col;
    memo[hash].value = value;
    memo[hash].used = 1;
}

int dfs(int row, int col) {
    int cached = getMemo(row, col);
    if (cached != -1) {
        return cached;
    }
    
    long long count = 1; // Current cell is a valid path
    
    for (int i = 0; i < 4; i++) {
        int newRow = row + directions[i][0];
        int newCol = col + directions[i][1];
        
        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
            grid[newRow][newCol] > grid[row][col]) {
            count = (count + dfs(newRow, newCol)) % MOD;
        }
    }
    
    setMemo(row, col, count);
    return count;
}

int countPaths(int** inputGrid, int rows, int cols) {
    grid = inputGrid;
    m = rows;
    n = cols;
    
    // Clear memo table
    memset(memo, 0, sizeof(memo));
    
    long long totalPaths = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            totalPaths = (totalPaths + dfs(i, j)) % MOD;
        }
    }
    
    return totalPaths;
}

int main() {
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    
    int** grid = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        grid[i] = (int*)malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    printf("%d\n", countPaths(grid, rows, cols));
    
    for (int i = 0; i < rows; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*n)

Each cell is processed exactly once due to memoization, and we visit m*n cells

✓ Linear Growth

Space Complexity

O(m*n)

Memoization table stores results for all m*n cells, plus recursion stack

⚡ Linearithmic Space

67.3K Views

High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Memoization (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler