[Need Help] Python solution erring in TLE constantly


  • 0
    J

    Hello,

    I just get started on Python last week and am learning by coding. Here's two piece of code that I came up with for 3sum question, both are erring in TLE(Time Limit Exceed) on my end, and I can't figure out where went wrong at present, I would love to learn from any member of the community and any suggestion to optimize is greatly appreciated.

    I tried sorted/sort(), range/xrange, and they both result in TLE.

    '''
    result=[]

        sl=sorted(nums)
        #0123456789
        #i..l.....r
        for i in xrange(len(sl)-2):
            l=i+1
            r=len(sl)-1
            while(l<r):
                sum_=sl[i]+sl[l]+sl[r]
                if sum_<0:
                    l=l+1
                elif sum_>0:
                    r=r-1
                else:
                    sublist=[sl[i],sl[l],sl[r]]
                    if not sublist in result:
                        result.append(sublist)
                    l=l+1
        return result
    
    
    
    
        for i in xrange(len(sl)):
            target = -sl[i]
            for j in xrange(i+1,len(sl)):
                x=sl[j]
                if target-x in sl[j+1:len(sl)]:
                    if [-target,x,target-x] not in result:
                        result.append([-target,x,target-x])
        return result
    

    '''


  • 0
    Y

    @jack43 Hi there.
    Your second function is brute force O(n**3). For each i, get each j and look through all the other numbers. It's probably not possible to get around TLE with that approach.

    Your first solution is a better idea. The issue is with avoiding duplicate results. You look through the previous result list to check it's not a duplicate and this takes a long time.
    Better would be to make results a set and sublist a tuple. This way it's O(1) to check if a result has been found already. But I just tried that and it's still too slow.
    Even better is to move the pointers i, l and r past all identical numbers to avoid duplicates in the first place, rather than finding everything and checking for duplicates later. The code is a bit longer but runs much faster.

    There are plenty of good solutions in the discussion forum and for what its worth mine is here ...
    https://github.com/jakehoare/leetcode/blob/master/015_3Sum.py
    Keep practicing!


  • 0
    L

    Actually I found a new test case with list of ~3000 numbers is added and my previous accepted two pointers Python solution got TLE because of it. Now only dict Python solution can pass all the test cases in time.


Log in to reply
 

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