DSA Longest Increasing Path in a Matrix
The longest increasing path in a matrix is the longest chain of neighbouring cells with strictly rising values. A depth-first search with a memory table finds each cell's best chain once and reuses it.
The problem
The longest increasing path in a matrix is the longest chain of neighbouring cells with strictly rising values. Neighbouring means sharing a side. Diagonal steps do not count.
The input is a grid of numbers. The output is the length of the longest such chain. The chain may start at any cell and turn in any direction, as long as every step rises.
The cases used in this article
grid_a = [
[9, 9, 4],
[6, 6, 8],
[2, 1, 1],
]
grid_b = [
[3, 4, 5],
[3, 2, 6],
[2, 2, 1],
]
for name, grid in [("Grid A", grid_a), ("Grid B", grid_b)]:
print(name, "- cells:", len(grid) * len(grid[0]), "- expected longest length: 4")Both grids answer four. Grid A reaches it through the values 1, 2, 6 and 9. Grid B reaches it through 3, 4, 5 and 6 along its top row and right column.
Intuition: always climb to the largest neighbour fails
The first idea starts somewhere low and always steps to the largest larger neighbour. The largest step feels like the fastest climb. It can also end the chain at once.
A large neighbour may be a dead end. Its own neighbours may all be smaller or equal. A smaller first step can keep the chain alive for much longer.
The greedy climb against the best chain
grid = [
[1, 9, 0],
[2, 0, 0],
[3, 4, 5],
]
def greedy_from(r, c):
path = [grid[r][c]]
while True:
best = None
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < 3 and 0 <= nc < 3 and grid[nr][nc] > grid[r][c]:
if best is None or grid[nr][nc] > grid[best[0]][best[1]]:
best = (nr, nc)
if best is None:
return path
r, c = best
path.append(grid[r][c])
print("greedy path from the 1:", greedy_from(0, 0))
print("best chain from the 1: [1, 2, 3, 4, 5], length 5")The greedy climb takes the 9 and stops at length two. The patient first step down earns a chain of five. Local greed spends the chain's future on one big step.
Brute force: explore every rising chain from every cell
The brute force starts a search at every cell. Each search steps to every larger neighbour. It returns one plus the best result among those steps.
No result is stored. Two different chains that pass through the same cell each pay for that cell's whole search again. The repeat work grows with every shared cell.
The unstored search, counted
calls = 0
def best_from(grid, r, c):
global calls
calls += 1
rows, cols = len(grid), len(grid[0])
best = 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
best = max(best, 1 + best_from(grid, nr, nc))
return best
grid_b = [
[3, 4, 5],
[3, 2, 6],
[2, 2, 1],
]
calls = 0
answer = max(best_from(grid_b, r, c) for r in range(3) for c in range(3))
print("Grid B answer:", answer)
print("search calls:", calls, "- cells in grid: 9")Nine cells produce 23 calls. Each call is honest work done again. The fix is to remember a finished cell's answer, which the next section adds.
The optimal solution: a depth-first search with a memory table
Memoisation stores each cell's best chain length after one search. A later visit reads the stored value instead of searching again. The memory table is the state.
Arrows between cells point from each cell to its larger neighbours. Values strictly rise along every arrow, so no arrow cycle can exist. A search along the arrows therefore always ends.
The memoised search on every case
def longest_path(grid):
if not grid or not grid[0]:
return 0, [], {}
rows, cols = len(grid), len(grid[0])
memory = {}
def best_from(r, c):
if (r, c) in memory:
return memory[(r, c)]
best = 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
best = max(best, 1 + best_from(nr, nc))
memory[(r, c)] = best
return best
start, best = None, 0
for r in range(rows):
for c in range(cols):
length = best_from(r, c)
if length > best:
best = length
start = (r, c)
path = []
cell = start
while cell is not None:
path.append(grid[cell[0]][cell[1]])
follow = None
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = cell[0] + dr, cell[1] + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[cell[0]][cell[1]]:
if memory[(nr, nc)] == memory[cell] - 1:
follow = (nr, nc)
break
cell = follow
return best, path, memory
grid_a = [
[9, 9, 4],
[6, 6, 8],
[2, 1, 1],
]
grid_b = [
[3, 4, 5],
[3, 2, 6],
[2, 2, 1],
]
for name, grid, expected in [("Grid A", grid_a, 4), ("Grid B", grid_b, 4)]:
best, path, memory = longest_path(grid)
print(name, "- length:", best, "expected:", expected, "match:", best == expected, "- one longest path:", path, "- cells stored:", len(memory))Both cases pass. The stored count equals the cell count on each grid. Every cell was computed exactly once, and every other visit was a lookup.
Walkthrough: the memory table for Grid B
The walkthrough runs the memoised search on Grid B. It then prints the stored length for every cell in grid order. Each entry answers the chain question for its own cell.
The largest entry sits at the start of the best chain. Following entries that drop by exactly one rebuilds a longest path. The printed values show each step of that follow.
Stored chain lengths and the rebuilt path
def longest_path(grid):
if not grid or not grid[0]:
return 0, [], {}
rows, cols = len(grid), len(grid[0])
memory = {}
def best_from(r, c):
if (r, c) in memory:
return memory[(r, c)]
best = 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
best = max(best, 1 + best_from(nr, nc))
memory[(r, c)] = best
return best
start, best = None, 0
for r in range(rows):
for c in range(cols):
length = best_from(r, c)
if length > best:
best = length
start = (r, c)
path = []
cell = start
while cell is not None:
path.append(grid[cell[0]][cell[1]])
follow = None
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = cell[0] + dr, cell[1] + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[cell[0]][cell[1]]:
if memory[(nr, nc)] == memory[cell] - 1:
follow = (nr, nc)
break
cell = follow
return best, path, memory
grid_b = [
[3, 4, 5],
[3, 2, 6],
[2, 2, 1],
]
best, path, memory = longest_path(grid_b)
for r in range(3):
print("memory row", r, [memory[(r, c)] for c in range(3)])
print("longest length:", best)
print("rebuilt path:", path)The top left cell stores four. Its right neighbour stores three, and the chain continues down the stored gradient. The path 3, 4, 5, 6 is read straight off the table.
Complexity
The memoised search computes each cell once, and each computation checks at most four neighbours, so its time is O(rows times cols). The memory table stores one length per cell, so its space is also O(rows times cols).
The unstored search has no such bound from the cell count. Its calls multiply along shared chains. The counts below use grids whose values rise in a simple pattern.
Unstored calls against memoised cells
calls = 0
def best_from(grid, r, c):
global calls
calls += 1
rows, cols = len(grid), len(grid[0])
best = 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
best = max(best, 1 + best_from(grid, nr, nc))
return best
for n in [2, 3, 4]:
grid = [[r * n + c for c in range(n)] for r in range(n)]
calls = 0
answer = max(best_from(grid, r, c) for r in range(n) for c in range(n))
print("grid", n, "x", n, "- answer:", answer, " unstored calls:", calls, " memoised cells:", n * n)The calls pass the cell count immediately and keep multiplying. The memoised count never moves. It is pinned to the grid size by construction.
Edge cases and pitfalls
A single cell is a chain of length one. A grid where every value is equal also answers one everywhere. Equal neighbours give no arrow, because the rise must be strict.
Letting equal neighbours link is the classic pitfall. The chain could then bounce between equal cells. The strict greater-than test is what keeps the arrows acyclic and the search finite.
Edge cases, run
def longest_path(grid):
if not grid or not grid[0]:
return 0, [], {}
rows, cols = len(grid), len(grid[0])
memory = {}
def best_from(r, c):
if (r, c) in memory:
return memory[(r, c)]
best = 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:
best = max(best, 1 + best_from(nr, nc))
memory[(r, c)] = best
return best
start, best = None, 0
for r in range(rows):
for c in range(cols):
length = best_from(r, c)
if length > best:
best = length
start = (r, c)
path = []
cell = start
while cell is not None:
path.append(grid[cell[0]][cell[1]])
follow = None
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = cell[0] + dr, cell[1] + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[cell[0]][cell[1]]:
if memory[(nr, nc)] == memory[cell] - 1:
follow = (nr, nc)
break
cell = follow
return best, path, memory
print("empty grid:", longest_path([])[0])
print("single cell:", longest_path([[7]])[:2])
print("all equal:", longest_path([[5, 5], [5, 5]])[:2])
print("falling row:", longest_path([[4, 3, 2, 1]])[:2])
print("rising row:", longest_path([[1, 2, 3, 4]])[:2])The falling row still answers four. Its chain runs from right to left, against the reading order. Direction is free in this problem, and only the rise matters.
Exercise
Why can the increasing arrows in this lesson never form a cycle?