Number of Increasing Paths in a Grid

Hard
955.

Number of Increasing Paths in a Grid

Number of Increasing Paths in a Grid is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countPaths = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Increasing Paths in a Grid — Problem & Solution

Number of Increasing Paths in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Increasing Paths in a Grid is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Amazon, Google and Adobe interviews.

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

Hints for Number of Increasing Paths in a Grid

  1. Hint 1

    Let ways[cell] be the number of increasing paths starting at that cell.

  2. Hint 2

    Then ways[cell] = 1 + Σ ways[neighbour] over strictly greater neighbours.

  3. Hint 3

    Process the cells in decreasing order of value so every neighbour is already finished.

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

  1. Sort the cells by value, largest first.
  2. For each cell, start at 1 and add ways[neighbour] for every strictly greater neighbour.
  3. 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

Java

public static int countPaths(int[][] grid) {
    final int MOD = 1000000007;
    int m = grid.length, n = grid[0].length;
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    Integer[] order = new Integer[m * n];
    for (int i = 0; i < m * n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> grid[b / n][b % n] - grid[a / n][a % n]);
    long[] ways = new long[m * n];
    long total = 0;
    for (int u : order) {
        int r = u / n, c = u % n;
        long sum = 1;
        for (int k = 0; k < 4; k++) {
            int 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 (int) total;
}

C++

int countPaths(vector<vector<int>>& grid) {
    const long long MOD = 1000000007;
    int m = (int) grid.size(), n = (int) grid[0].size();
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    vector<int> order(m * n);
    for (int i = 0; i < m * n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) {
        return grid[a / n][a % n] > grid[b / n][b % n];
    });
    vector<long long> ways(m * n, 0);
    long long total = 0;
    for (int u : order) {
        int r = u / n, c = u % n;
        long long sum = 1;
        for (int k = 0; k < 4; k++) {
            int 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 (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming