Find the longest path in a matrix where each step has entries that differ by 1

Question

Given an N*N matrix that all numbers are distinct in it, the function should find the maximum length path (starting from any cell) such that all the cells along the path are in increasing order with a difference of 1.

It can move in 4 directions from the given cell (i, j), It can move to (i-1, j) or (i, j-1) or (i+1, j) or (i, j+1) with the condition that the adjacent cells have a difference of 1.

I wrote the following code that works in all the cases that I have checked. I know that this is not optimal writing, with your permission, I would love to hear insights and ways to shorten the code. The program must be pure recursion without loops at all.

I'm not satisfied with the form and structure of my code because I went through the recursion step by step over all the options. I'm trying to write this in the form of backtracking with markings cells and stop conditions.

In the original question, the complexity of place, time, and the code are irrelevant.
At the moment, the discussion deals with the complexity of the code. I want to write it in a shorter and more elegant way while implementing backtracking.

public static int longestWorm(int[][] mat){
    return longestWorm(mat, 0,0,0);
}

private static int longestWorm(int[][] mat,int i, int j, int max){
    if (i == mat.length) return max;
    if (j == mat[i].length-1)
        return longestWorm(mat, i + 1, 0, max);
    if (wormCount(mat,i,j,0) > max) 
        max = wormCount(mat,i,j,0);
    return longestWorm(mat, i, j + 1, max);
}
private static int wormCount(int[][] mat, int i, int j,int count){
    if(i < mat.length-1 && mat[i][j] == mat[i+1][j]+1) 
        return 1+ wormCount(mat, i+1, j, count+1);
    if(j < mat[i].length-1 && mat[i][j] == mat[i][j+1]+1) 
        return 1+ wormCount(mat, i, j+1, count+1);
    if(i > 0 && mat[i][j] == mat[i-1][j]+1) 
        return 1+ wormCount(mat, i-1, j, count+1); 
    if(j > 0 && mat[i][j] == mat[i][j-1]+1)
        return 1+ wormCount(mat, i, j-1, count+1);
    return count;
}

Answer 1

So a couple of remarks:

• If I understand the required solution, you seem to have a bug, e.g. longestWorm(new int[][]{{0, 1, 3}, {9, 8 ,7}, {4, 5, 6}}) returns 10, although there are only 9 numbers. The wormcount calculation is then wrong because you increment the counter twice instead of once. Recursively defining the problem, you can say that the length of a path is the length of the current cell (which is one), summed by the length of the remaining path. Which would make the length function something like:

  private static int wormCount(int[][] mat, int i, int j){
      if (i < mat.length - 1 && mat[i][j] == mat[i + 1][j] + 1) {
          return 1 + wormCount(mat, i + 1, j);
      }
      ....
      return 1;
  }
  

This also makes the base case very clear. You also do not necessarily need to pass the count variable. Only perhaps if you would want to make it a tail-recursive function, but AFAIK in Java it will not help you eliminate a stack overflow.

• The problem is defined as finding a path of increasing order, but your code seems to calculate it the other way around. Not wrong, but slightly confusing.

• In the longestWorm function, you calculate the same function twice. This is not necessary:

  max = Math.max(max, wormCount(mat, i, j, 0));
  

You could save it in a local variable if it helps the readeability.

I do not know the optimal way to solve this problem. My guess would be you could at each index calculate the path length, and save it in a table. Because each value is unique, it could simply be a map between the value and the length of the path starting at that value (else, it could simply be a key generated using the indices i and j). Before calculating the length for a particular value (or starting at a particular index), you first look if you already calculated it, which you could then reuse.

Answer 2

After consulting with other students and after endless discussions about this question, the final solution of this code is:

public static int worm(int[][] a,int i,int j,int lastValue,boolean start)
{
  if(i<0||i==a.length||j<0||j==a[0].length)
    return 0;   

  if(lastValue == a[i][j] - 1 || start==true)
  {
      int l = worm(a,i,j-1,a[i][j],false);
      int r = worm(a,i,j+1,a[i][j],false);
      int u = worm(a,i-1,j,a[i][j],false);
      int d = worm(a,i+1,j,a[i][j],false);
      return 1 + Math.max(Math.max(l,r),Math.max(u,d));
    }  
      return 0;  
}

public static int longestWorm2(int[][] a,int i,int j,int max)
{
    if(i==a.length)
        return max;        
    if(j==a[0].length)
        return longestWorm2(a,i+1,0,max);       
    max = Math.max(max, worm(a,i,j,a[i][j],true));
    return longestWorm2(a,i,j+1,max);        
}
public static int longestWorm2(int[][] a){
 return longestWorm2(a,0,0,1);   
}

Answer 3

In accordance with @Koekje interesting recommendations, I edited the code so that the base case is more understandable, and also because a bug has been found in the code. It was also recommended by Koekje, of course, to use the current MAX to avoid recoding and recalculation. Now, the code seems shorter and more readable.
Of course, I'd like to see more comments/insights.

public static int longestWorm(int[][] mat){
    return longestWorm(mat, 0,0,0);
}

private static int longestWorm(int[][] mat,int i, int j, int max){
    if (i == mat.length) return max;
    if (j == mat[i].length)
        return longestWorm(mat, i + 1, 0, max);
    max= Math.max(max,wormCount(mat,i,j));
    return longestWorm(mat, i, j + 1, max);
}
private static int wormCount(int[][] mat, int i, int j){
    if(i < mat.length-1 && mat[i][j] == mat[i+1][j]+1) 
        return 1+ wormCount(mat, i+1, j);
    if(j < mat[i].length-1 && mat[i][j] == mat[i][j+1]+1) 
        return 1+ wormCount(mat, i, j+1);
    if(i > 0 && mat[i][j] == mat[i-1][j]+1) 
        return 1+ wormCount(mat, i-1, j); 
    if(j > 0 && mat[i][j] == mat[i][j-1]+1)
        return 1+ wormCount(mat, i, j-1);
    return 1;
}