Longest Increasing Path in a Matrix – Solution & 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