Number of Increasing Paths in a Grid — Hard Problem & Solution

From any cell of a grid you may move to an adjacent cell — up, down, left or right — whose value is strictly greater.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix, Depth-First Search, Topological Sort, Memoization
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

From any cell of a grid you may move to an adjacent cell — up, down, left or right — whose value is strictly greater.

Return the number of strictly increasing paths, starting from any cell and of any length (a single cell counts as a path), modulo 10^9 + 7. Two paths differ if they visit a different sequence of cells.

Example 1

Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The four single cells, plus `1 → 3`, `1 → 4`, `3 → 4` and `1 → 3 → 4`.

Example 2

Input: grid = [[1],[2]]
Output: 3
Explanation: Two single cells and `1 → 2`.

Example 3

Input: grid = [[5,5],[5,5]]
Output: 4
Explanation: No move is ever possible, so only the single cells count.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10^5
1 <= grid[i][j] <= 10^5

How to solve Number of Increasing Paths in a Grid

Count paths by their starting cell. A path from a cell is either the cell alone or a step to a strictly greater neighbour followed by a path from there, which gives a clean recurrence.

Approach

Sort the cells by value, largest first.
For each cell, start at 1 and add ways[neighbour] for every strictly greater neighbour.
Accumulate every ways[cell] into the answer, modulo 10^9 + 7.

Why it works

The strict increase forbids cycles, so the recurrence is well founded, and descending value order is a topological order for it: a strictly greater neighbour always comes earlier. That also means no explicit memoisation table is needed beyond ways itself — each cell is computed exactly once.

Complexity

Time — O(m · n · log(m · n))
Space — O(m · n)

Pitfalls

Equal neighbours are not moves; the increase is strict.
Every single cell is a path, which is where the 1 in the recurrence comes from.
Reduce modulo 10^9 + 7 while summing, not only at the end.

Reference solution

Python

from typing import List

def countPaths(grid: List[List[int]]) -> int:
    MOD = 1000000007
    m, n = len(grid), len(grid[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    order = sorted(range(m * n), key=lambda u: -grid[u // n][u % n])
    ways = [0] * (m * n)
    total = 0
    for u in order:
        r, c = divmod(u, n)
        s = 1
        for di, dj in dirs:
            nr, nc = r + di, c + dj
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > grid[r][c]:
                s = (s + ways[nr * n + nc]) % MOD
        ways[u] = s
        total = (total + s) % MOD
    return total

JavaScript

var countPaths = function(grid) {
    var MOD = 1000000007;
    var m = grid.length, n = grid[0].length, i;
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var order = [];
    for (i = 0; i < m * n; i++) order.push(i);
    order.sort(function(a, b) {
        return grid[Math.floor(b / n)][b % n] - grid[Math.floor(a / n)][a % n];
    });
    var ways = [];
    for (i = 0; i < m * n; i++) ways.push(0);
    var total = 0;
    for (var t = 0; t < order.length; t++) {
        var u = order[t];
        var r = Math.floor(u / n), c = u % n;
        var sum = 1;
        for (var k = 0; k < 4; k++) {
            var nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (grid[nr][nc] <= grid[r][c]) continue;
            sum = (sum + ways[nr * n + nc]) % MOD;
        }
        ways[u] = sum;
        total = (total + sum) % MOD;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue