{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Longest Increasing Path in a Matrix – Solution & Complexity

Interview solutions
/
Longest Increasing Path in a Matrix

Solution Walkthrough

1. See the hidden DAG

  • Draw a directed edge from each cell to any orthogonal neighbor with a larger value.
  • Because values must strictly increase along every move, cycles are impossible: you can never come back to an earlier value on the same path.

2. Brute-force baseline

  • Start a DFS from every cell and try every increasing continuation.
  • Without caching, many suffix paths are recomputed over and over, so the naive search becomes exponential in the worst case.

3. Peel topological layers

  • Count each cell's outdegree: how many larger neighbors it can move to. Cells with outdegree 0 are local peaks.
  • Put every peak in a queue. Removing one topological layer shortens the longest path by one step from the back.
  • When a peak is removed, decrement the outdegree of its smaller neighbors. Any neighbor whose outdegree falls to 0 becomes part of the next layer. The number of layers processed is exactly the longest increasing path length.

4. Final solution (all languages)

A topological BFS over the increasing-value DAG avoids recursion depth issues while still achieving optimal complexity.

from collections import deque

def longest_increasing_path(matrix: list[list[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    outdegree = [[0] * cols for _ in range(rows)]

    for row in range(rows):
        for col in range(cols):
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[row][col]:
                    outdegree[row][col] += 1

    queue = deque((row, col) for row in range(rows) for col in range(cols) if outdegree[row][col] == 0)
    length = 0

    while queue:
        length += 1
        for _ in range(len(queue)):
            row, col = queue.popleft()
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[row][col]:
                    outdegree[nr][nc] -= 1
                    if outdegree[nr][nc] == 0:
                        queue.append((nr, nc))

    return length

5. Why this matches the answer

  • Every valid increasing path ends at some peak. Removing all peaks strips away exactly the last step of every remaining path.
  • After one layer is removed, the cells that become new peaks are exactly the cells whose best path length is now one shorter.
  • Therefore the number of BFS layers equals the length of the longest increasing path.

FAQ

See also

Practice Longest Increasing Path in a Matrix online (run code in the browser)Pacific Atlantic Water Flow solution (medium)Cheapest Flights Within K Stops solution (medium)Clone Graph solution (medium)Number of Islands solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?