Solution: Longest Increasing Path in a Matrix
source link: https://dev.to/seanpgallivan/solution-longest-increasing-path-in-a-matrix-4o5f
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Leetcode Solutions (90 Part Series)
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #329 (Hard): Longest Increasing Path in a Matrix
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given an
m x nintegersmatrix, return the length of the longest increasing path inmatrix.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).
Examples:
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]. Visual:
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. Visual:
Example 3:
Input: matrix = [[1]] Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The naive approach here would be to iterate through the entire matrix (M) and attempt to traverse down each branching path, but we'd find ourselves repeating the same stretches of path over and over again.
Rather than having to repeat subproblems, we should cache those completed subproblem results for future use in a memoization data structure (memo). Since the paths can branch at any location, we should also use a depth-first search (DFS) approach with recursion to efficiently traverse the paths.
(Note: It is possible to use a bottom-up dynamic programming (DP) approach here as well, but since there's no convenient fixed point bottom location, we'd have to use a max-heap priority queue in order to traverse M in proper bottom-up order. That would push the time complexity to O(N * M * log(N * M)), so the memoization code is more efficient.)
So we can just iterate through every cell in M and run our recursive helper (dfs) which will fill in values in memo as it returns. For a given cell, if that cell's solution has already been found, we can return it, otherwise we'll take the best result of each of the four possible path directions.
Once the main iteration has finished, the highest value in memo will be our answer. so we should return it.
Implementation:
Python can make good use of @lru_cache instead of having to manually create a memoization data structure.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var longestIncreasingPath = function(M) {
let ylen = M.length, xlen = M[0].length, ans = 0,
memo = Array.from({length: ylen}, el => new Uint16Array(xlen))
const dfs = (y, x) => {
if (memo[y][x]) return memo[y][x]
let val = M[y][x]
memo[y][x] = 1 + Math.max(
y < ylen - 1 && M[y+1][x] < val ? dfs(y+1,x) : 0,
y > 0 && M[y-1][x] < val ? dfs(y-1,x) : 0,
x < xlen - 1 && M[y][x+1] < val ? dfs(y,x+1) : 0,
x > 0 && M[y][x-1] < val ? dfs(y,x-1) : 0)
return memo[y][x]
}
for (let i = 0; i < ylen; i++)
for (let j = 0; j < xlen; j++)
ans = Math.max(ans, dfs(i, j))
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def longestIncreasingPath(self, M: List[List[int]]) -> int:
ylen, xlen = len(M), len(M[0])
@lru_cache(maxsize=None)
def dfs(y, x):
val = M[y][x]
return 1 + max(
dfs(y+1,x) if y < ylen - 1 and val > M[y+1][x] else 0,
dfs(y-1,x) if y > 0 and val > M[y-1][x] else 0,
dfs(y,x+1) if x < xlen - 1 and val > M[y][x+1] else 0,
dfs(y,x-1) if x > 0 and val > M[y][x-1] else 0)
return max(dfs(y, x) for y in range(ylen) for x in range(xlen))
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int longestIncreasingPath(int[][] M) {
int ylen = M.length, xlen = M[0].length, ans = 0;
int[][] memo = new int[ylen][xlen];
for (int i = 0; i < ylen; i++)
for (int j = 0; j < xlen; j++)
ans = Math.max(ans, dfs(i,j,M,memo));
return ans;
}
public int dfs(int y, int x, int[][] M, int[][] memo) {
if (memo[y][x] > 0) return memo[y][x];
int val = M[y][x];
memo[y][x] = 1 + Math.max(
Math.max(y < M.length - 1 && M[y+1][x] < val ? dfs(y+1,x,M,memo) : 0,
y > 0 && M[y-1][x] < val ? dfs(y-1,x,M,memo) : 0),
Math.max(x < M[0].length - 1 && M[y][x+1] < val ? dfs(y,x+1,M,memo) : 0,
x > 0 && M[y][x-1] < val ? dfs(y,x-1,M,memo) : 0));
return memo[y][x];
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int memo[200][200];
int longestIncreasingPath(vector<vector<int>>& M) {
int ylen = M.size(), xlen = M[0].size(), ans = 0;
for (int i = 0; i < ylen; i++)
for (int j = 0; j < xlen; j++)
ans = max(ans, dfs(i,j,M));
return ans;
}
int dfs(int y, int x, vector<vector<int>>& M) {
if (memo[y][x]) return memo[y][x];
int val = M[y][x];
memo[y][x] = 1 + max(
max(y < M.size() - 1 && M[y+1][x] < val ? dfs(y+1,x,M) : 0,
y > 0 && M[y-1][x] < val ? dfs(y-1,x,M) : 0),
max(x < M[0].size() - 1 && M[y][x+1] < val ? dfs(y,x+1,M) : 0,
x > 0 && M[y][x-1] < val ? dfs(y,x-1,M) : 0));
return memo[y][x];
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK