Description
Find the largest number of cells in a strictly increasing path through a rectangular integer matrix. Moves are horizontal or vertical; equal values cannot extend a path.
Solution
from collections import deque
def longest_increasing_path(matrix):
rows, cols = len(matrix), len(matrix[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
degree = [[0] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
for dr, dc in directions:
x, y = r + dr, c + dc
if 0 <= x < rows and 0 <= y < cols and matrix[x][y] > matrix[r][c]:
degree[r][c] += 1
if degree[r][c] == 0:
queue.append((r, c))
length = 0
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
x, y = r + dr, c + dc
if 0 <= x < rows and 0 <= y < cols and matrix[x][y] < matrix[r][c]:
degree[x][y] -= 1
if degree[x][y] == 0:
queue.append((x, y))
length += 1
return lengthExamples
Example 1
- Input
[[[9,9,4],[6,6,8],[2,1,1]]]- Output
4
1-2-6-9 gives a four-cell increasing path.
Example 2
- Input
[[[1]]]- Output
1
The only cell is a path of length one.
Example 3
- Input
[[[2,2],[2,2]]]- Output
1
Equal values cannot be connected in an increasing path.
Approach
Orient neighbor edges from smaller to larger values. Count each cell's outgoing edges, enqueue all local maxima, and remove one layer at a time while decrementing smaller neighbors' outdegrees. The number of layers equals the longest path length.
Time & space
O(rc) time and O(rc) auxiliary space, where r and c are matrix dimensions.