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

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];
        }
    }
}

############

class Solution {
    private int[][] memo;
    private int[][] matrix;
    private int m;
    private int n;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(memo[i], -1);
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
        return ans;
    }

    private int dfs(int i, int j) {
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int ans = 1;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                ans = Math.max(ans, dfs(x, y) + 1);
            }
        }
        memo[i][j] = ans;
        return ans;
    }
}

// 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;
    }
};

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        @cache
        def dfs(i, j):
            ans = 1
            for a, b in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    ans = max(ans, dfs(x, y) + 1)
            return ans

        m, n = len(matrix), len(matrix[0])
        return max(dfs(i, j) for i in range(m) for j in range(n))

############

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

func longestIncreasingPath(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	ans := -1
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if memo[i][j] != -1 {
			return memo[i][j]
		}
		ans := 1
		dirs := []int{-1, 0, 1, 0, -1}
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] {
				ans = max(ans, dfs(x, y)+1)
			}
		}
		memo[i][j] = ans
		return ans
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans = max(ans, dfs(i, j))
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

329 - Longest Increasing Path in a Matrix

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions