Write a Python function to find the longest increasing subsequence in a matrix.
PaulAnd
Posted by PaulAnd
Last Updated: August 28, 2024
Python Matrix
Finding the Longest Increasing Subsequence in a Matrix
The problem of finding the longest increasing subsequence (LIS) in a matrix involves identifying the longest path of increasing numbers starting from any cell. The path can move in any of the eight possible directions: horizontally, vertically, or diagonally. Here's a Python function that implements a depth-first search (DFS) approach with memoization to efficiently find the longest increasing subsequence in a given matrix.
Python Implementation
def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    dp = [[-1 for _ in range(cols)] for _ in range(rows)]

    # Directions for moving up, down, left, right, and the four diagonals
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, 1), (-1, 1), (1, -1)]

    def dfs(r, c):
        if dp[r][c] != -1:  # Return already computed result
            return dp[r][c]

        max_length = 1  # At least the cell itself is an increasing path
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                path_length = 1 + dfs(nr, nc)
                max_length = max(max_length, path_length)

        dp[r][c] = max_length  # Memorize the result
        return max_length

    longest_path = 0
    for i in range(rows):
        for j in range(cols):
            longest_path = max(longest_path, dfs(i, j))

    return longest_path

# Example Usage
matrix = [
    [9, 6, 5],
    [5, 6, 8],
    [6, 2, 3]
]

print(longestIncreasingPath(matrix))  # Output will be the length of the LIS
Explanation of the Function
1. Initialization: - Check if the input matrix is valid. If not, return 0. - Define the dimensions of the matrix and create a memoization table dp, initialized with -1 to track computed longest paths. 2. Direction Array: - Define an array directions that contains the possible movements (up, down, left, right, and diagonals). 3. Depth-First Search (DFS): - The dfs function computes the longest increasing path starting from cell (r, c). - Check if the value at dp[r][c] is already computed. - Initialize max_length to 1, considering the cell itself as a starting path. - For each direction, calculate the new cell (nr, nc). If this cell is within bounds and has a greater value than the current cell, recursively call dfs from that cell and update the max_length. 4. Post-Processing: - Loop through each cell in the matrix. For each cell, invoke dfs and keep track of the longest path found. 5. Output: - Return the length of the longest increasing path found across the entire matrix. This approach efficiently finds the longest increasing subsequence in a matrix utilizing DFS and memoization, ensuring that each cell is computed only once, leading to a time complexity of \(O(n \times m)\), where \(n\) is the number of rows and \(m\) is the number of columns in the matrix.
Default Image