Why my code TLE? Python, O(n^2)

  • 0
    class Solution:
        # @return a list of lists of length 3, [[val1,val2,val3]]
        def threeSum(self, num):
            if len(num)<3:
                return array
            for i in xrange(len(num)):
                for j in xrange(i+1,len(num)):
                    if -(num[i]+num[j]) in num and sorted([num[i],num[j],-(num[i]+num[j])]) not in array and num.index(-(num[i]+num[j]))!=i and num.index(-(num[i]+num[j]))!=j:
            return array

  • 0

    num in your code is a list. So the -(num[i] + num[j]) in num will take O(n) time to find whether the element is in the list. So the total time complexity of your code is O(n^3).

Log in to reply

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