Find path of steepest descent along with path length in a matrix

Question

Came across this problem -- You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in, i.e. you can only descend. You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit. And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation. Ex Grid:

4 8 7 3 
2 5 9 3 
6 3 2 5 
4 4 1 6

On this particular map the longest path down is of length=5 and it is: 9-5-3-2-1.

There is another path that is also length five: 8-5-3-2-1. dropping from 9 to 1(8) is a steeper drop than 8 to 1(7). WAP to find the longest (and then steepest) path.

I've worked through Floyd Warshalls, DAG + Topological sorting, tried to think of DFS, though about DP, various things but I am not able to find a way to think through. Any pointers + simple pseudo code for approach would be helpful.

Answer 1

A few observations about this problem.

1. You are looking for the longest path with the given constraint, so it is not helpful to use A* or Floyd-Warshall which are designed to find the shortest path.

2. In extreme cases, the path could contain all fields of the grid, e.g.:

   1 2 3
   8 9 4
   7 6 5
   

   (here, the path forms a spiral, but other figures are possible.)

   Therefore, an ideal algorithm cannot be better than O(n), which is also the same complexity as visiting each field once.

3. Given a field F and its surrounding fields N, E, S, W as far as they exist, we can calculate the path length L(F) as

          ⎧ 1 + F(M) if M exists
   L(F) = ⎨
          ⎩ 0        otherwise
   

   where M ∈ {N, E, S, W} so that Value(M) < Value(F) and F(M) = max({F(X) | X ∈ {N, E, S, W}}). As pseudo-code:

   def L(F):
     lower = {X for X in {N, E, S, W} if X.value < F.value}
     if lower.is_empty:
       return 0
     return 1 + max({ L(X) for X in lower})
   

   Proof of correctness is left as an exercise to the reader.

4. The function L(F) may be calculated using memoization. That is, we build a cache for L(F) so that each field is only calculated once. At the beginning, each calculation might involve the calculations for other fields as well, in the worst case all fields. Therefore, our memoized L(F) has complexity O(n) to O(1) depending on whether the cache already contains the necessary values. But on average over the whole cache complexity is O(1) (each value is computed only once, and is only requested a constant number of times).

   So if we iterate over all fields and calculate the path length for that field, this iteration will be O(n). Therefore, this algorithm with memoization is ideal!

5. We cannot apply dynamic programming, since we do not know which fields would have to be calculated first. Well, we could sort all fields by their value and start calculating lowest first, but that would end up being more expensive and way more complicated than building the cache lazily.

6. While calculating L(F), we can also somehow keep track of the path that contains some field, and the currently longest paths. All of this will not affect the complexity.

Together, the following approach emerges:

• each field in your matrix has three properties: value, length, and next field in the path.
• as an implementation detail, you'll have to figure out how to retrieve the neighbour fields for a given field.
• the length is lazily calculated.

• when the M neighbour is selected, the next field is set to M. This might be problematic if more than one field has the properties of M, e.g. in this matrix:

  1 2 3
  4 9 8
  5 8 9
  

  Starting from the 9s, it is not immediately clear which 8 should be part of the ideal path. Either you implement this to keep track of all possible paths (which does not affect the complexity), or you select the partial path with the steepest descent. This will require you to walk both paths which is not free but O(n). To avoid this, you can memoize the maximum slope as an additional property of each field.

  By the way, that example shows a case where there are two solutions 9-8-3-2-1.

Pseudo-code:

record Field {
  value  : Int
  length : Count? = null
  next   : Field? = null
  slope  : Int?   = null
}

get-neighbours(f : Field): Set[Field] {
  ...
}

get-length(f : Field): Int {
  if f.length != null {
    return f.length
  }

  let next : Collection[Field] = get-neighbours(f)
    .where(x -> x.value < f.value) // must be smaller
    .max-by(x -> get-length(x)) // must have longest partial path
    .max-by(x -> x.slope) // prefer steepest path

  if next.is_empty {
    f.length = 0
    return f.length
  }

  let next = next.first // pick any field that satisfies all properties
  f.next = next
  f.slope = next.slope ?? f.value - next.value
  f.length = 1 + next.length
  return f.length
}

