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 steps up, down, left or right (no diagonals, 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 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, along the bottom row and up the middle column to the 9: 7 cells. From the smallest value, 1, the best paths have 5 cells.

Follow-up

Can you also return the cells of one longest path, along with its length?

Solution

Draw an arrow from every cell to each larger neighbour. Values rise along every arrow, so no chain of arrows can loop: the grid is a directed acyclic graph, and the answer is its longest path. Without cycles, the longest path from a cell depends only on that cell, so you compute it once per cell: O(m × n).

Follow every increasing path

Correct, but does not finish on the largest tests

Intuition

Start a walk at every cell and follow every branch of larger neighbours until none is left; the longest walk is the answer. Values rise at every step, so a walk never returns to a cell and needs no visited set.

The walk from a cell is redone every time another walk passes through it. On a 100 × 100 grid where each value is its row plus its column, every step right or down climbs, and more than 10^58 walks leave the top-left corner.

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 there: 1 + max(best[nb]) over the larger neighbours nb, or 1 if there are none. Storing it is safe because the cells before cell on a path are all smaller and never come after it. In the first example, 9 gets 1, 8 gets 2, 7 gets 3, 6 and 2 get 4, 5 and 1 get 5, 4 gets 6, and 3 gets 7.

A path can pass through all 10,000 cells, too deep for recursion, so keep your own stack. The top cell tries its next direction and pushes a larger neighbour that is not finished. Once all four are tried, pop it and set its best. No "in progress" mark is needed: each cell on the stack is larger than the one below it.

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.
At the top cell, advance its counter and push that neighbour if it is inside the grid, larger, and not finished.
After four directions, pop the cell and set best to 1 plus the largest best among its larger neighbours, or 1.
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

Build the same table from the top values down, like Kahn's topological sort. A peak, a cell with no larger neighbour, starts a path of 1 cell: layer 1. Remove all peaks; cells that lost their last larger neighbour are the next layer. Repeat until the grid is empty. A cell goes one round after its last larger neighbour, so its layer equals its best, and the number of layers is the answer. In the first example the layers are 9; 8; 7; 2 and 6; 1 and 5; 4; 3.

Count for each cell how many larger neighbours remain. Removing a cell lowers the count of each strictly smaller neighbour, and a count of 0 puts it in the next layer. Each cell is removed once: O(m × n), with no stack.

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

Comparing with >= instead of >. With two neighbouring 4s, a brute force walks back and forth forever, and a memoised search reads a length still being computed.
Recursing in Python. Values that snake across a 100 × 100 grid make a path of 10,000 cells, ten times the default limit of 1,000 calls.
Skipping finished cells as a flood fill would. Their stored length is exactly what the current cell needs.
Starting only from the smallest value. In the first example the 1 gives 5 cells, but the answer, 7, starts at the 3.
Starting lengths at 0. A grid of equal values has answer 1.

Frequently asked questions3

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

O(m × n) time and space, with memoised depth first search or with peeling: each cell is finished once and looks at its 4 neighbours. Trying every path from every cell is exponential.

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. Sorting the cells from largest to smallest value gives another 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 but keeps their order; a path here must step to a touching cell, in any of four directions. In both, a strictly increasing chain can never loop back on itself.

def longestIncreasingPath(matrix):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems