# TLE python code

• 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``````

• 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.

• 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).

• 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.

• thxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx a lot.

It's a great optimization.

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