LeetCode Solutions Blog

Longest Increasing Path in a Matrix

Number: 329

Difficulty: Hard

Paid? No

Problem Description

Given an m x n matrix of integers, find the length of the longest increasing path in the matrix. From each cell, you may move left, right, up, or down (but not diagonally or outside the matrix bounds). The path must be strictly increasing.

Key Insights

The problem can be modeled as a graph where each cell is a node connected to its neighbors if the neighbor's value is greater.
A Depth First Search (DFS) with memoization is effective to avoid recalculations.
Dynamic Programming (DP) is used to cache the longest path found from each cell.
Since each cell can be a start point, compute DFS for every cell and update the global maximum.

Space and Time Complexity

Time Complexity: O(m * n) – each cell is computed once due to memoization. Space Complexity: O(m * n) – space is used for the memoization cache and recursion stack.

Solution

We solve the problem using a DFS approach combined with memoization to keep track of already computed longest paths from each cell. For each cell in the matrix, a DFS is initiated to explore all four valid directions (up, down, left, right). If a neighboring cell has a larger value, the DFS recurses from that neighbor. The result for each cell is cached in a 2D memoization table, ensuring that each cell is processed only once. After processing all cells, the maximum value in the memo table represents the longest increasing path in the entire matrix.

Code Solutions

# Python implementation for Longest Increasing Path in a Matrix

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Return 0 if matrix is empty
        if not matrix or not matrix[0]:
            return 0
        
        # Dimensions of the matrix
        m, n = len(matrix), len(matrix[0])
        # Create a memoization table (same dimensions as the matrix) initialized to 0
        memo = [[0] * n for _ in range(m)]
        
        # Define the DFS function to explore the matrix
        def dfs(i, j):
            # If result is already computed, return it
            if memo[i][j]:
                return memo[i][j]
            
            # Start with a path length of 1 (the cell itself)
            max_len = 1
            # Define directions: up, down, left, right
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            
            # Explore each direction
            for dx, dy in directions:
                ni, nj = i + dx, j + dy
                # If neighbor is within bounds and its value is greater
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                    length = 1 + dfs(ni, nj)
                    max_len = max(max_len, length)
            
            # Store computed longest length in memoization table
            memo[i][j] = max_len
            return max_len
        
        # Compute the longest increasing path starting from each cell
        longest_path = 0
        for i in range(m):
            for j in range(n):
                longest_path = max(longest_path, dfs(i, j))
        
        return longest_path