# Why is Python O(n^3) TLE

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

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

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

There is, for example here.

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