Find the longest rectilinear path in a matrix with descending entries 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]) &gt; 1:
                break # current path indices not allowed in path (no diagonals or jumps)
            else:
                if dctOfMatrix[currIndexTuple] &gt;= dctOfMatrix[prevIndexTuple]: 
                    break # only "down" is allowed for "skiing" 
                else:
                    lstPossiblePath.append(currIndexTuple)
                    prevIndexTuple = currIndexTuple
        if len(lstPossiblePath) &gt; 1 and tuple(lstPossiblePath) not in setAllPossiblePaths: 
            setAllPossiblePaths.add(tuple(lstPossiblePath))

    return setAllPossiblePaths, dctOfMatrix

setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)

printedPath = []
bestPath = []
for path in setAllPossiblePaths:
    for point in path:
        printedPath.append(dctOfMatrix[point])
    if len(printedPath) &gt; len(bestPath): # Looking for the path with a maximum distance
        bestPath = printedPath
    if len(printedPath) == len(bestPath): # If we have more than one path with a maximum distance we look for the drop
        if (printedPath[0]-printedPath[-1]) &gt; (bestPath[0]-bestPath[-1]):
            bestPath = printedPath
    printedPath = []

print("Path --&gt;", bestPath)
print("Distance --&gt;", len(bestPath))
print("Drop --&gt;", bestPath[0]-bestPath[-1])


Sample input matrix:

4 5 2
1 1 6
8 7 5


Output:

Path --&gt; [8, 7, 1]
Distance --&gt; 3
Drop --&gt; 7


Explanation:

The longest path would be 8-7-1 as it has the maximum distance = 3.

There are other paths with the same maximum distance which are 8-7-5 and 5-4-1. However, 8-7-1 has the maximum drop = 7 (8-1).
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 &gt; 0) and (matrix[row][column-1] &gt; current_value):
        if max_steepness &lt; matrix[row][column-1]:
            max_steepness = matrix[row][column-1]
            coords = [row, column-1]
    if (row &gt; 0) and (matrix[row-1][column] &gt; current_value):
        if max_steepness &lt; matrix[row-1][column]:
            max_steepness = matrix[row-1][column]
            coords = [row-1, column]
    if (column &lt; size - 1) and (matrix[row][column+1] &gt; current_value):
        if max_steepness &lt; matrix[row][column+1]:
            max_steepness = matrix[row][column+1]
            coords = [row, column+1]
    if (row &lt; size - 1) and (matrix[row+1][column] &gt; current_value):
        if max_steepness &lt; 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 &gt; 0) and (matrix[row][column-1] &lt; current_value):
        return False
    if (row &gt; 0) and (matrix[row-1][column] &lt; current_value):
        return False
    if (column &lt; size - 1) and (matrix[row][column+1] &lt; current_value):
        return False
    if (row &lt; size - 1) and (matrix[row+1][column] &lt; 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) &gt; 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('---')