Why is this Python solution not fast enough to pass OJ?


  • 0
    D
    def numSquares(self, n):
        if not n: return 0
        memo, squares = [], []
        i = 1
        while len(memo) < n:
            if len(memo) == i*i-1:
                memo.append(1)
                squares.append(i*i)
                i += 1
            else:
                memo.append(min(memo[-s] for s in squares) + 1)
        return memo[-1]
    

    I came up with this solution and couldn't figure out how to make fast enough for OJ. When I was looking through the solution sharing, I saw that this is very similar to the static DP solution that is floating around. But what makes my solution so much slower?


Log in to reply
 

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