Longest Increasing Path in a Matrix

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:

  1. nums = [
  2.   [9,9,4],
  3.   [6,6,8],
  4.   [2,1,1]
  5. ]

Return 4

The longest increasing path is [1, 2, 6, 9].

Example 2:

  1. nums = [
  2.   [3,4,5],
  3.   [3,2,6],
  4.   [2,2,1]
  5. ]

Return 4

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution: