Short Python...


  • 12

    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])

  • 0
    G

    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"


  • 0
    E

    Can you please post a blog / video explaining?


  • 0

    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.


  • 2

    @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 :-)


  • 0

    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


  • 0

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


  • 0

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


  • 0
    W

    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
    

  • 0
    S

    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


  • 0
    S

    @san-ag

    Never mind, I got it :)


Log in to reply
 

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