Find the longest increasing path in a matrix.
Given an m x n integers matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down.
Input: matrix = [[1,2],[3,4]]
Output: 3
Explanation: The longest strictly increasing path is 1 - 3 - 4 (or 1 - 2 - 4), both of which have a length of 3.

Question

Find the longest increasing path in a matrix.

Given an m x n integers matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down.

Input: matrix = [[1,2],[3,4]]

Output: 3

Explanation: The longest strictly increasing path is 1 -> 3 -> 4 (or 1 -> 2 -> 4), both of which have a length of 3.

Anonymous · Accepted Answer

def longestIncreasingPath(self, matrix: List[List[int]]) -> int: m = len(matrix) if m==0: return 0 n = len(matrix[0]) dp = [-1 for i in range(n)] for j in range(m) result = 1 helper(i, j): if dp[i][j] != -1: return dp[i][j] ans = 1 if i+1matrix[i][j]: ans = max(helper(i+1, j), ans) if i>0 and matrix[i-1][j]>matrix[i][j]: ans = max(helper(i-1, j), ans) if j+1matrix[i][j]: ans = max(helper(i, j+1), ans) if j>0 and matrix[i][j-1]>matrix[i][j]: ans = max(helper(i, j-1), ans) result = max(result, ans) return ans for int i in range(m): for int j in range(n): if dp[i][j] != -1: dp[i][j] = helper(i,j) return result # TC = O(m*n) # SC = O(m*n)

Find the longest increasing path in a matrix.

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Practice More Questions