Question

Formatted question description: https://leetcode.ca/all/329.html

 329	Longest Increasing Path in a Matrix

 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.

Algorithm

Maintain a two-dimensional dynamic array dp, where dp[i][j] represents the length of the longest incremental path starting from (i,j) in the array, and initially assigns all dp arrays to 0.

When we call recursively and encounter a certain position (x, y), if dp[x][y] is not 0, we can directly return dp[x][y] without repeating calculations.

We need to call recursion with each position in the array as the starting point to do so, and compare to find the maximum value. When searching with DFS starting from a position, judge its four adjacent positions. If the value of the adjacent position is greater than the previous position, continue to call recursion on the adjacent position and update a maximum value, and the search is completed After returning.

Code

Java

  • 
    public class Longest_Increasing_Path_in_a_Matrix {
    
        class Solution {
    
            private int[] dx = new int[]{0, 0, -1, 1};
            private int[] dy = new int[]{1, -1, 0, 0};
    
            public int longestIncreasingPath(int[][] matrix) {
    
                if (matrix == null || matrix.length == 0) {
                    return 0;
                }
                int longest = 0;
    
                int m = matrix.length;
                int n = matrix[0].length;
    
                // longest path starting from position (i,j)
                int[][] dp = new int[m][n];
    
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        longest = Math.max(longest, dfs(i, j, matrix, dp));
                    }
                }
    
                return longest;
            }
    
            private int dfs(int row, int col, int[][] matrix, int[][] dp) {
                if (dp[row][col] > 0) {
                    return dp[row][col];
                }
    
                int m = matrix.length;
                int n = matrix[0].length;
    
                int currentLongest = 0;
                for (int c = 0; c < 4; c++) {
                    int i = row + dx[c];
                    int j = col + dy[c];
    
                    if (i >= 0 && i < m && j >= 0 && j < n && matrix[row][col] < matrix[i][j]) {
                        currentLongest = Math.max(currentLongest, dfs(i, j, matrix, dp));
                    }
                }
    
                dp[row][col] = 1 + currentLongest;
                return dp[row][col];
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
    // Time: O(MN)
    // Space: O(MN)
    class Solution {
        vector<vector<int>> cnt;
        int ans = 0, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        int dfs(vector<vector<int>> &A, int x, int y) {
            if (cnt[x][y]) return cnt[x][y];
            cnt[x][y] = 1;
            for (auto &dir : dirs) {
                int a = x + dir[0], b = y + dir[1];
                if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] <= A[x][y]) continue;
                cnt[x][y] = max(cnt[x][y], 1 + dfs(A, a, b));
            }
            return cnt[x][y];
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& A) {
            if (A.empty() || A[0].empty()) return 0;
            M = A.size(), N = A[0].size();
            cnt.assign(M, vector<int>(N));
            for (int i = 0; i < M; ++i) 
                for (int j = 0; j < N; ++j) 
                    ans = max(ans, dfs(A, i, j));
            return ans;
        }
    };
    
  • directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    
    
    class Solution(object):
      def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
    
        def dfs(matrix, i, j, visited, cache):
          if (i, j) in visited:
            return visited[(i, j)]
    
          ret = 0
          for di, dj in directions:
            p, q = i + di, j + dj
            if p < 0 or q < 0 or p >= len(matrix) or q >= len(matrix[0]):
              continue
            if (p, q) not in cache and matrix[p][q] > matrix[i][j]:
              cache.add((p, q))
              r = dfs(matrix, p, q, visited, cache)
              ret = max(ret, r)
              cache.discard((p, q))
    
          visited[(i, j)] = ret + 1
          return ret + 1
    
        visited = {}
        cache = set()
        ans = 0
        for i in range(0, len(matrix)):
          for j in range(0, len(matrix[0])):
            cache.add((i, j))
            ans = max(ans, dfs(matrix, i, j, visited, cache))
            cache.discard((i, j))
        return ans
    
    

All Problems

All Solutions