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

Hard — Dynamic Programming | Depth-First Search | Matrix | Memoization

The Problem

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

Uses depth-first search (DFS) with memoization to explore all possible increasing paths from each cell. The algorithm stores computed results in a DP table to avoid redundant calculations and returns the maximum path length found across all starting positions.

Time: O(mn) · Space: O(mn)

Code

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

        # Define directions for moving to neighboring cells: up, down, left, right.
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Function to perform DFS from a given cell (i, j).
        def dfs(i, j):
            # If the result for this cell is already calculated, return it.
            if dp[i][j] != -1:
                return dp[i][j]

            # Initialize the result for this cell to 1 (counting itself).
            dp[i][j] = 1

            # Explore the four neighboring cells.
            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]:
                    # If the neighboring cell has a larger value, perform DFS.
                    dp[i][j] = max(dp[i][j], 1 + dfs(x, y))

            return dp[i][j]

        m, n = len(matrix), len(matrix[0])
        dp = [[-1] * n for _ in range(m)]  # Memoization table to store results.
        max_path = 0

        # Start DFS from each cell in the matrix.
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))

        return max_path

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments