Longest Increasing Path in a Matrix

HardDynamic programming Graphs Topological sort

+10

You get matrix, a grid of whole numbers with m rows and n columns, as a list of rows. A path moves from cell to cell, one step up, down, left or right at a time (no diagonal steps, no wrapping around the edges), and every step must land on a strictly larger value. Return the number of cells on the longest such path. A single cell on its own is a path of 1 cell.

Function

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: the grid of values, as a list of rows of equal length
Returnsinteger: the number of cells on the longest strictly increasing path

Constraints

1 ≤ m, n ≤ 100, where m = matrix.length and n = matrix[i].length
Every row has the same length n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Examples

Input: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Output: 7
Explanation: The path 3, 4, 5, 6, 7, 8, 9 runs down the right column, left along the bottom row, up the middle column and left to the 9 in the corner: 7 cells. The smallest value does worse: from the 1 the best paths are 1, 2, 7, 8, 9 and 1, 6, 7, 8, 9, with 5 cells each.

+18 hidden tests on Submit

Follow-up

Can you also return the cells of one longest path, not only its length?

Solution

Draw an arrow from every cell to each neighbour that holds a larger value. Values rise along every arrow, so no chain of arrows can lead back to where it started: the grid is a directed acyclic graph, and the task is its longest path. In a general graph that question is hopeless for large inputs, but without cycles the longest path from a cell depends only on that cell, so you compute it once per cell and the whole problem drops to O(m × n). Memoised depth first search computes it from the top down; peeling the grid from its peaks, Kahn's algorithm in reverse, computes it from the bottom up.

Follow every increasing path

Correct, but does not finish on the largest tests

Intuition

Start a walk at every cell. From the cell you are on, try each of the four neighbours whose value is larger, and from there keep going the same way until no larger neighbour is left. Count the cells of every walk and keep the largest count.

The walk needs no visited set. Values rise at every step, so the walk can never return to a cell: to stand on it again it would have to come back down to that cell's value. Keep the walks on a stack of (cell, length) entries. Popping an entry ends one walk at that cell, and pushing its larger neighbours extends it.

The method is correct, and hopelessly slow, because walks branch. On a 100 × 100 grid where each value is its row plus its column, every step right or down is a step up, and the walks from the top-left corner alone number more than 10^58. Worse, the walk from any given cell is redone every time another walk passes through it, which is the waste the next approach removes.

Algorithm

For each cell, push (that cell, 1) on a stack.
Pop an entry (cell, length) and update the answer with length.
Push (neighbour, length + 1) for each neighbour inside the grid with a strictly larger value.
Repeat until the stack is empty, then move to the next starting cell.
Return the largest length seen.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Memoised depth first search with your own stack

Intuition

Let best[cell] be the number of cells on the longest increasing path that starts at that cell. The path either ends right there, or its next step goes to a larger neighbour and continues along the longest path from that neighbour. So best[cell] = 1 + max(best[nb]) over the larger neighbours nb, or 1 if there are none. This is safe to reuse because of the acyclic shape: the cells before cell on any path are all smaller, so they can never appear after it, and the best continuation from cell is the same no matter how you arrived. Compute each best once, store it, and the exponential tree of walks collapses to one visit per cell.

In the first example, 9 has no larger neighbour, so best is 1 there. Then 8 gets 2, 7 gets 3, 6 and 2 get 4, 5 and 1 get 5, 4 gets 6, and 3 gets 7, the answer. Each cell looks at its 4 neighbours, so the work is O(m × n).

The natural code is recursive: a function that returns best for a cell, calling itself on each larger neighbour. Its call depth equals the length of the path it follows, and the constraints allow a path through every cell: values that snake back and forth across a 100 × 100 grid make one path of 10,000 cells, while Python stops at 1,000 nested calls by default. The code below runs the recursion itself, so no path is too long for it. Keep a stack of cells and, per cell, how many of its four directions you have tried. Look at the top cell: if it has a direction left, try it, and push the neighbour there when it is larger and not finished yet. When all four are tried, every larger neighbour is finished, so pop the cell and set its best. This is exactly the order a recursive call would follow.

The search needs no "in progress" mark, unlike cycle detection. Each cell on the stack is larger than the one below it, so a larger neighbour of the top cell can never be sitting lower on the stack.

Algorithm

Fill best with 0 (not known yet) and a direction counter with 0 for every cell.
For each cell with best 0, push it on a stack.
Look at the top cell. If it has a direction left, advance its counter and push the neighbour in that direction if it is inside the grid, larger, and not finished.
If all four directions are tried, pop the cell and set best to 1 plus the largest best among its larger neighbours, or 1 if it has none.
Return the largest best.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Peel the grid from its peaks

Intuition

