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

• I like your solution I just have a few questions. As I understand it, we first re-write the matrix $A$ in increasing order. Then construct a matrix $B$. I don't fully understand the details of how to construct the matrix $B$. Am I correct with the first step though? – Snorrlaxxx Apr 24 '18 at 22:26
• I don't rewrite the matrix $A$. I just figure out the order of the entries, which I follow when filling the matrix $B$. – Yuval Filmus Apr 24 '18 at 22:27
• Okay, I am confused. Let me ask about the first sentence then. When you say arrange the entries of the matrix in non-decreasing order. Do you mean I create a matrix whose entries are non-decreasing entries of A? Sorry I am a bit slow with this. – Snorrlaxxx Apr 24 '18 at 22:30
• What I actually do is take all pairs of indices $(i,j)$, for $1 \leq i \leq n$ and $1 \leq j \leq m$, and arrange them in nondecreasing order of the corresponding entry of $A$. How you implement that is up to you. – Yuval Filmus Apr 24 '18 at 22:33
• Okay so let me see if I understand. If I have a matrix $$A = \begin{pmatrix} 10 & 5 & 1\\ 2 & 10 & 1\\ 2& 9 & 10 \end{pmatrix}$$ Then for your first sentence I create say $$A' = \begin{pmatrix} 1 & 1 & 2\\ 2 & 5 & 9\\ 10 & 10 & 10 \end{pmatrix}$$ – Snorrlaxxx Apr 24 '18 at 22:34