Longest Increasing Path in a Matrix

Hard

The problem

From any cell of matrix you can move up, down, left or right (not diagonally and not outside the grid) to a neighbour whose value is strictly bigger. Return the number of cells on the longest path you can make this way.

Example 1
Input: matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Output: 4
The path 1, 2, 6, 9 goes up through four cells.
Example 2
Input: matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
Output: 4
The path 3, 4, 5, 6.

Limits

1 ≤ rows, columns ≤ 200
0 ≤ matrix[r][c] ≤ 1,000,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Because the path must strictly increase, there are no cycles. Which results can you cache?

The idea

DFS with memoization: longest(r,c) = 1 + max over neighbours with larger values; cache per cell.

Target: O(m·n) time

Go function shape

func longestIncreasingPath(matrix [][]int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LongestIncreasingPath: memoized DFS. Strictly increasing steps cannot form a cycle,
// so every cell's answer can be cached the first time it is computed.
func LongestIncreasingPath(m [][]int) int {
	if len(m) == 0 {
		return 0
	}
	memo := make([][]int, len(m))
	for i := range memo {
		memo[i] = make([]int, len(m[0]))
	}
	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		if memo[r][c] != 0 {
			return memo[r][c]
		}
		best := 1
		for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
			nr, nc := r+d[0], c+d[1]
			if nr >= 0 && nr < len(m) && nc >= 0 && nc < len(m[0]) && m[nr][nc] > m[r][c] {
				best = max(best, 1+dfs(nr, nc))
			}
		}
		memo[r][c] = best
		return best
	}
	longest := 0
	for r := range m {
		for c := range m[r] {
			longest = max(longest, dfs(r, c))
		}
	}
	return longest
}

Read the lesson: 2-D Dynamic Programming