patternpythonMinor

Find the longest rectilinear path in a matrix with descending entries

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

rectilinearpaththedescendingwithfindlongestmatrixentries

Problem

Problem (Skiing):

Each number represents the elevation of that area of the mountain.

From each area (i.e. 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 ski downhill).

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.

Goal:

Find the longest path following these rules. Longest path means the maximum number of nodes where we are always going down.

If we have many longest paths with equal distance (number of nodes), then we should get the one with the maximum drop (value of 1st

node - value of the last node).

The aim is to run this code for a 1000 x 1000 matrix. As for now, running for just a 4 x 4, it's taking minutes. Any idea on how to reduce the complexity regarding time and space?

```
myMatrix = [[4, 5, 2],[1, 1, 6],[8, 7, 5]]
def getAllValidSkiingPathsFrom(myMatrix):
dctOfMatrix = {}
for row in range(len(myMatrix)):
for column in range(len(myMatrix[0])):
currPoint = (column, row)
dctOfMatrix[currPoint] = myMatrix[row][column]

lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
setAllPossiblePaths = set()

from itertools import permutations
for pathCandidate in permutations(lstIndicesOfAllMatrixPoints):
lstPossiblePath = []
prevIndexTuple = pathCandidate[0]
lstPossiblePath.append(prevIndexTuple)
for currIndexTuple in pathCandidate[1:]:
if abs(currIndexTuple[0]-prevIndexTuple[0]) + abs(currIndexTuple[1]-prevIndexTuple[1]) > 1:
break # current path indices

Solution

As I said in the comment, it's probably faster to get the local minima and check the paths that start from those points. You can then get the path with the maximum length and reverse the points if you want the descending path.

I haven't tested this a lot, but it takes less than a second on my pc with a 4x4 matrix.

Here's the code (again, I've only tested this with a few inputs and there's a bit of code duplication, take it as a general guideline):

def get_next_ascending_value(row, column, matrix, size):
    current_value = matrix[row][column]
    max_steepness = -1
    coords = []
    if (column > 0) and (matrix[row][column-1] > current_value):
        if max_steepness  0) and (matrix[row-1][column] > current_value):
        if max_steepness  current_value):
        if max_steepness  current_value):
        if max_steepness  0) and (matrix[row][column-1]  0) and (matrix[row-1][column]  0):
        print(next_coords, starting_matrix[next_coords[0]][next_coords[1]])
        next_coords = get_next_ascending_value(next_coords[0], next_coords[1], starting_matrix, size)
    print('---')

Code Snippets

def get_next_ascending_value(row, column, matrix, size):
    current_value = matrix[row][column]
    max_steepness = -1
    coords = []
    if (column > 0) and (matrix[row][column-1] > current_value):
        if max_steepness < matrix[row][column-1]:
            max_steepness = matrix[row][column-1]
            coords = [row, column-1]
    if (row > 0) and (matrix[row-1][column] > current_value):
        if max_steepness < matrix[row-1][column]:
            max_steepness = matrix[row-1][column]
            coords = [row-1, column]
    if (column < size - 1) and (matrix[row][column+1] > current_value):
        if max_steepness < matrix[row][column+1]:
            max_steepness = matrix[row][column+1]
            coords = [row, column+1]
    if (row < size - 1) and (matrix[row+1][column] > current_value):
        if max_steepness < matrix[row+1][column]:
            max_steepness = matrix[row+1][column]
            coords = [row+1, column]

    return coords


def is_local_minimum(row, column, matrix, size):
    current_value = matrix[row][column]
    if (column > 0) and (matrix[row][column-1] < current_value):
        return False
    if (row > 0) and (matrix[row-1][column] < current_value):
        return False
    if (column < size - 1) and (matrix[row][column+1] < current_value):
        return False
    if (row < size - 1) and (matrix[row+1][column] < current_value):
        return False

    return True

def get_local_minimum(matrix, size):
    for row in range(len(matrix)):
        for column in range(size):
            if is_local_minimum(row, column, matrix, size):
                yield [row, column]

# [4, 5, 6]
# [1, 1, 6]
# [4, 5, 6]

# starting_matrix = [[4, 5, 6],[1, 1, 6],[4, 5, 6]]
# size = 3

# [4, 5]
# [1, 1]

# starting_matrix = [[4, 5],[1, 1]]
# size = 2


# [4, 5, 7, 9]
# [1, 1, 2, 5]
# [4, 5, 7, 9]
# [1, 1, 2, 5]

starting_matrix = [[4, 5, 7, 9],[1, 1, 2, 5],[4, 5, 7, 9],[1, 1, 2, 5]]
size = 4

for coords in get_local_minimum(starting_matrix, size):
    print(coords, starting_matrix[coords[0]][coords[1]])
    next_coords = get_next_ascending_value(coords[0], coords[1], starting_matrix, size)
    while (len(next_coords) > 0):
        print(next_coords, starting_matrix[next_coords[0]][next_coords[1]])
        next_coords = get_next_ascending_value(next_coords[0], next_coords[1], starting_matrix, size)
    print('---')

Context

StackExchange Code Review Q#160614, answer score: 2

Revisions (0)

No revisions yet.