Problem
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: nums =
[
[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.
Solution
We can use graph dfs traversal start at each node for find the increasing paths. Since we need to find the max length path, we need to explore all the possibilities. This is a time we think of backtracking. We need to explore all the other directions once we tested one direction. At each node, there will be 3 possible directions that have increasing number, for a m x n matrix, we could end up exploring power(3, mn) states for each node. We can cut down the computation with memorization. We remember the longest increasing path for each node, that way, each node only have to be processes once and the cost reduced to O(mn) for each node. Since there are mn nodes total, the time complexity is O(mmnn), the space complexity is O(mn) for the memorization cache.
import java.util.*;
class Solution {
int maxLen = Integer.MIN_VALUE;
int[][] nums =
{
{9,9,4},
{6,6,8},
{2,1,1}
};
int[][] memo = new int[nums.length][nums[0].length];
public static void main(String[] args) {
Solution sol = new Solution();
sol.solve();
System.out.println(sol.maxLen);
}
private void solve() {
for(int row = 0; row < nums.length; row++) {
for(int col = 0; col < nums[0].length; col++) {
memo[row][col] = dfs(row, col);
maxLen = Math.max(maxLen, memo[row][col]);
}
}
}
private int dfs(int row, int col) {
if(memo[row][col] != 0) {
return memo[row][col];
}
int[][] directions = new int[][]{
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int tmpMax = 1;
for(int[] direct: directions) {
int newRow = row + direct[0];
int newCol = col + direct[1];
if(newRow >= 0 && newRow < nums.length && newCol >= 0 && newCol < nums[0].length && nums[row][col] < nums[newRow][newCol]) {
int len = dfs(newRow, newCol);
memo[newRow][newCol] = len;
tmpMax = Math.max(tmpMax, 1 + len);
}
}
return tmpMax;
}
}
