329. Longest Increasing Path in a Matrix LeetCode Solution
In this guide, you will get 329. Longest Increasing Path in a Matrix LeetCode Solution with the best time and space complexity. The solution to Longest Increasing Path in a Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in 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).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]]
Output: 1
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 – 1
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
329. Longest Increasing Path in a Matrix LeetCode Solution in C++
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
int ans = 0;
vector<vector<int>> mem(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = max(ans, dfs(matrix, i, j, INT_MIN, mem));
return ans;
}
private:
// mem[i][j] := the LIP starting from matrix[i][j]
int dfs(const vector<vector<int>>& matrix, int i, int j, int prev,
vector<vector<int>>& mem) {
if (i < 0 || i == matrix.size() || j < 0 || j == matrix[0].size())
return 0;
if (matrix[i][j] <= prev)
return 0;
int& ans = mem[i][j];
if (ans > 0)
return ans;
const int curr = matrix[i][j];
return ans = 1 + max({dfs(matrix, i + 1, j, curr, mem),
dfs(matrix, i - 1, j, curr, mem),
dfs(matrix, i, j + 1, curr, mem),
dfs(matrix, i, j - 1, curr, mem)});
}
}; /* code provided by PROGIEZ */
329. Longest Increasing Path in a Matrix LeetCode Solution in Java
class Solution {
public int longestIncreasingPath(int[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int ans = 0;
// mem[i][j] := the LIP starting from matrix[i][j]
int[][] mem = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j, Integer.MIN_VALUE, mem));
return ans;
}
private int dfs(int[][] matrix, int i, int j, int prev, int[][] mem) {
if (i < 0 || i == matrix.length || j < 0 || j == matrix[0].length)
return 0;
if (matrix[i][j] <= prev)
return 0;
if (mem[i][j] > 0)
return mem[i][j];
final int curr = matrix[i][j];
final int a = dfs(matrix, i + 1, j, curr, mem);
final int b = dfs(matrix, i - 1, j, curr, mem);
final int c = dfs(matrix, i, j + 1, curr, mem);
final int d = dfs(matrix, i, j - 1, curr, mem);
return mem[i][j] = 1 + Math.max(Math.max(a, b), Math.max(c, d));
}
} // code provided by PROGIEZ
329. Longest Increasing Path in a Matrix LeetCode Solution in Python
class Solution:
def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
m = len(matrix)
n = len(matrix[0])
@functools.lru_cache(None)
def dfs(i: int, j: int, prev: int) -> int:
if i < 0 or i == m or j < 0 or j == n:
return 0
if matrix[i][j] <= prev:
return 0
curr = matrix[i][j]
return 1 + max(dfs(i + 1, j, curr),
dfs(i - 1, j, curr),
dfs(i, j + 1, curr),
dfs(i, j - 1, curr))
return max(dfs(i, j, -math.inf) for i in range(m) for j in range(n)) # code by PROGIEZ
