The problem
Given an m × n matrix of integers, return the number of cells in the longest path that moves up, down, left or right, always to a strictly larger value.
Examples
- Input
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
- Output
4
- Input
matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
- Output
4
- Input
matrix = [[1]]
- Output
1
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ matrix[i][j] ≤ 2³¹ − 1
The idea
Draw an arrow from each cell to every larger neighbour. Arrows only go uphill, so they can never loop — the longest path is well defined, and can be found by peeling the matrix in layers, as Kahn’s algorithm does.
Count, for each cell, its smaller neighbours. Cells with none are where paths begin: layer 1. Remove them; every cell whose count drops to 0 is layer 2, and so on. The number of layers is the length of the longest path. (A depth-first search that remembers each cell’s answer works as well, but on a 200 × 200 matrix its recursion can run 40,000 calls deep.)
- Time
- O(m · n)
- Space
- O(m · n)
Solution · every language run against every case
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: rows, cols = len(matrix), len(matrix[0]) moves = ((1, 0), (-1, 0), (0, 1), (0, -1)) # Peel the matrix in layers, as in Kahn's algorithm: a cell's count is how many # neighbours are smaller. Cells with none start a path; removing a layer frees the next. smaller = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): for dr, dc in moves: x, y = r + dr, c + dc if 0 <= x < rows and 0 <= y < cols and matrix[x][y] < matrix[r][c]: smaller[r][c] += 1 layer = [(r, c) for r in range(rows) for c in range(cols) if smaller[r][c] == 0] length = 0 while layer: length += 1 # every cell in this layer ends a path of this many cells nxt = [] for r, c in layer: for dr, dc in moves: x, y = r + dr, c + dc if 0 <= x < rows and 0 <= y < cols and matrix[x][y] > matrix[r][c]: smaller[x][y] -= 1 if smaller[x][y] == 0: nxt.append((x, y)) layer = nxt return length