Conceptually correct Python solution exceeding time limit


  • 1
    A

    I wrote a fairly simple solution for this problem based on topologically sorting the elements of the matrix and then getting the LIS with DP (inspired by Magnus Hetland's book). I believe the solution is correct, because it passes the initial test case and a few other custom test cases that I tried out. Unfortunately, it's exceeding the time limit for some of the larger test cases. I've written it out iteratively so that the recursion doesn't hit Python's maximum recursion depth, but that doesn't seem to be doing anything for my efficiency either. Any thoughts on how I would go about improving this solution?

    def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if len(matrix) == 0: return 0
            G = {(i, j):set() for i in range(len(matrix)) for j in range(len(matrix[i]))}
            for i in range(len(matrix)):
                for j in range(len(matrix[i])):
                    if i != 0:
                        if matrix[i][j] < matrix[i-1][j]: G[(i,j)].add((i-1, j))
                    if i != len(matrix)-1:
                        if matrix[i][j] < matrix[i+1][j]: G[(i,j)].add((i+1, j))
                    if j != 0:
                        if matrix[i][j] < matrix[i][j-1]: G[(i,j)].add((i, j-1))
                    if j != len(matrix[i])-1:
                        if matrix[i][j] < matrix[i][j+1]: G[(i,j)].add((i, j+1))
            
            counts = {u: 0 for u in G}
            for u in G:
                for v in G[u]:
                    counts[v] += 1
            
            Q = deque([u for u in G if counts[u] == 0])
            topsort = []
            
            while Q:
                e = Q.popleft()
                for v in G[e]:
                    counts[v] -= 1
                    if counts[v] == 0: Q.append(v)
                topsort.append(e)
            
            res = [1]*len(topsort)
            for i in range(len(topsort)):
                for j in range(i):
                    if topsort[i] in G[topsort[j]]:
                        res[i] = max(res[i], 1 + res[j])
            
            return max(res)

Log in to reply
 

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