329. Longest Increasing Path in a Matrix #

Problem #

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [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.

Problem Statement #

Given an integer matrix, find the length of the longest increasing path. For each cell, you can move in four directions: up, down, left, and right. You cannot move diagonally or move outside the boundary (i.e. wrap-around is not allowed).

Solution Approach #

• Given a matrix, the task is to find the longest increasing path in this matrix. The path can move in 4 directions: up, down, left, and right.
• The approach for this problem is very obvious: just use DFS. After submitting the first version, you will find it gets TLE, because the problem provides a very large matrix and there are too many searches. Therefore, memoization is needed to cache the maximum length that has been searched before. After adding memoization and submitting again, it gets AC.

Code #

package leetcode

import (
	"math"
)

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func longestIncreasingPath(matrix [][]int) int {
	cache, res := make([][]int, len(matrix)), 0
	for i := 0; i < len(cache); i++ {
		cache[i] = make([]int, len(matrix[0]))
	}
	for i, v := range matrix {
		for j := range v {
			searchPath(matrix, cache, math.MinInt64, i, j)
			res = max(res, cache[i][j])
		}
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func isInIntBoard(board [][]int, x, y int) bool {
	return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}

func searchPath(board, cache [][]int, lastNum, x, y int) int {
	if board[x][y] <= lastNum {
		return 0
	}
	if cache[x][y] > 0 {
		return cache[x][y]
	}
	count := 1
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		if isInIntBoard(board, nx, ny) {
			count = max(count, searchPath(board, cache, board[x][y], nx, ny)+1)
		}
	}
	cache[x][y] = count
	return count
}