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


  • 0
    H
    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)

  • 1
    T

    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)


Log in to reply
 

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