Given a matrix with n rows and m columns. Your task is to find the length of the longest increasing path in matrix, here increasing path means that the value in the specified path increases. For example if a path of length k has values a_{1}, a_{2}, a_{3}, .... a_{k } , then for every i from [2,k] this condition must hold a_{i }> a_{i-1}.  No cell should be revisited in the path.
From each cell, you can either move in four directions: left, right, up, or down. You are not allowed to move diagonally or move outside the boundary.
Example 1:
Input:
n = 3, m = 3
matrix[][] = {{1 2 3},
              {4 5 6},
              {7 8 9}}
Output: 
5
Explanation: 
The longest increasing path is 
{1, 2, 3, 6, 9}. 
Example 2:
Input:
n = 3, m = 3
matrix[][] = {{3 4 5},
              {6 2 6},
              {2 2 1}}
Output: 
4
Explanation:
The longest increasing path is
{3, 4, 5, 6}.
Your Task:
You only need to implement the given function longestIncreasingPath() which takes the two integers n and m and the matrix matrix as input parameters, and returns the length of the longest increasing path in matrix.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n,m ≤ 1000
0 ≤ matrix[i] ≤ 2^{30}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3

# You are required to complete this function
# Function should return the an integer 

class Solution:
    def longestIncreasingPath(matrix, n, m):
        # Code here


Solutions:
class Solution:

	def longestIncreasingPath(self, matrix, n, m):

		def dfs(matrix, dummy, i, j, n, m):
			if dummy[i][j] != 0:
				return dummy[i][j]
			dx = [0, 0, 1, -1]
			dy = [1, -1, 0, 0]
			res = 1
			for k in range(4):
				p = i + dx[k]
				q = j + dy[k]
				if p >= 0 and p < n and (q >= 0) and (q < m) and (matrix[i][j] < matrix[p][q]):
					res = max(res, 1 + dfs(matrix, dummy, p, q, n, m))
			dummy[i][j] = res
			return res
		dummy = [[0] * m for i in range(n)]
		maxi = 0
		for i in range(n):
			for j in range(m):
				maxi = max(maxi, dfs(matrix, dummy, i, j, n, m))
		return maxi


class Solution:

	def longestIncreasingPath(self, matrix, n, m):
		dp = [[0 for j in range(m)] for i in range(n)]
		dr = [[-1, 0], [1, 0], [0, -1], [0, 1]]

		def dfs(i, j):
			if i < 0 or j < 0 or i >= n or (j >= m):
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			ans = 0
			for (k, l) in dr:
				x = i + k
				y = j + l
				if x > -1 and y > -1 and (x < n) and (y < m) and (matrix[i][j] < matrix[x][y]):
					up = dfs(x, y)
					ans = max(ans, up)
			dp[i][j] = ans + 1
			return dp[i][j]
		p = 0
		for i in range(n):
			for j in range(m):
				a = dfs(i, j)
				p = max(p, a)
		return p


class Solution:

	def longestIncreasingPath(self, matrix, n, m):
		dp = [[-1] * m for i in range(n)]
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = 1
			for k in dirs:
				(i1, j1) = (i + k[0], j + k[1])
				if 0 <= i1 < n and 0 <= j1 < m:
					if matrix[i][j] > matrix[i1][j1]:
						dp[i][j] = max(dp[i][j], 1 + dfs(i1, j1))
			return dp[i][j]
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, dfs(i, j))
		return ans


class Solution:

	def LIS(self, matrix, i, j, row, col, dp):
		if i < 0 or i > row or j < 0 or (j > col):
			return 0
		if dp[i][j] > 0:
			return dp[i][j]
		currentMax = 1
		if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:
			currentMax = max(currentMax, 1 + self.LIS(matrix, i, j - 1, row, col, dp))
		if j + 1 < col and matrix[i][j + 1] > matrix[i][j]:
			currentMax = max(currentMax, 1 + self.LIS(matrix, i, j + 1, row, col, dp))
		if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:
			currentMax = max(currentMax, 1 + self.LIS(matrix, i - 1, j, row, col, dp))
		if i + 1 < row and matrix[i + 1][j] > matrix[i][j]:
			currentMax = max(currentMax, 1 + self.LIS(matrix, i + 1, j, row, col, dp))
		dp[i][j] = currentMax
		return currentMax

	def longestIncreasingPath(self, matrix, n, m):
		dp = []
		for i in range(n):
			result = []
			for j in range(m):
				result.append(0)
			dp.append(result)
		maxPath = 0
		for i in range(n):
			for j in range(m):
				maxPath = max(maxPath, self.LIS(matrix, i, j, n, m, dp))
		return maxPath


