TLE python code


  • 0
    S

    I think the time complexity is O(n^2). Don't know why it got TLE even on not a super large input. [7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6]
    I ran it on my own computer, the output is correct, so there is no infinite loop in the code. Any one else uses python and have similar issue?

    Share my code here

    def threeSum(self, num):
        length = len(num)
        if length < 3:
            return []
        num = self.sort(num)
        triplets = []
        for i in range(0, length-2):
            if i>=1 and num[i] == num[i-1]:
                continue
            j = i+1
            k = length-1
            while j<k:
                if j> i+1 and num[j] == num[j-1]:
                    j = j+1
                    continue
                if k<length-1 and num[k] == num[k+1]:
                    k = k-1
                    continue
                s = num[i] + num[j] + num[k]
                if s == 0:
                    triplets.append([num[i], num[j], num[k]])
                    j = j+1
                    k = k-1
                elif s>0:
                    k = k-1
                else:
                    j = j+1
        return triplets
    
    def sort(self, num):
        length = len(num)
        if length <= 1:
            return num
        middle = int((length-1)/2)
        left = self.sort(num[0:middle+1])
        right = self.sort(num[middle+1:length])
        
        new_num = []
        p1 = 0
        p2 = 0
        length1 = len(left)
        length2 = len(right)
        while p1<=length1-1 and p2<=length2-1:
            if left[p1] < right[p2]:
                new_num.append(left[p1])
                p1 = p1+1
            else:
                new_num.append(right[p2])
                p2 = p2+1
        if p1<= length1-1:
            new_num.extend(left[p1:length1])
        elif p2 <= length2-1:
            new_num.extend(right[p2:length2])
        return new_num

  • 0
    W

    same problem with you. I also implement a O(n^2) and get a TLE with the same input. I also check this on my computer and the answer is correct. Have no idea why it could be.


  • 0
    P

    I used the input data of TLE case for my submission to run it on my own computer and it cost only 14 ms. I think there must be something wrong with OJ (maybe the special judge is broken).


  • 0
    H

    One optimization is to add:

    if num[i] > 0:
        break;
    

    after

    for i in range(0, length-2):
        if i>=1 and num[i] == num[i-1]:
            continue
    

    This helped my python code get accepted.


  • 0
    M

    thxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx a lot.

    It's a great optimization.


Log in to reply
 

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