get-path(f: Field): Field generator {
  yield f
  if f.next != null {
    yield from get-path(f.next)
  }
}

let matrix : Array[height, Array[width, Field]] = {
  { Field(1), ... },
  ...,
}

// evaluate length for each field in matrix
// and keep track of longest paths

let mut longest = List()
let mut length = 0

for f in matrix {
  let l = get-lengh(f)
  if l > length {
    length = get-length(f)
    longest = List(f)
  }
  else if l == length {
    longest.add(f)
  }
}

// print out longest paths
for start in longest {
  println(List(get-path(start)))
}

Answer 2

A dynamic programming approach should work.

For each cell:

• Reduce the problem of finding the best (longest, steepest slope) descending path from there to the problem of finding the best path from each of its neighbors that is smaller and then adding the step to that neighbor to get the best path from the cell in question.

• Memo(r)ize the best path from each cell along the way.

• Don't actually save an explicit path, only save the next cell on the path (that way the path is there, just implicitly).

That should run in time linear to the size of the matrix if you do it correctly... unless I'm misunderstanding the problem of course.

Code might look something like:

public class BestDynamicDescendingPathFinder {
    public static int[][] example = new int[][]{{4, 8, 7, 3},{2, 5, 9, 3},{6, 3, 2, 5},{4, 4, 1, 6}};

    public static void main(String[] args)
    {
        BestDynamicDescendingPathFinder finder = new BestDynamicDescendingPathFinder(example);
        System.out.println("Best overall: " + Arrays.toString(finder.find()));
        System.out.println("Best starting from some other cell: " + Arrays.toString(finder.unfoldBestPathFromCell(3, 3)));
    }

    private int[][] matrix;
    private PathInformation[][] informationForBestPathFromCellMemory;

    public BestDynamicDescendingPathFinder(int[][] aMatrix)
    {
        informationForBestPathFromCellMemory = new PathInformation[aMatrix.length][];
        matrix = new int[aMatrix.length][];

        for(int i = 0; i < aMatrix.length; i++)
        {
            informationForBestPathFromCellMemory[i] = new PathInformation[aMatrix[i].length];
            matrix[i] = new int[aMatrix[i].length];

            for(int j = 0; j < aMatrix[i].length; j++)
            {
                matrix[i][j] = aMatrix[i][j];
            }
        }
    }

    // find the best path by getting the best starting cell and unfolding the information for it
    public int[] find()
    {
        int currentBestStartingCellColumn = 0;
        int currentBestStartingCellRow = 0;
        for(int i = 0; i < matrix.length; i++)
        {
            for(int j = 0; j < matrix[i].length; j++)
            {
               if(getInformationForBestPathFromCell(i, j).compareTo(getInformationForBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow)) == 1){
                   currentBestStartingCellColumn = i;
                   currentBestStartingCellRow = j;
               }
            }
        }

        return unfoldBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow);
    }

    // unfold the best path (starting) from a cell by walking the PathInformation structures in memory
    private int[] unfoldBestPathFromCell(int colNum, int rowNum)
    {
        PathInformation currentCellInformation = getInformationForBestPathFromCell(colNum, rowNum);
        int[] path = new int[currentCellInformation.length];
        path[0] = matrix[colNum][rowNum];
        int idx = 1;

        while(currentCellInformation.length > 1)
        {
            path[idx] = matrix[currentCellInformation.nextCellColumn][currentCellInformation.nextCellRow];
            idx++;
            currentCellInformation = getInformationForBestPathFromCell(currentCellInformation.nextCellColumn, currentCellInformation.nextCellRow);
        }

        return path;
    }

    // get the information for the best path (starting) from a cell: from memory if available or calculate otherwise
    private PathInformation getInformationForBestPathFromCell(int colNum, int rowNum)
    {
        if(informationForBestPathFromCellMemory[colNum][rowNum] == null)
        {
            informationForBestPathFromCellMemory[colNum][rowNum] = calculateInformationForBestPathFromCell(colNum, rowNum);
        }
        return informationForBestPathFromCellMemory[colNum][rowNum];
    }

    // calculate the information for the best path (starting) from a cell by using the information for best paths from neighboring cells
    private PathInformation calculateInformationForBestPathFromCell(int colNum, int rowNum)
    {
        List<PathInformation> possiblePathsFromCell = new ArrayList<PathInformation>();
        if(colNum != 0 && matrix[colNum - 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum - 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum - 1, rowNum));
        }

        if(colNum != matrix.length - 1 && matrix[colNum + 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum + 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum + 1, rowNum));
        }

        if(rowNum != 0 && matrix[colNum][rowNum - 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum - 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum - 1));
        }

        if(rowNum != matrix[colNum].length -1 && matrix[colNum][rowNum + 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum + 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum + 1));
        }

        if(possiblePathsFromCell.isEmpty())
        {
            return new PathInformation(1, matrix[colNum][rowNum], matrix[colNum][rowNum], -1, -1);   
        }

        return Collections.max(possiblePathsFromCell);
    }
}

