What's the expected running time for Python solution?


  • 1
    S

    I've got a solution running one test case in 20ms but still got TLE, so I wonder what the expected running time is for Python. I'm still checking the code though.

    >> timeit Solution().fourSum([-494,-474,-425,-424,-391,-371,-365,-351,-345,-304,-292,-289,-283,-256,-236,-236,-236,-226,-225,-223,-217,-185,-174,-163,-157,-148,-145,-130,-103,-84,-71,-67,-55,-16,-13,-11,1,19,28,28,43,48,49,53,78,79,91,99,115,122,132,154,176,180,185,185,206,207,272,274,316,321,327,327,346,380,386,391,400,404,424,432,440,463,465,466,475,486,492], -1211)
    >> 10 loops, best of 3: 19.9 ms per loop
    

    The idea is to cache sum of two numbers in a dict and check if there are two numbers that add up to the remainder using strategy of two sum.

    Edit: include by far the fastest code I've gotten

    10 loops, best of 3: 158 ms per loop

    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, nums, target):
            nums = sorted(nums)
        
            result = set()
            for b in xrange(1, len(nums) - 2):
                # stores sub_sums for the new num index just moved on
                sub_sums = {}
            
                for a in xrange(b):
                    sub_sums[nums[a] + nums[b]] = [nums[a], nums[b]]
            
                for c in xrange(b + 1, len(nums) - 1):
                    for d in xrange(c + 1, len(nums)):
                        remainder = target - nums[c] - nums[d]
                        if remainder in sub_sums:
                            result.add(tuple(
                               sub_sums[remainder]  + [nums[c], nums[d]]))
        
            return map(list, result)

  • 0
    S

    Reduced this down to within 10ms, but still TLE on the case

    [91277418,66271374,38763793,4092006,11415077,60468277,1122637,72398035,-62267800,22082642,60359529,-16540633,92671879,-64462734,-55855043,-40899846,88007957,-57387813,-49552230,-96789394,18318594,-3246760,-44346548,-21370279,42493875,25185969,83216261,-70078020,-53687927,-76072023,-65863359,-61708176,-29175835,85675811,-80575807,-92211746,44755622,-23368379,23619674,-749263,-40707953,-68966953,72694581,-52328726,-78618474,40958224,-2921736,-55902268,-74278762,63342010,29076029,58781716,56045007,-67966567,-79405127,-45778231,-47167435,1586413,-58822903,-51277270,87348634,-86955956,-47418266,74884315,-36952674,-29067969,-98812826,-44893101,-22516153,-34522513,34091871,-79583480,47562301,6154068,87601405,-48859327,-2183204,17736781,31189878,-23814871,-35880166,39204002,93248899,-42067196,-49473145,-75235452,-61923200,64824322,-88505198,20903451,-80926102,56089387,-58094433,37743524,-71480010,-14975982,19473982,47085913,-90793462,-33520678,70775566,-76347995,-16091435,94700640,17183454,85735982,90399615,-86251609,-68167910,-95327478,90586275,-99524469,16999817,27815883,-88279865,53092631,75125438,44270568,-23129316,-846252,-59608044,90938699,80923976,3534451,6218186,41256179,-9165388,-11897463,92423776,-38991231,-6082654,92275443,74040861,77457712,-80549965,-42515693,69918944,-95198414,15677446,-52451179,-50111167,-23732840,39520751,-90474508,-27860023,65164540,26582346,-20183515,99018741,-2826130,-28461563,-24759460,-83828963,-1739800,71207113,26434787,52931083,-33111208,38314304,-29429107,-5567826,-5149750,9582750,85289753,75490866,-93202942,-85974081,7365682,-42953023,21825824,68329208,-87994788,3460985,18744871,-49724457,-12982362,-47800372,39958829,-95981751,-71017359,-18397211,27941418,-34699076,74174334,96928957,44328607,49293516,-39034828,5945763,-47046163,10986423,63478877,30677010,-21202664,-86235407,3164123,8956697,-9003909,-18929014,-73824245], -236727523
    

    with running time about 150ms.


  • 0
    S

    I think for many problems (like this one), it also makes more sense to expect the result to be a set of tuples for Python.

    I understand it now: Line 32: Exception: Type <type 'set'>: Not implemented


  • 5
    S

    Just tried to translate the answer here and got AC. Local running time is less than 30ms.

    10 loops, best of 3: 26.7 ms per loop

    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, nums, target):
            nums = sorted(nums)
            result = set()
            cache  = collections.defaultdict(set)
        
            for i in range(len(nums)):
                for j in range(i + 1, len(nums)):
                    for half in cache[target - nums[i] - nums[j]]:
                        result.add(tuple(list(half) + [nums[i], nums[j]]))
            
                for j in range(i):
                    cache[nums[i] + nums[j]].add((nums[j], nums[i]))
        
            return map(list, result)
    

  • 0
    S

    It's essentially the reverse of my prior algo, regarding both which to put in hashtable and scan direction.

    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, nums, target):
            nums = sorted(nums)
            result = set()
            cache = collections.defaultdict(set)
            for b in xrange(1, len(nums) - 2):
                for a in xrange(b):
                    cache[nums[a] + nums[b]].add((nums[a], nums[b]))
    
                c = b + 1
                for d in xrange(c + 1, len(nums)):
                    remainder = target - nums[c] - nums[d]
                    for half in cache[remainder]:
                        result.add(tuple(list(half)  + [nums[c], nums[d]]))
    
            return map(list, result)

  • 0
    A

    Nice Solution and pretty neat


  • 0
    E

    Cool idea.

    My algorithm, 100 loops, best of 3: 15.6 ms per loop using itertools.product:

    def fourSum(self, num, target):
        sz, two_sums = len(num), collections.defaultdict(list)
        for i in range(sz - 1):
            for j in range(i+1, sz):
                # append indexes, rather than numbers
                two_sums[num[i] + num[j]].append((i, j))
    
        res = set()
        for two_sum in two_sums:
            rest = target - two_sum
            if rest in two_sums:
                for p1, p2 in itertools.product(two_sums[two_sum],
                                                two_sums[rest]):
                    if len(set(p1 + p2)) == 4:
                        # no duplicate indexes
                        q = sorted([num[p1[0]], num[p1[1]],
                                    num[p2[0]], num[p2[1]]])
                        res.add(tuple(q))
        return map(list, res)
    

Log in to reply
 

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