Turn the dynamic programming around and build it from the top values down, the way Kahn's algorithm builds a topological order. Call a cell a peak when no neighbour is larger. A path from a peak cannot move, so it has 1 cell. Remove all the peaks at once: that is layer 1. Now some cells have lost their last larger neighbour, so they are peaks of what is left. Remove them as layer 2, and keep going until the grid is empty. The number of layers is the answer.

Why: a cell lands in layer k exactly when the longest path starting at it has k cells. A cell is removed in the round after its last larger neighbour goes, so its layer is 1 plus the highest layer among its larger neighbours, which is the formula best[cell] = 1 + max(best[nb]) from the previous approach. The deepest layer belongs to the start of a longest path.

On the first example, the only peak is the 9 (its neighbours are 8 and 2). Removing it frees the 8, removing the 8 frees the 7, removing the 7 frees the 2 and the 6, those two free the 1 and the 5, the 5 frees the 4, and the 4 frees the 3. That is 7 layers, and the path 3, 4, 5, 6, 7, 8, 9 climbs through one cell of each.

To find the next layer quickly, count for each cell how many larger neighbours it still has. Removing a cell lowers the count of each strictly smaller neighbour, and a count that reaches 0 puts that neighbour in the next layer. Each cell is removed once and each pair of neighbours is looked at a constant number of times, so the work is O(m × n), with no stack and no recursion.

Algorithm

For every cell, count the neighbours with a larger value.
Put every cell whose count is 0 in the current layer.
While the layer is not empty, add 1 to the layer count. For each cell in it, lower the count of each strictly smaller neighbour, and put a neighbour whose count reaches 0 in the next layer.
Make the next layer the current one and repeat.
Return the layer count.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Pitfalls and edge cases

The bugs here come from the word "strictly", from deep recursion, and from habits carried over from other grid problems.

Comparing with >= instead of >. With two neighbouring 4s, each one counts as a step up from the other, the arrows form a loop, a brute force walks back and forth forever, and a memoised search reads a length that is still being computed.
Recursion on very long paths. A recursive search goes as many calls deep as the path is long, and the constraints allow a path through every cell: values that snake back and forth across a 100 × 100 grid make one path of 10,000 cells, ten times Python's default limit of 1,000 nested calls. Paths that long need an iterative search with your own stack, or a raised recursion limit (sys.setrecursionlimit in Python), and a very high limit can still overflow the interpreter's own stack.
Skipping cells already visited, the way a flood fill does. Reaching a finished cell is not a dead end: its stored length is exactly what the current cell needs. Read it, do not skip it.
Starting only from the smallest value. In the first example the 1 gives 5 cells, but the answer, 7, starts at the 3. The longest path can start at any cell that has no smaller neighbour, and there can be many of those.
Returning 0. Every cell is a path of 1 cell, so a grid of equal values, or a 1 × 1 grid, has answer 1. Start every cell's length at 1, not 0.
In the peeling approach, lowering the count of an equal neighbour. Only a strictly smaller neighbour has lost a larger one.

Frequently asked questions4

What is the time complexity of Longest Increasing Path in a Matrix?

O(m × n) time and O(m × n) space with memoised depth first search or with topological peeling. Each of the m × n cells is finished once and looks at its 4 neighbours a constant number of times, and each method keeps one number per cell. Trying every path from every cell is exponential instead: on a 100 × 100 grid where each value is its row plus its column, more than 10^58 paths leave the top-left corner.

Why does this problem need no visited set?

A path that only climbs can never return to a cell, because it would need to come back down to that cell's value. So the strictly increasing rule already forbids revisits, and the graph of steps has no cycles. That is also why memoisation is safe: the cells before a given cell cannot interfere with the path after it.

Is Longest Increasing Path in a Matrix dynamic programming or a graph problem?

Both. It is the longest path in a directed acyclic graph, which is dynamic programming over a topological order: a cell's answer is 1 plus the best answer among its larger neighbours. Memoised depth first search fills the table in the order the search finishes cells, and topological peeling fills it layer by layer starting from the peaks. Sorting the cells by value from largest to smallest gives a third valid order, at the cost of O(m × n × log(m × n)) for the sort.

How is this different from the longest increasing subsequence?

A subsequence may skip elements and must keep their order, while a path here must step to a touching cell, in any of four directions. The subsequence problem is dynamic programming on a line; this one is dynamic programming on a grid turned into a graph. Both rely on the same fact: a strictly increasing chain can never loop back on itself.

Python

def longestIncreasingPath(matrix):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Expected

Longest Increasing Path in a Matrix

Function

Constraints

Examples

Hints

Solution

Follow every increasing path

Memoised depth first search with your own stack

Peel the grid from its peaks

Pitfalls and edge cases

Frequently asked questions4

Similar problems