Why is Python O(n^3) TLE


  • 0
    Z
    class Solution(object):
        def fourSum(self, nums, target):
            n = len(nums)
            if n < 4:
                return []
            nums = sorted(nums)
            combo = [None, None, None, None]
            res = []
            
            i = 0
            while i <= n-4 and nums[i]*4 <= target:
                combo[0] = nums[i]
                j = i + 1
                while j <= n-3 and nums[j]*3 + nums[i] <= target:
                    combo[1] = nums[j]
                    p = j + 1
                    q = n - 1
                    while p < q and nums[j] + nums[i] + nums[p]*2 <= target:
                        combo[2] = nums[p]
                        combo[3] = nums[q]
                        if sum(combo) <= target:
                            res.append(combo[:]) if sum(combo) == target else None
                            while p < q and nums[p] == combo[2]:
                                p += 1
                        else:
                            while q > p and nums[q] == combo[3]:
                                q -= 1
                    while j <= n-3 and nums[j] == combo[1]:
                        j += 1
                while i <= n-4 and nums[i] == combo[0]:
                    i += 1
            return res

  • 1
    Z
    class Solution:
        def fourSum(self, nums, target):
            index_pairs = dict()
            combos = dict()
            n = len(nums)
            for i in range(0,n):
                for j in range(i+1,n):
                    sum = nums[i] + nums[j]
                    if index_pairs.get(target - sum) is not None:
                        for pair in index_pairs[target - sum]:
                            if i != pair[0] and i != pair[1] and j != pair[0] and j != pair[1]: # Avoid overuse
                                combo = sorted((nums[i], nums[j], nums[pair[0]], nums[pair[1]])) # Avoid duplicate
                                combos[tuple(combo)] = True
    
                    if index_pairs.get(sum) is not None:
                        index_pairs[sum].append((i,j))
                    else:
                        index_pairs[sum] = [(i,j)]
    
            return combos.keys()
    

    And I wonder why there isn't discussion on O(n^2) time O(n^2) space solution?
    Though this only beats 55%


  • 0

    "there isn't discussion on O(n^2) time"

    There is, for example here.


Log in to reply
 

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