329. Longest Increasing Path in a Matrix

LeetCode 329. Longest Increasing Path in a Matrix

Description

Given an m x n integers matrix, return the length of the longest increasing path inmatrix.

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

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 200

• 0 <= matrix[i][j] <= 2^31 - 1

Tags

Depth-first Search, Topological Sort, Memoization

Solution

We build a 2D array dp with the same size of matrix to store the Longest Increasing Path starting from matrix[i][j], with all elements initialized with 1. We also need an 1D array of all elements in descending order. It allows us to find the longest path in decreasing way. Then we perform BFS for each elements of this 1D array, and update the longest path.

Complexity

• Time complexity: $O(mn)$

• Space complexity: $O(mn)$

Code

func longestIncreasingPath(matrix [][]int) int {
	ans, elements := 1, make([][]int, 0, len(matrix)*len(matrix[0]))
	for i, line := range matrix {
		for j, v := range line {
			elements = append(elements, []int{v, i, j})
		}
	}
	sort.Slice(elements, func(i, j int) bool {
		return elements[i][0] > elements[j][0]
	})
	dp, dirs := make([][]int, len(matrix)), [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for i := range dp {
		dp[i] = make([]int, len(matrix[0]))
		for j := range dp[i] {
			dp[i][j] = 1
		}
	}
	for _, e := range elements {
		v, i, j := e[0], e[1], e[2]
		for _, d := range dirs {
			if x, y := i+d[0], j+d[1]; x >= 0 && y >= 0 && x < len(matrix) && y < len(matrix[0]) && matrix[x][y] > v && dp[i][j] < dp[x][y]+1 {
				dp[i][j] = dp[x][y] + 1
			}
		}
		if dp[i][j] > ans {
			ans = dp[i][j]
		}
	}
	return ans
}

Reference

1. 329. Longest Increasing Path in a Matrix