LeetCode 329: Longest Increasing Path In A Matrix — Step-by-Step Visual Trace

Source: Dev.to

Problem Description

Find the length of the longest increasing path in a matrix where you can move in four directions (up, down, left, right) to adjacent cells with strictly increasing values.

Approach

The solution uses depth‑first search (DFS) with memoization:

1. Perform DFS from each cell to explore all possible increasing paths.
2. Store the length of the longest path starting from each cell in a DP (memoization) table to avoid redundant calculations.
3. The answer is the maximum value found in the DP table across all starting positions.

Complexity Analysis

• Time: O(m × n) – each cell is processed once thanks to memoization.
• Space: O(m × n) – for the DP table and recursion stack.

Reference Implementation (Python)

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        # Directions: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        m, n = len(matrix), len(matrix[0])
        dp = [[-1] * n for _ in range(m)]  # memoization table

        def dfs(i: int, j: int) -> int:
            # Return cached result if already computed
            if dp[i][j] != -1:
                return dp[i][j]

            # At least the cell itself
            dp[i][j] = 1

            # Explore neighbors
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    dp[i][j] = max(dp[i][j], 1 + dfs(x, y))

            return dp[i][j]

        max_path = 0
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))

        return max_path

Interactive Visualization

Try it yourself: Open TraceLit and step through every line – built with TraceLit, the visual algorithm tracer for LeetCode practice.