Longest Increasing Path in a Matrix solution and explanation
Google
9 more videos on this problem
Longest Increasing Path in a Matrix - Leetcode 329NeetCode · 17:45 · 92K views
Longest Increasing Path in a Matrix | Live Coding with Explanation | Leetcode - 329Algorithms Made Easy · 9:59 · 13K views
LeetCode 329. Longest Increasing Path in a Matrix Explanation and Solutionhappygirlzt · 7:26 · 8K views
Google Coding Interview Tutorial - Longest Increasing Path in a Matrix [LeetCode 329]Shiran Afergan · 10:06 · 4K views
Leetcode - Longest Increasing Path in a Matrix (Python)Timothy H Chang · 5:38 · 2K views
329. Longest Increasing Path in a Matrix (Leetcode Hard)Programming Live with Larry · 27:02 · 1K views
Longest Increasing Path | LeetCode 329 (Hard)Destination FAANG · 23:01 · 831 views
LeetCode 329. Longest Increasing Path in a MatrixHappy Coding · 12:58 · 412 views
Leetcode 329. Longest Increasing Path in a Matrix | DFS SolutionPlacement Corner · 13:32 · 270 views
Longest Increasing Path in a Matrix | LeetCode 329 | Coders CampCoders Camp · 12:39 · 267 views
The problem
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
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Approach overview
Problem Overview: Given an m x n matrix, return the length of the longest strictly increasing path. From any cell you can move up, down, left, or right, but only to a cell with a larger value. The goal is to explore the grid efficiently without recomputing paths starting from the same cell.
Approach 1: Depth‑First Search (DFS) with Memoization (O(m*n) time, O(m*n) space)
Treat each cell as the start of a path and run DFS to explore neighbors with strictly larger values. The key insight: many paths overlap. If you already computed the longest path starting from a cell, reuse that result instead of recomputing it. Store results in a memo matrix where memo[r][c] represents the longest path beginning at that cell. Each cell is processed once, and every DFS only explores four directions. This converts an exponential search into linear work over all cells. This approach combines Depth‑First Search with Dynamic Programming via caching.
Approach 2: Topological Sort / BFS on Directed Graph (O(m*n) time, O(m*n) space)
Interpret the matrix as a directed graph. Create edges from smaller values to larger neighbors. Because values must increase, the graph is a DAG. Compute the outdegree for each cell (how many neighbors are larger). Cells with outdegree 0 represent path endpoints. Push them into a queue and perform level‑order processing similar to Kahn's algorithm. Each BFS layer represents one step backward in increasing paths. Reduce neighbor outdegrees as nodes are removed. The number of BFS layers processed equals the longest increasing path length. This reframes the grid as a graph problem with matrix traversal.
Recommended for interviews: DFS with memoization is the most commonly expected solution. It demonstrates understanding of DFS, caching overlapping subproblems, and converting exponential recursion into O(m*n) dynamic programming. Mentioning the topological sort interpretation shows deeper graph insight and can impress interviewers when discussing alternative formulations.
Approach 1: Depth First Search (DFS) with Memoization
This approach uses a combination of Depth First Search (DFS) and memoization to solve the problem efficiently. We explore each cell, attempting to find the longest increasing path starting from that cell. To avoid recalculating the path length for each call from the same cell, we use memoization to store already computed results.
def longestIncreasingPath(matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
memo = [[-1] * n for _ in range(m)]
def dfs(x, y):
if memo[x][y] != -1:
return memo[x][y]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_len = 1
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
max_len = max(max_len, 1 + dfs(nx, ny))
memo[x][y] = max_len
return max_len
return max(dfs(x, y) for x in range(m) for y in range(n))class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] memo = new int[m][n];
int maxLen = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxLen = Math.max(maxLen, dfs(matrix, i, j, memo));
}
}
return maxLen;
}
private int dfs(int[][] matrix, int x, int y, int[][] memo) {
if (memo[x][y] != 0) return memo[x][y];
int m = matrix.length, n = matrix[0].length;
int maxLen = 1;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : directions) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
int len = 1 + dfs(matrix, nx, ny, memo);
maxLen = Math.max(maxLen, len);
}
}
memo[x][y] = maxLen;
return maxLen;
}
}#include <vector>
using namespace std;
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> memo(m, vector<int>(n, -1));
int maxLen = 0;
std::function<int(int, int)> dfs = [&](int x, int y) {
if (memo[x][y] != -1) return memo[x][y];
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int max_len = 1;
for (const auto& d : directions) {
int nx = x + d.first, ny = y + d.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
max_len = max(max_len, 1 + dfs(nx, ny));
}
}
memo[x][y] = max_len;
return max_len;
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
maxLen = max(maxLen, dfs(i, j));
}
}
return maxLen;
}
};In this Python solution, we define a helper function dfs that performs DFS on the matrix starting from a given cell. We utilize a memo table to store the longest path from each cell to avoid redundant calculations, improving performance significantly. The main function starts by iterating over each cell to compute the maximum length path by considering each cell as a starting point.
The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.
Approach 2: Dynamic Programming
This approach systematically calculates the longest increasing path dynamically by first iterating over the matrix and then updating results based on previously computed values. By using a dynamic programming table, we determine, for each cell, the longest chain it can contribute to incrementally.
var longestIncreasingPath = function(matrix) {
if (!matrix || !matrix.length || !matrix[0].length) return 0;
let m = matrix.length, n = matrix[0].length;
let dp = Array.from({length: m}, () => Array(n).fill(0));
let maxLen = 0;
const dfs = (x, y) => {
if (dp[x][y] !== 0) return dp[x][y];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
dp[x][y] = 1;
for (let [dx, dy] of directions) {
let nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
dp[x][y] = Math.max(dp[x][y], 1 + dfs(nx, ny));
}
}
return dp[x][y];
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
maxLen = Math.max(maxLen, dfs(i, j));
}
}
return maxLen;
};public class Solution {
public int LongestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.Length == 0) return 0;
int m = matrix.Length, n = matrix[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) dp[i] = new int[n];
int maxLen = 0;
int dfs(int x, int y) {
if (dp[x][y] != 0) return dp[x][y];
int[][] directions = new int[][]{new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};
dp[x][y] = 1;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
dp[x][y] = Math.Max(dp[x][y], 1 + dfs(nx, ny));
}
}
return dp[x][y];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxLen = Math.Max(maxLen, dfs(i, j));
}
}
return maxLen;
}
}The JavaScript solution uses dynamic programming. For each cell, the function dfs recursively explores valid neighbors, resulting in the longest increasing path starting from that cell. The result for each cell is stored in a DP table before being returned, which ensures efficiency by preventing the recalculation of already known results.
The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.
Approach 3: Memoization Search
We design a function dfs(i, j), which represents the length of the longest increasing path that can be obtained starting from the coordinate (i, j) in the matrix. The answer is max_{i, j} dfs(i, j).
The execution logic of the function dfs(i, j) is as follows:
- If
(i, j)has been visited, directly returnf(i, j); - Otherwise, search
(i, j), search the coordinates(x, y)in four directions. If0 \le x < m, 0 \le y < nandmatrix[x][y] > matrix[i][j], then search(x, y). After the search is over, updatef(i, j)tof(i, j) = max(f(i, j), f(x, y) + 1). Finally, returnf(i, j).
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.
Similar problems:
function longestIncreasingPath(matrix: number[][]): number {
const m = matrix.length;
const n = matrix[0].length;
const f: number[][] = Array(m)
.fill(0)
.map(() => Array(n).fill(0));
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number): number => {
if (f[i][j] > 0) {
return f[i][j];
}
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
f[i][j] = Math.max(f[i][j], dfs(x, y));
}
}
return ++f[i][j];
};
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}func longestIncreasingPath(matrix [][]int) (ans int) {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if f[i][j] != 0 {
return f[i][j]
}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if 0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j] {
f[i][j] = max(f[i][j], dfs(x, y))
}
}
f[i][j]++
return f[i][j]
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
ans = max(ans, dfs(i, j))
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Memoization | The time complexity is |
| Dynamic Programming | The time complexity is |
| Memoization Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization | O(m*n) | O(m*n) | Best general solution. Clean recursion with caching avoids recomputation. |
| Topological Sort (BFS / Kahn's Algorithm) | O(m*n) | O(m*n) | Useful when modeling the matrix as a DAG and processing nodes by levels. |
| Naive DFS without Memoization | O((m*n)*4^(m*n)) worst case | O(m*n) | Conceptual baseline. Demonstrates the overlapping subproblem issue. |
Frequently asked questions
Is Longest Increasing Path in a Matrix easy or hard?
Longest Increasing Path in a Matrix is classified as a Hard problem on LeetCode. The difficulty comes from recognizing overlapping subproblems and transforming naive DFS into an efficient O(m*n) dynamic programming solution using memoization or graph topological ordering.
Longest Increasing Path in a Matrix Python/Java solution
Python and Java implementations typically use DFS with a memo table. A recursive function explores four directions and stores the computed longest path for each cell. This reduces the complexity to O(m*n) while keeping the implementation concise.
How to solve Longest Increasing Path in a Matrix in O(n)?
Treat the grid as m*n nodes and compute the longest path in O(m*n) time using DFS with memoization. Store the best path length starting from each cell in a cache so overlapping searches are avoided. Another O(m*n) method uses topological sorting by treating the matrix as a DAG and processing nodes by levels.
What is the best approach for Longest Increasing Path in a Matrix?
DFS with memoization is the most widely used approach. Start a DFS from every cell and cache the longest path length for that cell so repeated subproblems are not recomputed. Each cell is evaluated once, giving O(m*n) time and O(m*n) space complexity.
Is Longest Increasing Path in a Matrix asked at Google/Amazon/Meta?
Longest Increasing Path in a Matrix frequently appears in interviews at companies like Google, Amazon, and Meta because it tests DFS, dynamic programming, and graph modeling. Candidates must recognize overlapping subproblems and optimize recursion with memoization.
What data structure is used in Longest Increasing Path in a Matrix?
The main structures are a 2D memoization array for dynamic programming and recursion or a queue for BFS. The matrix itself can be interpreted as a directed graph where edges go from smaller values to larger neighbors.
What is the time complexity of Longest Increasing Path in a Matrix?
The optimal solutions run in O(m*n) time where m and n are the matrix dimensions. With DFS and memoization, each cell's result is computed once and reused. Every DFS checks at most four neighbors, keeping the total work linear in the number of cells.