Find out the Longest Path in a matrix

Given an m-by-n matrix with positive integers, determine the length of the longest path of increasing within the matrix. For example, consider the input matrix:
[1 2 3
4 5 6
7 8 9]

The answer should be 5 since the longest path would be 1-2-5-6-9

def isValid(mat, i, j):
   return 0 <= i < len(mat) and 0 <= j < len(mat)

def findLongestPath(mat, i, j):
   if not isValid(mat, i, j):
       return []
   path = []
   if i > 0 and mat[i - 1][j] - mat[i][j] == 1:
       path = findLongestPath(mat, i - 1, j)

   if j + 1 < len(mat) and mat[i][j + 1] - mat[i][j] == 1:
       path = findLongestPath(mat, i, j + 1)

   if i + 1 < len(mat) and mat[i + 1][j] - mat[i][j] == 1:
       path = findLongestPath(mat, i + 1, j)

   if j > 0 and mat[i][j - 1] - mat[i][j] == 1:
       path = findLongestPath(mat, i, j - 1)

   path.insert(0, mat[i][j])
   return path

def longestPath(mat):
   if not mat or not len(mat):
       return []
   longest_path = []
   for i in range(len(mat)):
       for j in range(len(mat)):
           path = findLongestPath(mat, i, j)
           if len(path) > len(longest_path):
               longest_path = path
   return len(longest_path)


if __name__ == '__main__':

   mat = [
           [10, 13, 14, 21, 23],
           [11, 9, 22, 2, 3],
           [12, 8, 1, 5, 4],
           [15, 24, 7, 6, 20],
           [16, 17, 18, 19, 25]
       ]
   res = longestPath(mat)
   print ("Length of longest path :",res)

Leave a Reply

%d bloggers like this: