Question

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:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

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

Example 2:

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

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

Quick Hints

• Do a DFS from every cell of the matrix
• Direction array {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
• Memorize the length in another matrix

Solution

Time complexity

O(m * n)

the DFS here is basically like DP with memorization. Every cell that has been computed will not be computed again, only a value look-up is performed. So this is O(mn), m and n being the width and height of the matrix.
To be exact, each cell can be accessed 5 times at most: 4 times from the top, bottom, left and right and one time from the outermost double for loop. 4 of these 5 visits will be look-ups except for the first one. So the running time should be lowercase o(5mn), which is of course O(mm).

Reference

Space complexity

O(m * n)

Notes