LeetCode 329: Longest Increasing Path in a Matrix Solution in Python – A Step-by-Step Guide

What Is LeetCode 329: Longest Increasing Path in a Matrix?

In LeetCode 329: Longest Increasing Path in a Matrix, you’re given an m x n integer matrix, and your task is to find the length of the longest path where each step moves to a strictly greater value (up, down, left, or right). For example, with matrix = [[9,9,4],[6,6,8],[2,1,1]], the longest path is 4 (1->2->6->9). This problem tests your ability to navigate a grid as a directed acyclic graph (DAG), connecting to concepts in LeetCode 200: Number of Islands.

Problem Statement

• Input: An m x n integer matrix matrix.
• Output: An integer—the length of the longest increasing path.
• Rules:
• Moves: up, down, left, right (no diagonals).
• Each step must increase (matrix[next] > matrix[curr]).
• Path can start anywhere.

Constraints

• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 2³¹ - 1

Examples

• Input: [[9,9,4],[6,6,8],[2,1,1]]
• Output: 4 (Path: 1->2->6->9)
• Input: [[3,4,5],[3,2,6],[2,2,1]]
• Output: 4 (Path: 3->4->5->6)
• Input: [[1]]
• Output: 1 (Single cell)

Understanding the Problem: Finding the Longest Climb

To solve LeetCode 329: Longest Increasing Path in a Matrix in Python, we need to find the longest sequence of increasing values in the matrix, moving only to adjacent cells. A naive approach—trying all paths from each cell—is exponential in time, impractical for 200x200 grids. Instead, we’ll use:

• Best Solution (DFS with Memoization): O(m*n) time, O(m*n) space—fast and efficient.
• Alternative Solution (Topological Sort): O(m*n) time, O(m*n) space—graph-based but complex.

Let’s start with the DFS with memoization solution, explained in a beginner-friendly way.

Best Solution: DFS with Memoization

Why This Is the Best Solution

The DFS with memoization approach is the top choice for LeetCode 329 because it’s efficient—O(mn) time, O(mn) space—and elegantly solves the problem by exploring paths while caching results. It treats the matrix as a DAG, using depth-first search to find the longest path from each cell, memoizing to avoid recomputation. It’s like hiking with a map that remembers your best routes—smart and quick!

How It Works

Think of this as a path-finding adventure:

• Step 1: Define DFS:
• For each cell, explore 4 directions if value increases.
• Return longest path length from that cell.
• Step 2: Memoize:
• Cache results in a dp array to reuse paths.
• Step 3: Explore All Starts:
• Run DFS from every cell, track global max.
• Step 4: Why It Works:
• Increasing condition ensures no cycles (DAG).
• Memoization makes each cell O(1) after first visit.

It’s like mapping every trail in one go!

Step-by-Step Example

Example: matrix = [[9,9,4],[6,6,8],[2,1,1]]

• Init: dp = [[0]*3]*3, max_len = 0
• DFS(2,0)=2:
• Down: None, Left: None, Right: 1->DFS(2,1)=1, Up: 6->DFS(1,0)=2
• dp[2][0] = 1 + max(1, 2) = 3
• DFS(1,0)=6:
• Down: 2->3, Left: None, Right: 6, Up: 9->DFS(0,0)=1
• dp[1][0] = 1 + 3 = 4
• Max Length: 4 (Path: 1->2->6->9)
• Result: 4

Code with Detailed Line-by-Line Explanation

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

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

        def dfs(i, j):
            if dp[i][j]:  # If already computed
                return dp[i][j]

            max_len = 1  # Base case: current cell
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if (0 <= ni < m and 0 <= nj < n and 
                    matrix[ni][nj] > matrix[i][j]):
                    max_len = max(max_len, 1 + dfs(ni, nj))
            dp[i][j] = max_len
            return max_len

        # Explore from each cell
        max_path = 0
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))

        return max_path

• Lines 3-8: Handle empty case, initialize dp and directions.
• Lines 10-20: DFS:
• Return cached result if exists.
• Explore 4 directions, recurse if increasing.
• Cache longest path from (i,j).
• Lines 23-26: Try all starting points, track max.
• Time Complexity: O(m*n)—each cell visited once.
• Space Complexity: O(m*n)—dp array.

This is like a path-finding mountaineer—swift and sharp!

Alternative Solution: Topological Sort

Why an Alternative Approach?

The topological sort approach—O(mn) time, O(mn) space—treats the matrix as a DAG, using indegree counts and BFS to process nodes in order, computing longest paths. It’s more graph-theoretical and complex, but insightful for DAG problems. It’s like mapping the terrain’s flow—detailed and structured!

How It Works

Process as a DAG:

• Step 1: Build graph with indegrees (nodes pointing to larger neighbors).
• Step 2: BFS from leaves (indegree 0):
• Update path lengths as you dequeue.
• Step 3: Track max path length.

Step-by-Step Example

Example: matrix = [[1,2],[3,4]]

• Graph: 1->2, 1->3, 2->4, 3->4
• Indegree: 1:0, 2:1, 3:1, 4:2
• BFS:
• Start 1: Path=1, Update 2:1, 3:1
• Process 2: Path=2, Update 4:2
• Process 3: Path=2, Update 4:3
• Process 4: Path=3
• Result: 3 (1->3->4)

Code for Topological Sort Approach

Copy codefrom collections import deque

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        indegree = [[0] * n for _ in range(m)]
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        # Build indegree (count incoming edges)
        for i in range(m):
            for j in range(n):
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if (0 <= ni < m and 0 <= nj < n and 
                        matrix[ni][nj] > matrix[i][j]):
                        indegree[ni][nj] += 1

        # BFS from leaves
        queue = deque()
        dp = [[1] * n for _ in range(m)]  # Path length from each cell
        for i in range(m):
            for j in range(n):
                if indegree[i][j] == 0:
                    queue.append((i, j))

        max_len = 1
        while queue:
            i, j = queue.popleft()
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if (0 <= ni < m and 0 <= nj < n and 
                    matrix[ni][nj] > matrix[i][j]):
                    indegree[ni][nj] -= 1
                    if indegree[ni][nj] == 0:
                        dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1)
                        queue.append((ni, nj))
                        max_len = max(max_len, dp[ni][nj])

        return max_len

• Time Complexity: O(m*n)—process each cell once.
• Space Complexity: O(m*n)—indegree and dp arrays.

It’s a graph-traversing climber—intricate but thorough!

Comparing the Two Solutions

• DFS with Memoization (Best):
• Pros: O(m*n) time, O(m*n) space, simpler and faster in practice.
• Cons: Recursive logic.
• Topological Sort (Alternative):
• Pros: O(m*n) time, O(m*n) space, graph-theoretic insight.
• Cons: More complex setup.

DFS wins for elegance.

Additional Examples and Edge Cases

• [[1,2]]: 2.
• [[5]]: 1.
• [[1,1]]: 1.

Both handle these well.

Complexity Breakdown

• DFS with Memoization: Time O(m*n), Space O(m*n).
• Topological Sort: Time O(m*n), Space O(m*n).

DFS is the practical choice.

Key Takeaways

• DFS with Memoization: Climb and cache—efficient!
• Topological Sort: Order the ascent—deep!
• Python: Grids and recursion shine—see [Python Basics](/python/basics).
• Paths: Increasing steps unlock length.

Final Thoughts: Ascend the Matrix

LeetCode 329: Longest Increasing Path in a Matrix in Python is a grid-traversal masterpiece. DFS with memoization offers speed and simplicity, while topological sort provides a graph-based view. Want more matrix challenges? Try LeetCode 200: Number of Islands or LeetCode 542: 01 Matrix. Ready to climb? Head to Solve LeetCode 329 on LeetCode and find that longest path today!