public class PathInformation implements Comparable<PathInformation>
{
    int length;
    int startValue;
    int endValue; 
    int nextCellColumn;
    int nextCellRow;

    public PathInformation(int length, int startValue, int endValue, int nextCellColumn, int nextCellRow) 
    {
        this.length = length;
        this.startValue = startValue;
        this.endValue = endValue;
        this.nextCellColumn = nextCellColumn;
        this.nextCellRow = nextCellRow;
    }

    @Override
    public int compareTo(PathInformation other) {
        if(this.length < other.length || (this.length == other.length && this.startValue - this.endValue < other.startValue - other.endValue)){
            return -1;
        }
        if(this.length > other.length || (this.length == other.length && this.startValue - this.endValue > other.startValue - other.endValue)){
            return 1;
        }
        return 0;
    }
}

Answer 3

I solved it using a memoized DFS solution. I am visualizing this matrix as a DAG with the values as nodes and a edge to NWES neighbors only if the value of the neighbor is < the value at the node. I am traversing each of the node and storing the max depth starting from that node and the value of the node at the deepest end of the path.

After the complete graph traversal I am comparing the depth for the longest and node value - value at the end of the path as the steepness.

    public class LongestSteepestPath {
        private static final int[] rows = {0, 0, 1, -1}, cols = {1, -1, 0, 0};
    
        /**
         * @param grid The matrix which shows the topography of the area
         * @return [length of the path, steepness of the path]
         */
        public int[] longestSteepestPath(int[][] grid) {
            if (grid == null || grid.length == 0)
                return new int[]{0, 0};
            int n = grid.length, m = grid[0].length;
            int[][][] length = new int[n][m][2];
            Arrays.stream(length).forEach(arr -> Arrays.fill(arr, new int[]{-1, -1}));
            int[] ans = {-1, -1};
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (length[i][j][0] == -1)
                        dfs(i, j, grid, length);
                }
            }
            //Arrays.stream(length).forEach(arr -> System.out.println(Arrays.stream(arr).map(Arrays::toString).collect(Collectors.toList())));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (ans[0] < length[i][j][0]) {
                        ans[0] = length[i][j][0];
                        ans[1] = grid[i][j] - length[i][j][1];
                    } else if (ans[0] == length[i][j][0] && ans[1] < grid[i][j] - length[i][j][1]) {
                        ans[0] = length[i][j][0];
                        ans[1] = grid[i][j] - length[i][j][1];
                    }
                }
            }
            return ans;
        }
    
        private void dfs(int row, int col, int[][] grid, int[][][] length) {
            length[row][col] = new int[]{0, grid[row][col]};
            for (int i = 0; i < 4; i++) {
                int r = row + rows[i], c = col + cols[i];
                if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] < grid[row][col]) {
                    if (length[r][c][0] == -1)
                        dfs(r, c, grid, length);
                    if (length[row][col][0] < length[r][c][0] + 1) {
                        length[row][col][0] = length[r][c][0] + 1;
                        length[row][col][1] = length[r][c][1];
                    } else if (length[row][col][0] == (length[r][c][0] + 1) && length[row][col][1] > length[r][c][1])
                        length[row][col][1] = length[r][c][1];
                }
            }
        }
    }