Longest Increasing Path in a Matrix LeetCode Solution

Last updated on January 21st, 2025 at 02:18 am

Here, we see a Longest Increasing Path in a Matrix LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Memorization, Topological Sort

Companies

Google

Level of Question

Hard

Longest Increasing Path in a Matrix LeetCode Solution

Longest Increasing Path in a Matrix LeetCode Solution

1. Problem Statement

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

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).

Example 1:

grid1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

tmp grid

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.

Example 3:
Input: matrix = [[1]]
Output: 1

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Dynamic Programming with Depth First Search (DFS)”. The problem involves finding the longest increasing path in a matrix, which is solved using a combination of DFS for traversal and memoization (dynamic programming) to store intermediate results and avoid redundant computations.

3. Code Implementation in Different Languages

3.1 Longest Increasing Path in a Matrix C++

class Solution {
public:
    int m, n;
    short path[200][200];
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        memset(path, 0, sizeof(path));
        int max_path = 1;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                max_path = max(max_path, dfs(i, j, matrix));
        return max_path;
    }
    int dfs(int i, int j, vector<vector<int>>& mat) {
        if(path[i][j] >   0) return path[i][j];
        if(path[i][j] == -1) return 0;
        int max_next = 0;
        path[i][j] = -1;
        if(i > 0   && mat[i][j] < mat[i-1][j]) max_next = max(max_next, dfs(i-1, j, mat));
        if(j > 0   && mat[i][j] < mat[i][j-1]) max_next = max(max_next, dfs(i, j-1, mat));
        if(i < m-1 && mat[i][j] < mat[i+1][j]) max_next = max(max_next, dfs(i+1, j, mat));
        if(j < n-1 && mat[i][j] < mat[i][j+1]) max_next = max(max_next, dfs(i, j+1, mat));
        return path[i][j] = 1 + max_next;
    }

public:
    Solution() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        wcin.tie(nullptr);
        cerr.tie(nullptr);
        wcerr.tie(nullptr);
        clog.tie(nullptr);
        wclog.tie(nullptr);
    }
};

3.2 Longest Increasing Path in a Matrix Java

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[][] cache = new int[matrix.length][matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int length = findSmallAround(i, j, matrix, cache, Integer.MAX_VALUE);
                max = Math.max(length, max);
            }
        }
        return max;
    }
    private int findSmallAround(int i, int j, int[][] matrix, int[][] cache, int pre) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] >= pre) {
            return 0;
        }
        if (cache[i][j] > 0) {
            return cache[i][j];
        } else {
            int cur = matrix[i][j];
            int tempMax = 0;
            tempMax = Math.max(findSmallAround(i - 1, j, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i + 1, j, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i, j - 1, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i, j + 1, matrix, cache, cur), tempMax);
            cache[i][j] = ++tempMax;
            return tempMax;
        }
    }
}

3.3 Longest Increasing Path in a Matrix JavaScript

var longestIncreasingPath = function(matrix) {
    let ylen = matrix.length, xlen = matrix[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 = matrix[y][x]
        memo[y][x] = 1 + Math.max(
            y < ylen - 1 && matrix[y+1][x] < val ? dfs(y+1,x) : 0,
            y > 0 && matrix[y-1][x] < val ? dfs(y-1,x) : 0,
            x < xlen - 1 && matrix[y][x+1] < val ? dfs(y,x+1) : 0,
            x > 0 && matrix[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
};

3.4 Longest Increasing Path in a Matrix Python

class Solution(object):
    def longestIncreasingPath(self, matrix):
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(
                    dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
            return dp[i][j]
        if not matrix or not matrix[0]: return 0
        M, N = len(matrix), len(matrix[0])
        dp = [[0] * N for i in range(M)]
        return max(dfs(x, y) for x in range(M) for y in range(N))

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(m * n)O(m * n)
JavaO(m * n)O(m * n)
JavaScriptO(m * n)O(m * n)
PythonO(m * n)O(m * n)
  • Dynamic Programming with DFS is a powerful technique for solving problems involving optimal paths or sequences in a grid or graph.
  • The memoization table ensures that each cell is processed only once, significantly reducing redundant computations.
  • The recursion stack depth depends on the structure of the matrix, but in the worst case, it can go as deep as the total number of cells (m * n).
Scroll to Top