3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Snorrlaxxx Apr 24 '18 at 22:26
  • $\begingroup$ I don't rewrite the matrix $A$. I just figure out the order of the entries, which I follow when filling the matrix $B$. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:27
  • $\begingroup$ 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. $\endgroup$ – Snorrlaxxx Apr 24 '18 at 22:30
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:33
  • $\begingroup$ 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}$$ $\endgroup$ – Snorrlaxxx Apr 24 '18 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.