Longest Increasing Path in a Matrix

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

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline \color{red} 9 & 9 & 4 \\ \hline \color{red}{6} & 6 & 8 \\ \hline \color{red}{2} & \color{red}{1} & 1 \\ \hline \end{array} $$

1
2
3
4
5


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:

$$ \begin{array}{|c|c|c|} \hline \color{red}3 & \color{red}{4} & \color{red}{5} \\ \hline 3 & 2 & \color{red}{6} \\ \hline 2 & 2 & 1 \\ \hline \end{array} $$

The longest increasing path is $\color{red}{3 \to 4 \to 5 \to 6}$ (top-left $\to$ top-middle $\to$ top-right $\to$ middle-right).

1
2
3
4
5


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.

Method 1 – DFS with Memoization

Intuition

We want to find the longest increasing path starting from every cell. To avoid recalculating results for the same cell, we store the answer for each cell after computing it once. This way, if another path reaches the same cell, we can reuse the result instantly. For example, if we’ve already found the longest path from (2,1), we don’t need to recompute it when another path passes through.

Approach

For each cell, start a DFS to find the longest increasing path from that cell.
At each step, move to any of the four adjacent cells (up, down, left, right) if the next cell’s value is strictly greater.
Use a 2D cache to store the result for each cell, so repeated visits don’t redo the work.
The answer is the maximum path length found from any cell.
No need for a visited array, since we only move to strictly increasing values, preventing cycles.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
	int longestIncreasingPath(vector<vector<int>>& matrix) {
		int m = matrix.size(), n = matrix[0].size(), ans = 0;
		vector<vector<int>> cache(m, vector<int>(n));
		vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
		function<int(int,int)> dfs = [&](int i, int j) {
			if (cache[i][j]) return cache[i][j];
			int res = 1;
			for (auto& d : dirs) {
				int x = i + d.first, y = j + d.second;
				if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
					res = max(res, 1 + dfs(x, y));
				}
			}
			return cache[i][j] = res;
		};
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				ans = max(ans, dfs(i, j));
		return ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func longestIncreasingPath(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	cache := make([][]int, m)
	for i := range cache {
		cache[i] = make([]int, n)
	}
	dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if cache[i][j] != 0 {
			return cache[i][j]
		}
		res := 1
		for _, d := range dirs {
			x, y := i+d[0], j+d[1]
			if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] {
				res = max(res, 1+dfs(x, y))
			}
		}
		cache[i][j] = res
		return res
	}
	ans := 0
	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 } else { return b } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
	private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	public int longestIncreasingPath(int[][] matrix) {
		int m = matrix.length, n = matrix[0].length, ans = 0;
		int[][] cache = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				ans = Math.max(ans, dfs(matrix, i, j, cache));
			}
		}
		return ans;
	}
	private int dfs(int[][] matrix, int i, int j, int[][] cache) {
		if (cache[i][j] != 0) return cache[i][j];
		int m = matrix.length, n = matrix[0].length, res = 1;
		for (int[] d : dirs) {
			int x = i + d[0], y = j + d[1];
			if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
				res = Math.max(res, 1 + dfs(matrix, x, y, cache));
			}
		}
		return cache[i][j] = res;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
	private val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
	fun longestIncreasingPath(matrix: Array<IntArray>): Int {
		val m = matrix.size
		val n = matrix[0].size
		val cache = Array(m) { IntArray(n) }
		var ans = 0
		fun dfs(i: Int, j: Int): Int {
			if (cache[i][j] != 0) return cache[i][j]
			var res = 1
			for (d in dirs) {
				val x = i + d[0]
				val y = j + d[1]
				if (x in 0 until m && y in 0 until n && matrix[x][y] > matrix[i][j]) {
					res = maxOf(res, 1 + dfs(x, y))
				}
			}
			cache[i][j] = res
			return res
		}
		for (i in 0 until m) for (j in 0 until n) ans = maxOf(ans, dfs(i, j))
		return ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
	def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
		m, n = len(matrix), len(matrix[0])
		cache: list[list[int]] = [[0]*n for _ in range(m)]
		dirs = [(1,0),(-1,0),(0,1),(0,-1)]
		def dfs(i: int, j: int) -> int:
			if cache[i][j]: return cache[i][j]
			res = 1
			for dx, dy in dirs:
				x, y = i+dx, j+dy
				if 0<=x<m and 0<=y<n and matrix[x][y] > matrix[i][j]:
					res = max(res, 1+dfs(x, y))
			cache[i][j] = res
			return res
		return max(dfs(i, j) for i in range(m) for j in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


impl Solution {
	pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
		let m = matrix.len();
		let n = matrix[0].len();
		let mut cache = vec![vec![0; n]; m];
		let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
		fn dfs(i: usize, j: usize, m: usize, n: usize, matrix: &Vec<Vec<i32>>, cache: &mut Vec<Vec<i32>>, dirs: &[(i32,i32);4]) -> i32 {
			if cache[i][j] != 0 { return cache[i][j]; }
			let mut res = 1;
			for &(dx, dy) in dirs {
				let x = i as i32 + dx;
				let y = j as i32 + dy;
				if x>=0 && x<m as i32 && y>=0 && y<n as i32 && matrix[x as usize][y as usize] > matrix[i][j] {
					res = res.max(1 + dfs(x as usize, y as usize, m, n, matrix, cache, dirs));
				}
			}
			cache[i][j] = res;
			res
		}
		let mut ans = 0;
		for i in 0..m {
			for j in 0..n {
				ans = ans.max(dfs(i, j, m, n, &matrix, &mut cache, &dirs));
			}
		}
		ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
	longestIncreasingPath(matrix: number[][]): number {
		const m = matrix.length, n = matrix[0].length;
		const cache: number[][] = Array.from({length: m}, () => Array(n).fill(0));
		const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
		const dfs = (i: number, j: number): number => {
			if (cache[i][j]) return cache[i][j];
			let res = 1;
			for (const [dx, dy] of dirs) {
				const x = i + dx, y = j + dy;
				if (x>=0 && x<m && y>=0 && y<n && matrix[x][y] > matrix[i][j]) {
					res = Math.max(res, 1 + dfs(x, y));
				}
			}
			cache[i][j] = res;
			return res;
		};
		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;
	}
}

Complexity

⏰ Time complexity: O(m * n), since each cell is visited once and each DFS call is memoized.
🧺 Space complexity: O(m * n), for the memoization cache and recursion stack.

Method 2 – Priority Queue (Topological Order) + DP

Intuition

Instead of searching from every cell, we process cells in decreasing order of their values. By always updating from higher to lower, we ensure that when we process a cell, all possible longer paths from its neighbors have already been computed. This is similar to topological sorting, but we use a max-heap (priority queue) to always pick the largest unprocessed cell.

Approach

Push all cells into a max-heap (priority queue) based on their values.
Pop cells one by one, and for each, try to update its neighbors if the neighbor’s value is less.
Use a DP table to store the longest path ending at each cell.
For each cell, set its path length to 1, and update it if a neighbor can extend the path.
The answer is the maximum value in the DP table after all cells are processed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
	int longestIncreasingPath(vector<vector<int>>& matrix) {
		int m = matrix.size(), n = matrix[0].size(), ans = 0;
		vector<vector<int>> dp(m, vector<int>(n, 1));
		auto cmp = [&](const pair<int,int>& a, const pair<int,int>& b) {
			return matrix[a.first][a.second] < matrix[b.first][b.second];
		};
		priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				pq.emplace(i, j);
		vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
		while (!pq.empty()) {
			auto [i, j] = pq.top(); pq.pop();
			for (auto& d : dirs) {
				int x = i + d.first, y = j + d.second;
				if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] < matrix[i][j]) {
					dp[x][y] = max(dp[x][y], dp[i][j] + 1);
				}
			}
			ans = max(ans, dp[i][j]);
		}
		return ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


import "container/heap"
type cell struct{ i, j, val int }
type maxHeap []cell
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i].val > h[j].val }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x interface{}) { *h = append(*h, x.(cell)) }
func (h *maxHeap) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func longestIncreasingPath(matrix [][]int) int {
	m, n := len(matrix), len(matrix[0])
	dp := make([][]int, m)
	for i := range dp { dp[i] = make([]int, n); for j := range dp[i] { dp[i][j] = 1 } }
	h := &maxHeap{}
	for i := 0; i < m; i++ { for j := 0; j < n; j++ { heap.Push(h, cell{i, j, matrix[i][j]}) } }
	dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
	ans := 0
	for h.Len() > 0 {
		c := heap.Pop(h).(cell)
		for _, d := range dirs {
			x, y := c.i+d[0], c.j+d[1]
			if x>=0 && x<m && y>=0 && y<n && matrix[x][y] < c.val {
				if dp[x][y] < dp[c.i][c.j]+1 {
					dp[x][y] = dp[c.i][c.j]+1
				}
			}
		}
		if dp[c.i][c.j] > ans { ans = dp[c.i][c.j] }
	}
	return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import java.util.*;
class Solution {
	private static final int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
	public int longestIncreasingPath(int[][] matrix) {
		int m = matrix.length, n = matrix[0].length, ans = 0;
		int[][] dp = new int[m][n];
		for (int[] row : dp) Arrays.fill(row, 1);
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> matrix[b[0]][b[1]] - matrix[a[0]][a[1]]);
		for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) pq.offer(new int[]{i, j});
		while (!pq.isEmpty()) {
			int[] cell = pq.poll();
			int i = cell[0], j = cell[1];
			for (int[] d : dirs) {
				int x = i + d[0], y = j + d[1];
				if (x>=0 && x<m && y>=0 && y<n && matrix[x][y] < matrix[i][j]) {
					dp[x][y] = Math.max(dp[x][y], dp[i][j]+1);
				}
			}
			ans = Math.max(ans, dp[i][j]);
		}
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import java.util.PriorityQueue
class Solution {
	private val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
	fun longestIncreasingPath(matrix: Array<IntArray>): Int {
		val m = matrix.size
		val n = matrix[0].size
		val dp = Array(m) { IntArray(n) { 1 } }
		val pq = PriorityQueue<Pair<Int,Int>>(compareByDescending { (i,j) -> matrix[i][j] })
		for (i in 0 until m) for (j in 0 until n) pq.add(i to j)
		var ans = 0
		while (pq.isNotEmpty()) {
			val (i, j) = pq.poll()
			for (d in dirs) {
				val x = i + d[0]
				val y = j + d[1]
				if (x in 0 until m && y in 0 until n && matrix[x][y] < matrix[i][j]) {
					dp[x][y] = maxOf(dp[x][y], dp[i][j]+1)
				}
			}
			ans = maxOf(ans, dp[i][j])
		}
		return ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import heapq
class Solution:
	def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
		m, n = len(matrix), len(matrix[0])
		dp = [[1]*n for _ in range(m)]
		heap = [(-matrix[i][j], i, j) for i in range(m) for j in range(n)]
		heapq.heapify(heap)
		dirs = [(1,0),(-1,0),(0,1),(0,-1)]
		ans = 0
		while heap:
			val, i, j = heapq.heappop(heap)
			for dx, dy in dirs:
				x, y = i+dx, j+dy
				if 0<=x<m and 0<=y<n and matrix[x][y] < matrix[i][j]:
					dp[x][y] = max(dp[x][y], dp[i][j]+1)
			ans = max(ans, dp[i][j])
		return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


use std::collections::BinaryHeap;
impl Solution {
	pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
		let m = matrix.len();
		let n = matrix[0].len();
		let mut dp = vec![vec![1; n]; m];
		let mut heap = BinaryHeap::new();
		for i in 0..m { for j in 0..n { heap.push((matrix[i][j], i, j)); } }
		let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
		let mut ans = 0;
		while let Some((val, i, j)) = heap.pop() {
			for (dx, dy) in dirs.iter() {
				let x = i as i32 + dx;
				let y = j as i32 + dy;
				if x>=0 && x<m as i32 && y>=0 && y<n as i32 && matrix[x as usize][y as usize] < val {
					let (x, y) = (x as usize, y as usize);
					if dp[x][y] < dp[i][j]+1 {
						dp[x][y] = dp[i][j]+1;
					}
				}
			}
			if dp[i][j] > ans { ans = dp[i][j]; }
		}
		ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
	longestIncreasingPath(matrix: number[][]): number {
		const m = matrix.length, n = matrix[0].length;
		const dp: number[][] = Array.from({length: m}, () => Array(n).fill(1));
		const heap: [number, number, number][] = [];
		for (let i = 0; i < m; ++i)
			for (let j = 0; j < n; ++j)
				heap.push([matrix[i][j], i, j]);
		heap.sort((a, b) => b[0] - a[0]);
		const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
		let ans = 0;
		for (const [val, i, j] of heap) {
			for (const [dx, dy] of dirs) {
				const x = i + dx, y = j + dy;
				if (x>=0 && x<m && y>=0 && y<n && matrix[x][y] < matrix[i][j]) {
					dp[x][y] = Math.max(dp[x][y], dp[i][j]+1);
				}
			}
			ans = Math.max(ans, dp[i][j]);
		}
		return ans;
	}
}

Complexity

⏰ Time complexity: O(m * n * log(m * n)), since each cell is pushed and popped from the heap, and each update is O(1).
🧺 Space complexity: O(m * n), for the DP table and heap.

Problem#

Examples#

Similar Problem#

Method 1 – DFS with Memoization#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Priority Queue (Topological Order) + DP#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Similar Problem

Method 1 – DFS with Memoization

Intuition

Approach

Code

Complexity

Method 2 – Priority Queue (Topological Order) + DP

Intuition

Approach

Code

Complexity