Longest Increasing Path In A Matrix - Leetcode Solution

The Longest Increasing Path In A Matrix problem on LeetCode is a dynamic programming problem that asks you to find the length of the longest increasing path in a given matrix. An increasing path is a path in which each cell is greater than the cell before it. The path can start from any cell in the matrix and can move in any of the four directions (up, down, left, or right).

Here is a detailed solution for this problem with step-by-step explanation.

Step 1: Understand the problem statement The problem statement is asking us to find the length of the longest increasing path in a given matrix. We can move in any of the four directions from a cell and the path can start from any cell in the matrix.

Step 2: Approach We can solve this problem using dynamic programming. We will start by creating a DP matrix of the same size as the input matrix to store the longest path length from each cell. We will then iterate through each cell in the matrix and use a recursive DFS approach to find the longest increasing path from that cell.

Step 3: Pseudo code The pseudo code for the solution is as follows:

Initialize a DP matrix of the same size as the input matrix to store the longest path length from each cell Define a recursive DFS function that takes the matrix, the current cell coordinates, and the DP matrix as input If the DP matrix contains a calculated value for the current cell, return that value Set the longest path length from the current cell to 1 For each of the four neighboring cells, if the neighbor is greater than the current cell, recursively call the DFS function on that neighbor and add 1 to the returned value Set the longest path length from the current cell to the maximum path length from its neighbors Update the DP matrix with the calculated longest path length for the current cell Return the longest path length from the current cell

Loop through each cell in the matrix and call the recursive DFS function to find the longest increasing path from that cell Return the maximum path length found

Step 4: Code implementation

In the code below, we have created a class Solution with a single function longestIncreasingPath which takes a matrix as input and returns the length of the longest increasing path in the matrix.

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

    # Initialize a DP matrix of the same size as the input matrix to store the longest path length from each cell
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]

    # Define a recursive DFS function that takes the matrix, the current cell coordinates, and the DP matrix as input
    def dfs(x, y):
        # If the DP matrix contains a calculated value for the current cell, return that value
        if dp[x][y]:
            return dp[x][y]

        # Set the longest path length from the current cell to 1
        path = 1

        # For each of the four neighboring cells, if the neighbor is greater than the current cell,
        # recursively call the DFS function on that neighbor and add 1 to the returned value
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                path = max(path, dfs(nx, ny) + 1)

        # Set the longest path length from the current cell to the maximum path length from its neighbors
        dp[x][y] = path

        # Return the longest path length from the current cell
        return path

    # Loop through each cell in the matrix and call the recursive DFS function to find the longest increasing path from that cell
    ans = 0
    for i in range(m):
        for j in range(n):
            ans = max(ans, dfs(i, j))

    # Return the maximum path length found
    return ans

Step 5: Test the solution We can test our solution with some sample test cases:

assert(Solution().longestIncreasingPath([ [9,9,4], [6,6,8], [2,1,1] ]) == 4)

assert(Solution().longestIncreasingPath([ [3,4,5], [3,2,6], [2,2,1] ]) == 4)

The above test cases pass successfully.

Step 6: Time complexity analysis We are iterating through each cell in the matrix once and for each cell, we perform a recursive DFS operation on its neighbors. The max length of the path is limited by the number of cells in the matrix. So, the worst-case time complexity of the algorithm will be O(n^2 * 4^n), where n is the number of cells in the matrix. However, in practice, the time complexity of this algorithm is much lower due to the memoization technique used to avoid duplicate computations.

Step 7: Space complexity analysis We are using a DP matrix of the same size as the input matrix to store the longest path length from each cell. So, the space complexity of the algorithm is O(n^2), where n is the number of cells in the matrix.

1