forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
longest-increasing-path-in-a-matrix.py
60 lines (54 loc) · 1.65 KB
/
longest-increasing-path-in-a-matrix.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Time: O(m * n)
# Space: O(m * n)
# Given an integer matrix, find the length of the longest increasing path.
#
# From each cell, you can either move to four directions: left, right, up
# or down. You may NOT move diagonally or move outside of the boundary
# (i.e. wrap-around is not allowed).
#
# Example 1:
#
# nums = [
# [9,9,4],
# [6,6,8],
# [2,1,1]
# ]
# Return 4
# The longest increasing path is [1, 2, 6, 9].
#
# Example 2:
#
# nums = [
# [3,4,5],
# [3,2,6],
# [2,2,1]
# ]
# Return 4
# The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
# DFS + Memorization solution.
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix:
return 0
def longestpath(matrix, i, j, max_lengths):
if max_lengths[i][j]:
return max_lengths[i][j]
max_depth = 0
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
for d in directions:
x, y = i + d[0], j + d[1]
if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and \
matrix[x][y] < matrix[i][j]:
max_depth = max(max_depth, longestpath(matrix, x, y, max_lengths));
max_lengths[i][j] = max_depth + 1
return max_lengths[i][j]
res = 0
max_lengths = [[0 for _ in xrange(len(matrix[0]))] for _ in xrange(len(matrix))]
for i in xrange(len(matrix)):
for j in xrange(len(matrix[0])):
res = max(res, longestpath(matrix, i, j, max_lengths))
return res