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