longest_increasing_path_in_a_matrix
1from math import inf 2 3 4# @leet start 5class Solution: 6 def longestIncreasingPath(self, matrix: list[list[int]]) -> int: 7 """ 8 This question asks us to find the longest increasing path in a matrix 9 We can do this by DFSing through the entire matrix, keeping track of 10 the previous value to make sure our number is always strictly increasing, 11 but this would have a time complexity of $O(2^n)$. 12 We want and $O(n)$ solution, and we can get one with caching. We first 13 define a cache, which holds the longest increasing path from this node. 14 Then, we dfs through, checking the cache to see if we've already visited 15 that node. If we have, we return that, if we go out of bounds or if 16 we aren't increasing anymore, we return 0. 17 18 Finally, we save the max we see 4-dimensionally in a variable, and 19 add it to our cache before returning it, so that other recursive calls 20 of the function can use our computation. 21 """ 22 m, n = len(matrix), len(matrix[0]) 23 cache = {} 24 25 def inbounds(y, x): 26 return 0 <= y < m and 0 <= x < n 27 28 def dfs(y, x, prev): 29 if not inbounds(y, x) or matrix[y][x] <= prev: 30 return 0 31 if (y, x) in cache: 32 return cache[(y, x)] 33 34 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 35 ans = 1 + max(dfs(dy + y, dx + x, matrix[y][x]) for dy, dx in dirs) 36 cache[(y, x)] = ans 37 return ans 38 39 for y in range(m): 40 for x in range(n): 41 dfs(y, x, -inf) 42 43 return max(cache.values()) 44 45 46# @leet end 47 48 49def test(): 50 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def longestIncreasingPath(self, matrix: list[list[int]]) -> int: 8 """ 9 This question asks us to find the longest increasing path in a matrix 10 We can do this by DFSing through the entire matrix, keeping track of 11 the previous value to make sure our number is always strictly increasing, 12 but this would have a time complexity of $O(2^n)$. 13 We want and $O(n)$ solution, and we can get one with caching. We first 14 define a cache, which holds the longest increasing path from this node. 15 Then, we dfs through, checking the cache to see if we've already visited 16 that node. If we have, we return that, if we go out of bounds or if 17 we aren't increasing anymore, we return 0. 18 19 Finally, we save the max we see 4-dimensionally in a variable, and 20 add it to our cache before returning it, so that other recursive calls 21 of the function can use our computation. 22 """ 23 m, n = len(matrix), len(matrix[0]) 24 cache = {} 25 26 def inbounds(y, x): 27 return 0 <= y < m and 0 <= x < n 28 29 def dfs(y, x, prev): 30 if not inbounds(y, x) or matrix[y][x] <= prev: 31 return 0 32 if (y, x) in cache: 33 return cache[(y, x)] 34 35 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 36 ans = 1 + max(dfs(dy + y, dx + x, matrix[y][x]) for dy, dx in dirs) 37 cache[(y, x)] = ans 38 return ans 39 40 for y in range(m): 41 for x in range(n): 42 dfs(y, x, -inf) 43 44 return max(cache.values())
def
longestIncreasingPath(self, matrix: list[list[int]]) -> int:
7 def longestIncreasingPath(self, matrix: list[list[int]]) -> int: 8 """ 9 This question asks us to find the longest increasing path in a matrix 10 We can do this by DFSing through the entire matrix, keeping track of 11 the previous value to make sure our number is always strictly increasing, 12 but this would have a time complexity of $O(2^n)$. 13 We want and $O(n)$ solution, and we can get one with caching. We first 14 define a cache, which holds the longest increasing path from this node. 15 Then, we dfs through, checking the cache to see if we've already visited 16 that node. If we have, we return that, if we go out of bounds or if 17 we aren't increasing anymore, we return 0. 18 19 Finally, we save the max we see 4-dimensionally in a variable, and 20 add it to our cache before returning it, so that other recursive calls 21 of the function can use our computation. 22 """ 23 m, n = len(matrix), len(matrix[0]) 24 cache = {} 25 26 def inbounds(y, x): 27 return 0 <= y < m and 0 <= x < n 28 29 def dfs(y, x, prev): 30 if not inbounds(y, x) or matrix[y][x] <= prev: 31 return 0 32 if (y, x) in cache: 33 return cache[(y, x)] 34 35 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 36 ans = 1 + max(dfs(dy + y, dx + x, matrix[y][x]) for dy, dx in dirs) 37 cache[(y, x)] = ans 38 return ans 39 40 for y in range(m): 41 for x in range(n): 42 dfs(y, x, -inf) 43 44 return max(cache.values())
This question asks us to find the longest increasing path in a matrix We can do this by DFSing through the entire matrix, keeping track of the previous value to make sure our number is always strictly increasing, but this would have a time complexity of $O(2^n)$. We want and $O(n)$ solution, and we can get one with caching. We first define a cache, which holds the longest increasing path from this node. Then, we dfs through, checking the cache to see if we've already visited that node. If we have, we return that, if we go out of bounds or if we aren't increasing anymore, we return 0.
Finally, we save the max we see 4-dimensionally in a variable, and add it to our cache before returning it, so that other recursive calls of the function can use our computation.
def
test():