Problem Explanation

In this problem, we are given a two-dimensional integer matrix, and we are asked to find the length of the longest increasing path. We can move to four directions around a cell (left, right, up, down), but movement across the diagonal or outside the boundary of the matrix is not allowed.

For example, consider the following matrix:

[ [9,9,4], [6,6,8], [2,1,1] ]

In this matrix, the longest increasing path is [1, 2, 6, 9], so the answer is 4.

Approach

The problem can be solved using Depth-first search (DFS) and memoization. DFS is an algorithm for traversing or searching tree data structure, starting at root and exploring as far as possible along each branch before backtracking. Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and reusing them when the same inputs occur again.

Python solution

1
2python
3class Solution:
4    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
5        if not matrix: return 0
6        m, n, dp = len(matrix), len(matrix[0]), {}
7        def dfs(x, y):
8            if (x, y) in dp: return dp[(x, y)]
9            dp[(x, y)] = 1 + max(
10                dfs(x - 1, y) if x and matrix[x][y] < matrix[x - 1][y] else 0,
11                dfs(x + 1, y) if x < m - 1 and matrix[x][y] < matrix[x + 1][y] else 0,
12                dfs(x, y - 1) if y and matrix[x][y] < matrix[x][y - 1] else 0,
13                dfs(x, y + 1) if y < n - 1 and matrix[x][y] < matrix[x][y + 1] else 0)
14            return dp[(x, y)]
15        return max(dfs(x, y) for x in range(m) for y in range(n))

In this Python solution, we first check if the matrix does not exist, return 0. If the matrix exist, we start a depth-first search from every cell, and keep a record of the maximum length of the increasing path we've seen so far in variable dp. For all neighboring cells that has a value larger than than the current cell, perform dfs and update dp[(x, y)] with the maximum length that can be achieved from current cell, plus one. When we finish, dp[(x, y)] will have the longest length of increasing path from cell (x, y). Therefore, the result would be the maximum value in dp.

This Python solution uses DFS and memoization from dynamic programming to solve the problem. The problem is broken down into smaller subproblems, each of which is solved and memoized, and then these memoized solutions are used to compose an optimal solution to the problem. This reduces the complexity of the problem and makes it possible to solve it in a reasonable amount of time.# JavaScript solution

In JavaScript, we can approach the problem in a similar way:

1
2javascript
3var longestIncreasingPath = function(matrix) {
4    if(!matrix || !matrix[0]) return 0;
5    let m = matrix.length, n = matrix[0].length, dp = Array(m).fill(0).map(()=>Array(n).fill(0)), max = 1;
6    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];    
7    const dfs = (i, j) => {
8        if(dp[i][j]) return dp[i][j];
9        for(let dir of dirs) {
10            let x = i + dir[0], y = j + dir[1];
11            if(x<0 || y<0 || x>=m || y>=n || matrix[x][y] <= matrix[i][j]) continue;
12            dp[i][j] = Math.max(dp[i][j], dfs(x, y));
13        }
14        return ++dp[i][j];
15    }
16    for(let i=0; i<m; i++) {
17        for(let j=0; j<n; j++) {
18            max = Math.max(max, dfs(i, j));
19        }
20    }
21    return max;
22}

In this JavaScript solution, we first check whether the matrix exists. If it doesn't, return 0. While looping through each cell in the matrix, we perform a depth-first search to find out the maximum length of the increasing path from each cell, and store the maximum length in an array dp.

Java solution

The Java approach is also quite similar to the Python and JavaScript solutions:

1
2java
3public int longestIncreasingPath(int[][] matrix) {
4    if(matrix==null || matrix.length==0) return 0;
5    int m = matrix.length, n = matrix[0].length, max = 0;
6    int[][] dp = new int[m][n];
7    for(int i=0; i<m; i++) {
8        for(int j=0; j<n; j++) {
9            max = Math.max(max, dfs(matrix, Integer.MIN_VALUE, i, j, dp));
10        }
11    }
12    return max;
13}
14    
15private int dfs(int[][] matrix, int min, int i, int j, int[][] dp) {
16    if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length || matrix[i][j]<=min) return 0;
17    if(dp[i][j]!=0) return dp[i][j];
18    dp[i][j] = 1+ Math.max(Math.max(
19            dfs(matrix, matrix[i][j], i-1, j, dp),
20            dfs(matrix, matrix[i][j], i+1, j, dp)), Math.max(
21            dfs(matrix, matrix[i][j], i, j-1, dp),
22            dfs(matrix, matrix[i][j], i, j+1, dp)));
23    return dp[i][j];
24}

In the Java solution, we first check if the matrix exist, return 0. If the matrix exist, then we perform a depth-first search (DFS) from each cell which maintains the maximum length of the increasing path that we've seen so far in a 2D DP array. By the end of the function, the max value would be our result.

Each of these solutions makes use of the DFS algorithm to explore the matrix along with memoization to keep track of the longest path length discovered so far. As a result, we can determine the longest increasing path in the matrix with an improved time complexity.