Confused about TLE in python


  • 0
    S

    Here are two pieces of codes, both in python. They are doing the same thing. However, the first one is time-limit-exceeded, while the second one doesn't. I am confused....Anyone can help me? The only difference is that in Code 1, it defines a global variable.

    Code 1

    class Solution(object):
     _res = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = self._res
        while len(res) <=n:
            res += [min([res[-i*i] for i in range(1,int(len(res)**0.5)+1)]) +1]
        return res[n]
    

    Code 2

    class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = [0]
        while len(res) <=n:
            res += [min([res[-i*i] for i in range(1,int(len(res)**0.5)+1)]) +1]
        return res[n]

  • 0
    Z

    Quote from here for Python:

    "Variables declared inside the class definition, but not inside a method are class or static variables"

    Typical code 1 in static typing is

    class Solution(object):
        res = [0]
        def numSquares(self, n):
            while len(self.res) <=n:
                self.res += [min([self.res[-i*i] for i in range(1,int(len(self.res)**0.5)+1)]) +1]
            return self.res[n]
    

    if you re-declare self.res you will get TLE as you change back to dynamic typing:

    class Solution(object):
        res = [0]
        def numSquares(self, n):
            self.res = [0]     # re-declare
            while len(self.res) <=n:
                self.res += [min([self.res[-i*i] for i in range(1,int(len(self.res)**0.5)+1)]) +1]
            return self.res[n]
    

    My understanding is static typing is faster as (a) no wasting time in checking type and (b) use previous results if there are many tests.


  • 0
    S

    Thanks! That helps a lot.


Log in to reply
 

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