O(n^2) space complexity, worst case O(n^4) time complexity solutions


  • 0
    O
    def fourSum(self, nums, target):
        """
        - use O(n^2) to genereae all_pair and hash it with key 
          equal to pair_sum and value equal to **index tuple**!!
            - (The recent to hash with index is cuz u need th check 
               repeated element in each tuple)
        - then u can go through all all pair to check whether four 
          number's sum would be target!
        """
        nums.sort()
        ln, res = len(nums), []
        pairMap = collections.defaultdict(set)
        for i in range(ln - 1):
            for j in range(i + 1, ln):
                pairMap[nums[i] + nums[j]].add((i, j))
                
        for v in pairMap:
            if target - v in pairMap:
                for p1 in pairMap[v]:
                    for p2 in pairMap[target - v]:
                        #Then there would not be repeated element
                        if len(set(p1) | set(p2)) == 4: 
                            sol = tuple(sorted([nums[x] for x in (p1 + p2)])) 
                            # But still it might happend 
                            # (-1,  0, 0, 1) or (-1, 1, 0, 0)
                            # Since it's from all_pair and trnasformed 
                            # to (-1, 0) X (0, 1) and (-1, 1) X (0, 0)
                            if sol not in res:
                                res.append(sol)
        return res

  • 1

    "O(n^2) time complexity"

    That's impossible.

    Consider nums being the n numbers from 1 to n. Then there are Θ(n4) different quadruplets and Θ(n) possible sums, meaning at least one sum must have Ω(n3) different quadruplets. Which you can't generate in O(n2) time.

    And actually your solution is only O(n4). Just imagine nums = [0] * n and target = 0.


  • 0
    O

    yep u are right, let me change with my title, thanks~


  • 0

    Well, I just looked through older discussions here and you're by far not alone :-)
    Sooooo many people thought they had something faster than O(n^3)...


  • 0
    O

    haha, I just did it too. No wonder I'm quite struggling about how could 4sum run the same complexity with 3 sum before!


  • 0

    Good point, that comparison to 3Sum.


  • 0

    Haha, I just saw your new title. I think you'd better describe your question/solution, not my answer :-)

    In case you did that because you wanted to draw attention to my answer, don't worry, I also posted it as a standalone question (here).


Log in to reply
 

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