# Is this 4Sum python solution O(N*N) in time complexity?

• ``````class Solution(object):
### run time is O(N*N)
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
#nums.sort()
length = len(nums)
d = dict()
for i in xrange(length):
for j in xrange(i+1, length):
val = nums[i] + nums[j]
if val in d:
d[val].append((i,j))
else:
d[val] = [(i,j)]
res = set()
for k in d:
val = target - k
if val in d:
vlist = d[val]
klist = d[k]
for (i,j) in vlist:
for (l,m) in klist:
ilist = [i,j,l,m]
if len(set(ilist)) != len(ilist):
continue
mylist = [nums[i], nums[j], nums[l], nums[m]]
mylist.sort()
res.add( tuple(mylist) )
return list(res)``````

• I don't think so.

The expected number of different key in your dictionary d is N and the number of elements is N^2. Thus the expected length of the list that each key hold is N.

So the loop

``````for k in d:
for (i, j) in vlist:
for(l, m) in klist:
``````

is O(N^3)

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