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
Level of Question
Hard

Longest Increasing Path in a Matrix LeetCode Solution
Table of Contents
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:

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:

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 Complexity | Space Complexity | |
C++ | O(m * n) | O(m * n) |
Java | O(m * n) | O(m * n) |
JavaScript | O(m * n) | O(m * n) |
Python | O(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
).