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

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