Longest Increasing Path In a Matrix 🧠
LeetCode Link: Longest Increasing Path In a Matrix
Difficulty: Hard
Problem Explanation 📝
Problem: LeetCode 329 - Longest Increasing Path in a Matrix
Description: Given an m x n integers matrix, return the length of the longest increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Intuition: To find the longest increasing path in the matrix, we can use dynamic programming. The problem can be broken down into smaller subproblems, where we find the longest increasing path starting from each cell in the matrix.
Approach:
- Create a 2D dp array of the same size as the matrix to store the length of the longest increasing path starting from each cell.
- Initialize the dp array to all zeros, as the minimum path length from any cell is 1 (the cell itself).
- For each cell (i, j) in the matrix, perform a depth-first search (DFS) to find the longest increasing path starting from that cell.
- During the DFS, for each neighboring cell (x, y) of the current cell (i, j) that is within bounds and has a greater value than the current cell, calculate the length of the longest increasing path starting from (x, y) using the DFS, and update the dp array accordingly.
- Return the maximum value in the dp array as the result, which represents the length of the longest increasing path in the matrix.
⌛ Time Complexity: The time complexity is O(m * n), where m and n are the dimensions of the matrix, as we perform a DFS starting from each cell once.
💾 Space Complexity: The space complexity is also O(m * n) as we use a 2D dp array to store the length of the longest increasing path for each cell.
Dynamic Programming:
- Subproblem: The subproblem is finding the longest increasing path starting from each cell in the matrix.
- Recurrence Relation: For each neighboring cell (x, y) of the current cell (i, j) that is within bounds and has a greater value than the current cell, calculate the length of the longest increasing path starting from (x, y) using the DFS, and update the dp array accordingly.
- Base Case: Initialize the dp array to all zeros, as the minimum path length from any cell is 1 (the cell itself).
Solutions 💡
Cpp 💻
class Solution {
public:
int longestIncreasingPath(vector<vector<int>> &matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0)); // dp[i][j] stores the longest increasing path starting at position (i, j)
int longestPath = 0;
// Iterate through each element in the matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Find the longest increasing path starting at position (i, j) and update the longestPath
longestPath = max(longestPath, dfs(matrix, dp, i, j));
}
}
return longestPath; // Return the overall longest increasing path
}
// Helper function to find the longest increasing path starting at position (i, j)
int dfs(vector<vector<int>> &matrix, vector<vector<int>> &dp, int i, int j) {
if (dp[i][j] > 0) {
return dp[i][j]; // If the result is already calculated, return it from the dp array
}
int m = matrix.size();
int n = matrix[0].size();
int longest = 1; // The minimum length is 1, considering the current element
// Check the four neighbors
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (const auto &dir : directions) {
int x = i + dir.first;
int y = j + dir.second;
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
// If the neighbor is within the matrix bounds and has a greater value, calculate the longest path recursively
longest = max(longest, 1 + dfs(matrix, dp, x, y));
}
}
dp[i][j] = longest; // Save the result in the dp array to avoid redundant computations
return longest;
}
};
Python 🐍
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
# Define directions for moving to neighboring cells: up, down, left, right.
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Function to perform DFS from a given cell (i, j).
def dfs(i, j):
# If the result for this cell is already calculated, return it.
if dp[i][j] != -1:
return dp[i][j]
# Initialize the result for this cell to 1 (counting itself).
dp[i][j] = 1
# Explore the four neighboring cells.
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
# If the neighboring cell has a larger value, perform DFS.
dp[i][j] = max(dp[i][j], 1 + dfs(x, y))
return dp[i][j]
m, n = len(matrix), len(matrix[0])
dp = [[-1] * n for _ in range(m)] # Memoization table to store results.
max_path = 0
# Start DFS from each cell in the matrix.
for i in range(m):
for j in range(n):
max_path = max(max_path, dfs(i, j))
return max_path