# Short Python...

• ## Solution 1

Bottom-up DP, about 480 ms.

``````def longestIncreasingPath(self, matrix):
matrix = {i + j*1j: val
for i, row in enumerate(matrix)
for j, val in enumerate(row)}
length = {}
for z in sorted(matrix, key=matrix.get):
length[z] = 1 + max([length[Z]
for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
or [0])
return max(length.values() or [0])
``````

## Solution 2

Top-down DP, about 560 ms.

``````def longestIncreasingPath(self, matrix):
def length(z):
if z not in memo:
memo[z] = 1 + max([length(Z)
for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
or [0])
return memo[z]
memo = {}
matrix = {i + j*1j: val
for i, row in enumerate(matrix)
for j, val in enumerate(row)}
return max(map(length, matrix) or [0])``````

• complex numbers as keys?! had no idea that was even possible in python. Someday you'll have to make a video explaining how you come up with this stuff. I suspect it will be along the lines of: "Write down the problem, think very hard, write down the answer"

• Can you please post a blog / video explaining?

• Whenever I finish a problem, I'll always search for your answers in discuss pages firstly.
Your solutions are literally extraordinary, I've never stop been shocked and learned enormous knowledge from them. Thank you so much.

• @grodrigues3 I'm not sure, but I might've gotten the complex numbers idea from veky's solution of a CheckIO problem.

@eran What needs explaining? The Python? The complex numbers? The algorithm(s)?

@waigx Good, shocks and learning is a major reason I post them :-)

• Just amazed and thankful for how much I am learning from your posts... If I ever get hired by a good company I need to offer you a beer. Don't worry, I'll also pay for flight ticket and hotel stay in US. Lol

• @StefanPochmann: just nitpicking... Your code doesn't work in Python 3. You need to substitute `for Z in z+1, z-1, z+1j, z-1j` with `for Z in (z+1, z-1, z+1j, z-1j)` to make it work.

• Hmm, interesting... that's a version difference I wasn't aware of yet. Thanks.

• hi, stefan, do you know how to speed up this code? and why his is faster than yours

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix:
return 0
w=len(matrix[0])
h=len(matrix)
bank=[[0]*w for i in range(h)]
for i in range(h):
for j in range(w):
stack=[(i,j,0)]
while stack:
iin,jin,k=stack.pop(0)
for x,y in (iin+1,jin),(iin-1,jin),(iin,jin+1),(iin,jin-1):
if -1<x<h and -1<y<w and matrix[x][y]>matrix[iin][jin]:
stack.append((x,y,k+1))
bank[x][y]=max(bank[x][y],k+1)
return max(max(a)for a in bank)+1
``````

• Hi Stefan

``````for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
``````

I am a bit confused here. Aren't we supposed to be moving in the increasing direction i.e matrix[Z] > matrix[z] ? Can you please explain?

Thanks

• @san-ag

Never mind, I got it :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.