3Sum

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Approach 1:

I remembered to use a hashmap in 2 Sum question.

I thought I would be able to implement 2 Sum question with target value as the ith value of the nums array and iterate until i = len(nums) - 2. Since there can not be duplicate answers with different indices (ex [-1,0,1] and [0,1,-1]), I think I would use set data structure to store the returning lists.

1. Initialize the returning list and target as sets since we cannot have duplicate answers.
2. Add the ith value to the target set since we can skip any ith value that already checked for 3 sum previously.
3. Do 2 Sum checking if the rest of the array can sum up to the target value
4. Unlike returning the indices that sum up to zero, add the 3 elements to the result set by sorting them and overcasting them into a tuple

Implementation:

class Solution:


    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result, target = set(), set()
        for i in range(len(nums) - 2):
            if nums[i] not in target:
                target.add(nums[i])
                h = {}
                for j in range(i+1, len(nums)):
                    complement = - nums[i] - nums[j]
                    if complement in h:
                        result.add(tuple(sorted((nums[i],nums[j],complement))))
                    h[nums[j]] = j
        return result
        

Complexity Analysis:

Time Complexity:O(n^2) where n is the length of the list. We will minimize a repetitive search by utilizing sets

Space Complexity: O(n) for hashmap and sets

Approach 2:

While I did not come up with this solution and believe that my solution that does the job efficiently, there is another way to solve this questions.

It optimizes the solution with little tweaks such as sorting the list before anything, and having an early breaking point using the fact that it is a sorted list.

It goes through the list similarly, but has two pointers in the inner loop checking to see if elements can sum up to zero.

Implementation:

class Solution:

    # Two-Pointer Solution
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
        # if the current value is greater than zero, break from the loop as nums is sorted
            if nums[i] > 0:
                break
            if i == 0 or nums[i-1] != nums[i]:
                self.twoSumII(nums, i, res)
        return res
        
    def twoSumII(self, nums, i, res):
        lo,hi = i+1, len(nums) - 1
        while(lo < hi):
            sum = nums[i] + nums[lo] + nums[hi]
            if sum < 0:
                lo += 1
            elif sum > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and num[lo] == nums[lo-1]:
                    lo += 1
       

Complexity Analysis:

Time Complexity:O(n^2) where n is the length of the list

Space Complexity: O(log n) to O(n) depending on the sorting algorithm in the beginning of the array

Reflection

I am elated to finally solve a question without looking at the solution. The trickiest part is to get rid of all the duplicates while sorting the elements and remembering that sets only take tuples as elements helped a lot:)