Finding the length of the longest increasing path in a matrix

Problem:

Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right.

Example:

$$
\begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}
$$

Output: 7

Longest path is 1, 2, 3, 4, 5, 6, 7

Question:

I am not sure if this post is relevant to this site. I having some trouble coming up with a system to solve this problem. I am not too advanced with programming, I am more of a mathematician by trade but I know some stuff about data structure and algorithms.

If possible, an ideal answer for me would be a step by step guide in solving this problem. My initial thought was to find the smallest number in the $(i, j)$ position and start with the first $(i,j)$ position that was found. Then check up, down, left, right to see which number is larger. But then I thought okay what if there are more than 1 position that is larger? I am pretty stuck with this so any help would be useful.

I found solutions to this online but reading other peoples code is nauseating and I don't find it useful at all.

Here is an $O(nm \log nm)$ solution, where $n,m$ are the dimensions of the matrix. Later we improve it to an optimal $O(nm)$ solution.

Let $A[i_1j_1],\ldots,A[i_{nm}j_{nm}]$ be the entries of $A$ in non-decreasing order; the indices $i_tj_t$ can be computed in time $O(nm\log nm)$. We will compute a new matrix $B$ with the same dimensions such that $B[ij]$ is the length of the longest increasing part ending at $A[ij]$. We compute the entries of $B$ in the order $B[i_1j_1],\ldots,B[i_{nm}j_{nm}]$, using the formula
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'],
$$
where $i'j' \sim ij$ means that $A[i'j']$ is a neighbor of $A[ij]$, and we set $B[ij] = 1$ if the maximum is over the empty set.

The answer is simply the maximum entry of $B$. You can find an actual longest increasing sequence by starting with a maximum entry of $B$, say equal to $\ell$, finding a neighbor equal to $\ell-1$, then a neighbor equal to $\ell-2$, and so on until hitting a neighbor equal to $1$. This gives you a longest increasing sequence in reverse order.

As an example, consider your matrix
$$
A = \begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}.
$$
We can order the entries as follows (there are many possible orders, since the entries are not distinct):
$$
A[1,1],A[1,2],A[2,1],A[2,2],A[3,2],A[1,3],A[2,3],A[3,1],\\A[3,3],A[1,4],A[2,4],A[3,4],A[4,1],A[4,2],A[4,3],A[4,4].
$$
We now compute $B$ in the same order:
$$
\begin{pmatrix}
1& & & \\
& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2&1& & \\
& & & \\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2& & \\
2&1& & \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1& & \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1& & \\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2& \\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5& &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&7
\end{pmatrix}.
$$
We conclude that the answer is $7$. Retracing our steps, we highlight the following path in $B$, which corresponds to the longest increasing sequence in $A$ (accidentally, having exactly the same values):
$$
\begin{pmatrix}
1& & & \\
2& & & \\
3& & & \\
4&5&6&7
\end{pmatrix}.
$$

We can implement essentially the same solution in time $O(nm)$ using DFS. We go over the entries of $B$ in some arbitrary order, attempting to use the same recurrence formula we had before:
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'].
$$
If we are trying to access an entry $B[i'j']$ which hasn't already been computed we compute it recursively. Conversely, once an entry $B[ij]$ has been computed, there is no need to compute it again.

This can be implemented using the following pseudocode:

compute-B-matrix:
  initialize B to be empty
  for 1 <= i <= n and 1 <= j <= m:
     if B[i,j] is empty, call compute-entry(i,j)

compute-entry(i,j):
  let S = { neighbors (i',j') of (i,j) such that A[i',j'] < A[i,j] }
  if S is empty:
     set B[i,j] = 1
  if S is non-empty:
    for every (i',j') in S:
      if B[i',j'] is empty, call compute-entry(i',j')
    set B[i,j] = 1 + max({ B[i',j'] : (i',j') in S })

This solution essentially amounts to computing a topological ordering of a digraph naturally associated with $A$. Details left to the reader.

StackExchange Computer Science Q#91115, answer score: 2