Finding the Longest Increasing Path in a Matrix Using Python
The problem of finding the longest increasing path in a matrix involves exploring the matrix to determine the maximum length of a sequence where each subsequent number is greater than the previous. This problem can be efficiently addressed using Depth-First Search (DFS) combined with memoization to avoid redundant calculations.
Here is a Python function that implements this approach:
def longestIncreasingPath(matrix):
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = [[-1] * cols for _ in range(rows)]
def dfs(r, c):
if memo[r][c] != -1:
return memo[r][c]
# Directions for moving up, down, left, right
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
max_length = 1 # At least the cell itself
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]:
max_length = max(max_length, 1 + dfs(nr, nc))
memo[r][c] = max_length
return max_length
longest_path = 0
for r in range(rows):
for c in range(cols):
longest_path = max(longest_path, dfs(r, c))
return longest_path
# Example usage
matrix = [
[9, 9, 4],
[6, 6, 8],
[2, 1, 1]
]
print(longestIncreasingPath(matrix)) # Output: 4
Explanation of the Code:
1. Initial Checks: The function first checks if the input matrix is empty or has no columns.
2. Memoization Table: A 2D list memo is created to store the lengths of the longest increasing paths starting from each cell, initialized to -1, indicating that those cells have not been computed yet.
3. DFS Function: The nested dfs function performs a depth-first search from the current cell (r, c). It explores all four possible directions (up, down, left, right) to find adjacent cells with larger values. For each adjacent cell that is part of a valid increasing sequence, the function recursively calls itself and updates the maximum length found.
4. Updating Memoization: The result of each DFS call (the length of the longest increasing path starting from cell (r, c)) is stored in the memo table.
5. Result Calculation: After processing all cells in the matrix, the function returns the longest found path.
Complexity Analysis:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. Each cell is visited once.
- Space Complexity: O(m * n) for the memo table used to store intermediate results.
This implementation efficiently determines the length of the longest increasing path in the matrix, leveraging the power of recursion and memoization.