> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-08/lc329-longest-increasing-path-in-a-matrix.md).

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

### Example

**Input:** matrix = `[[9,9,4],[6,6,8],[2,1,1]]`

**Output:** 4

**Explanation:** The longest increasing path is `[1, 2, 6, 9]`.

## Solution

### Cached DFS

Intuitively, the longest increasing path from each coordinate is fixed, and is dependent on that of its neighbors. Hence, we can calculate the longest increasing path of each coordinate and return the maximum. To do this, we can use a DFS. Since calculations will inevitably repeated due to the neighboring dependencies, we will use a cache to save time. Time and space complexity of this solution is $$O(m\cdot n)$$.

```python
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
	ROWS = len(matrix)
	COLS = len(matrix[0])
	@cache
	def dfs(row, col, prev):
		if (row < 0 or row == ROWS or col < 0 or col == COLS or matrix[row][col] <= prev):
			return 0
		subLip = 1
		# Get LIP of each direction and return the maximum
		subLip = max(subLip, 1 + dfs(row + 1, col, matrix[row][col]))
		subLip = max(subLip, 1 + dfs(row - 1, col, matrix[row][col]))
		subLip = max(subLip, 1 + dfs(row, col + 1, matrix[row][col]))
		subLip = max(subLip, 1 + dfs(row, col - 1, matrix[row][col]))
		return subLip

	lip = 0
	for row in range(ROWS):
		for col in range(COLS):
			# use -1 because value in each coord is >= 0 
			lip = max(lip, dfs(row, col, -1))
	return lip
```