Leetcode 329: Longest increasing path in matrix

June  20, 2016

problem statement:

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

329. Longest Increasing Path in a matrix

Example 1:

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

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

Study the code written in Java:

http://blog.csdn.net/sbitswc/article/details/50707203

1st practice using C#: 

https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4

Question and answer:

1. How is the practice? 

The study was very good. DFS - using recursive call, and then, tricky part is to use memorization to 

avoid duplicated calculation. 

2. Talk more with an easy example, therefore, next time you will not forget the problem after 

a few months. 

Answer: Will write something here. 

1. Talk about node row = 2, col =1, value is 1, denoted as start1,  3 neigbors, left (value 2), right (value 1), up(value 6)

2. Try to avoid loops - base case checking, always go to the node value >= current value >= start node '1'

3. Also, if neighbour node left (value 2) has maximum increasing path in matrix n, then, what we can know:

   value 1 < value 2, then, start1's longest path at least 1 + value2's longest increasing path. Need to check other 2 

  neighbors to see if it is larger value

    left neighbor (value 2)'s longest increasing path in matrix 2->6->9, length is 3;

    right neighbor (value 1)'s longest increasing path in matrix 1->8, length is 2; 

    upper neighbor (value 6)'s longest increasing path in matrix (actually 2 of them, 6->9 or 6->8), length is 2. 

4. DFS algorithm can be set up using recursive function; also, there are total 3*3 = 9 nodes in the above matrix, 

    each node's increasing path in matrix should not count more than once. 

    For example, nums[0,0] = 9, is maximum value of matrix, so the longest path = 1. 

    Let us put a sentence together. How about the following:

    Be greedy, check your neighbors (at most 4), and find maximum one with longest increasing path in matrix, and then use the path

to build your own. The value is 1 + that neighbor's problem, where the recursive function is constructed. 

5. The design of algorithm - brute force solution - how many paths in the matrix - n^4 = n x n x n x n; filter out non-

increasing path, then find maximum value - not efficient

6. For each node in matrix, find its longest increasing path in matrix, nxn nodes, each node, DFS algorithm is applied. 

    at most nxn node is checked about increasing order. <- try to reason the time complexity -> ...

    Will be less than n^4. 

7. Prepare a check list for the design:

    1. Run time issue - index out of range - array - boundary check 

        loops - always go to bigger value - no loop 

    2. time complexity - nxn node, each one does DFS; each DFS, at most 4 n^2 comparison of value. 

    3. space complexity - use extra array nxn to store bool value - memorization  

    4. value is bigger/ smaller / 0, 0 - not possible, at least 1, miss count - recursive, should be easy. 

    5. Brute force solution and its issues - more time consuming etc., duplication calculation    

Most important discussion: 

find the idea to store in extra array: 

1. Extra array to store the length of "longest increasing path in matrix" for each node in the array - (working idea)

2. Extra array to mark the node is visited or not -  (not enough for calculation!)

 denote DFS function to calculate the longest increasing path in matrix, then starting from start1, the function will be

left->left->up->up, in other words, from 1->2->6->9, and then, 

up->right,    1->6->8   

up-> up,       1->6->9, 

the visiting order of neighbors is left, down, right, up.

https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4

anti-clockwise, left, down, right, up  - line 116 - 120

So, the cache value of (2, 1) is 4, longest path is 4 (1->2->6->9); and 6 nodes in matrix are calculated and saved with 

cache value - 2 matrix(2,0), 6(1,0), 9(0,0), 6(1,1), 8(1,2), 9(0,1), the order of saving is 

9(0,0),          - 0 neighbor

6(1,0),          - 1 neighbor

2 matrix(2,0) - 1neighbor, value 1

6(1,1)

8(1,2)            

9(0,1)

6(1,1)   - 2 neighbors, comparison 1 vs 1 

1(2,1)   - 2 neighbors, comparison 3 vs 2

Use stack to help to track the order: 

start1 node, 2 neighbors

go to left neighbor first, 

      push to stack, 2, 6, 9

no down neighbor, skip right

then go to up neighbour, 

     ...

Statistics: 

Time to work out order of calculation cache value in the above list takes more than 10 minutes. 

Two motivations to work on reasoning and analysis:

1. Leetcode 329 is hard

2. Being able to write down bug free, executable code in 20 minutes. 

  3. Study more solutions from others, and then, practice it using C#. Study one using C++. 

C++ solution:

http://gaocegege.com/Blog/algorithm/leetcode329

http://codingmelon.com/2016/01/20/longest-increasing-path-in-a-matrix-leetcode-329/

To be continued.