4Sum

Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch thata+b+c+d= target? Find all unique quadruplets in the array which gives the sum of target.

Note:The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution:

O(n^3)

Three sum idea: fix the first element, then do bidirectional processing on the following elements.

same logic as three sum. Fix the first two elements. But remember to check duplicates for first two points

class Solution(object):
    def fourSum(self, nums, targetOriginal):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        n = len(nums)
        nums.sort()
        p1 = 0

        res = []

        while p1 < n - 3:
            p2 = p1 + 1

            # classic three sum iteration
            while p2 < n - 2:
                l = p2 + 1
                r = n - 1
                target = targetOriginal - (nums[p1] + nums[p2] )

                # classic two sum iteration
                while l < r:

                    if nums[l] + nums[r] == target:
                        res.append([ nums[p1], nums[p2], nums[l], nums[r]])
                        l += 1
                        r -= 1
                    elif nums[l] + nums[r] < target:
                        l += 1
                    else:
                        r -= 1

                    # avoid duplicate on l and r indices
                    while l < r and l > p2 + 1 and nums[l] == nums[l-1]:
                        l += 1
                    while l < r and r < n - 1 and nums[r] == nums[r+1]:
                        r -= 1
                p2 += 1
                # avoid duplicates on p2 
                while p2 < n - 2 and nums[p2] == nums[p2 - 1]:
                    p2 += 1

            p1 += 1
            # avoid duplicates on p1
            while p1 < n - 3 and nums[p1] == nums[p1 - 1]:
                p1 += 1
        return res

Approach 2:

Time: O(n^2)

Space: O(n^2)

Create a 2 pair combinations for the entire array and store them into a hashmap. Key being the 2sum, value being a list of index pairs(tuple) that summed up to key. -- O(n^2) time and space

Go through the key set of the hashmap. For each key A, find B = target - A. -- O(1) look up time for n times

the values returned will be a list of tuples from A, and another list of tuples from B. Pair each of them up individually to check there's no duplicates of indices. - constant time.

Thus, total time complexity is O(n^2)