class Solution:

	def longestIncreasingPath(self, matrix, n, m):
		longest = 0
		mem = dict()
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				cand = self.longest_helper(matrix, i, j, mem)
				if cand > longest:
					longest = cand
		return longest

	def longest_helper(self, matrix, i, j, mem):
		if (i, j) in mem:
			return mem[i, j]
		curr_val = matrix[i][j]
		longest = 1
		diff = [(0, -1), (0, 1), (-1, 0), (1, 0)]
		for d in diff:
			new_i = i + d[0]
			new_j = j + d[1]
			if 0 <= new_i < len(matrix) and 0 <= new_j < len(matrix[i]):
				new_val = matrix[new_i][new_j]
				if new_val > curr_val:
					cand_path = 1 + self.longest_helper(matrix, new_i, new_j, mem)
					if cand_path > longest:
						longest = cand_path
		mem[i, j] = longest
		return longest


class Solution:

	def dfs(self, mat, dp, i, j):
		(n, m) = (len(dp), len(dp[0]))
		if i - 1 >= 0 and mat[i - 1][j] < mat[i][j]:
			if not dp[i - 1][j]:
				dp[i - 1][j] = self.dfs(mat, dp, i - 1, j)
			dp[i][j] = max(dp[i][j], dp[i - 1][j])
		if j - 1 >= 0 and mat[i][j - 1] < mat[i][j]:
			if not dp[i][j - 1]:
				dp[i][j - 1] = self.dfs(mat, dp, i, j - 1)
			dp[i][j] = max(dp[i][j], dp[i][j - 1])
		if i + 1 < n and mat[i + 1][j] < mat[i][j]:
			if not dp[i + 1][j]:
				dp[i + 1][j] = self.dfs(mat, dp, i + 1, j)
			dp[i][j] = max(dp[i][j], dp[i + 1][j])
		if j + 1 < m and mat[i][j + 1] < mat[i][j]:
			if not dp[i][j + 1]:
				dp[i][j + 1] = self.dfs(mat, dp, i, j + 1)
			dp[i][j] = max(dp[i][j], dp[i][j + 1])
		dp[i][j] += 1
		return dp[i][j]

	def longestIncreasingPath(self, mat, n, m):
		dp = [[0 for j in range(m)] for i in range(n)]
		mx = 1
		for i in range(n):
			for j in range(m):
				if not dp[i][j]:
					dp[i][j] = self.dfs(mat, dp, i, j)
				mx = max(mx, dp[i][j])
		return mx


class Solution:

	def longestIncreasingPath(self, matrix, n, m):
		dp = [[-1 for i in range(m + 1)] for i in range(n)]

		def findLongestFromACell(i, j, mat, dp):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			(x, y, z, w) = (-1, -1, -1, -1)
			if j < m - 1 and mat[i][j] < mat[i][j + 1]:
				x = 1 + findLongestFromACell(i, j + 1, mat, dp)
			if j > 0 and mat[i][j] < mat[i][j - 1]:
				y = 1 + findLongestFromACell(i, j - 1, mat, dp)
			if i > 0 and mat[i][j] < mat[i - 1][j]:
				z = 1 + findLongestFromACell(i - 1, j, mat, dp)
			if i < n - 1 and mat[i][j] < mat[i + 1][j]:
				w = 1 + findLongestFromACell(i + 1, j, mat, dp)
			dp[i][j] = max(x, max(y, max(z, max(w, 1))))
			return dp[i][j]
		result = 1
		for i in range(n):
			for j in range(m):
				if dp[i][j] == -1:
					findLongestFromACell(i, j, matrix, dp)
				result = max(result, dp[i][j])
		return result