user2914144 - 11 months ago 83

Python Question

I'm was working on this question (it's from Leetcode):

"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.

I keep running into a KeyError specifically:

`Traceback (most recent call last):`

File "/Users/Desktop/longest_increasing_path_in_a_matrix.py", line 41, in <module>

print(test.longestIncreasingPath(matrix))

File "/Users/Desktop/longest_increasing_path_in_a_matrix.py", line 31, in longestIncreasingPath

traverse(x, y, [])

File "/Users/Desktop/longest_increasing_path_in_a_matrix.py", line 5, in traverse

if traverse.traveled[str(x_coor) + "_" + str(y_coor)]:

KeyError: '0_0'

and I'm not sure exactly what I'm doing wrong. I understand it has to do with my dictionary. Please let me know if there is anything else I need to post:

`class Solution(object):`

def longestIncreasingPath(self, matrix):

def traverse(x_coor, y_coor, build):

key = str(x_coor) + "_" + str(y_coor)

if key in traverse.traveled and traverse.traveled[key]:

if traveled[str(x_coor) + "_" + str(y_coor)]:

return

elif x_coor < 0 or y_coor < 0 or x_coor >= len(matrix[0]) or y_coor >= len(matrix)-1:

return

elif len(build) > 0 and matrix[x_coor][y_coor] <= build[-1]:

if len(build) > traverse.count:

traverse.count = len(build)

return

traveled[str(x_coor) + "_" + str(y_coor)] = true

build.append(matrix[y_coor][x_coor])

traverse(x_coor, y_coor-1, build)

traverse(x_coor, y_coor+1, build)

traverse(x_coor+1, y_coor, build)

traverse(x_coor-1, y_coor, build)

build.pop()

del traveled[str(x_coor) + "_" + str(y_coor)]

traverse.count = 0

traverse.traveled = {}

for y in range(0, len(matrix)-1, 1):

for x in range(0, len(matrix[0]), 1):

traverse(x, y, [])

return(traverse.count)

matrix = [

[9,9,4],

[6,6,8],

[2,1,1]

]

test = Solution()

print(test.longestIncreasingPath(matrix))

Answer Source

You are trying to access a key (`0_0`

) that doesn't exist yet in the dictionary.

You have to check beforehand if it exists, I'd suggest the `in`

keyword:

```
key = str(x_coor) + "_" + str(y_coor)
if key in traverse.traveled and traverse.traveled[key]:
# ...
```

See also: Avoiding KeyError Exceptions