3Sum—LeetCode

Key takeaways:
The 3Sum problem involves finding all unique triplets in an array that equals zero.
Steps of the algorithm are:
Sort the input array in non-decreasing order.
Create an empty list to store unique triplets.
For each element a, skip duplicates and check for pairs using two pointers.
Set two pointers—one immediately after a and one at the end of the array. Adjust the pointers based on the sum of the triplets until all unique triplets are found.
After iterating through the array, return the list of unique triplets.
Time complexity of 3sum problem is $O(n^2)$ .
Space complexity of 3sum problem is $O(1)$ or $O(n)$ .

The 3Sum problem is a classic algorithmic problem that involves finding all unique triplets in an array that sum up to a target value of zero. Given an array of n integers, we need to check sets of three elements in the array sequentially. If the sum of these three values equals zero, it indicates a unique triplet. However, if such a sum doesn’t occur, we move on to the next set of three integers.

Problem statement

Given an array, nums, containing n integers, determine if elements a, b, and c are within the array such that their sum equals zero (i.e., a + b + c = 0). The elements a, b, and c represent nums[0], nums[1], and nums[2] respectively. Find and return all unique triplets from the array that satisfy this condition. Additionally, the solution set must not include any duplicate triplets.

Constraints

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

Example

Explanation of the above example

The sums of distinct triplets in the given array of the above example are as follows:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0

Thus, the unique triplets are [-1, 0, 1] and [-1, -1, 2]. It is important to emphasize that the order in which the triplets are returned and the order of the elements within each triplet does not matter.

Knowledge test

Let’s test if you’ve got the hang of the problem with a short quiz.

Algorithm to solve 3Sum LeetCode problem

For this problem, we’ll make slight changes to the two pointer approach. As we need to find the three elements that sum to zero, we'll follow the approach given below:

Sort the array:
1. Sort the input array nums in non-decreasing order.
Initialize result:
1. Create an empty list, res, to store the unique triplets.
Iterate through array elements:
1. For each element a at index i in the array:
  1. If a is the same as the previous element, skip this iteration to avoid duplicate triplets.
Two pointer search:
1. For each element a, set two pointers:
  1. l as the element immediately after a.
  2. r as the last element in the array.
2. While l is less than r:
  1. Calculate the sum of the triplet formed by a, nums[l], and nums[r].
  2. If the sum is greater than zero, move the right pointer r to the left (decrement r).
  3. If the sum is less than zero, move the left pointer l to the right (increment l).
  4. If the sum equals zero, add the triplet [a, nums[l], nums[r]] to the result list res.
    1. Move the left pointer l to the right, skipping over duplicate values to ensure unique triplets.
Return result:
1. After completing the iterations, return the list res containing all unique triplets that sum to zero.

def threeSum(nums):
  res = []
  nums.sort()
  for i, a in enumerate(nums):
    if i > 0 and a == nums[i-1]:
      continue
        
    l, r = i+1, len(nums)-1
    while l < r:
      threeSum = a + nums[l] + nums[r]
      if threeSum > 0:
        r -= 1
      elif threeSum < 0:
        l += 1
      else:
        res.append([a, nums[l], nums[r]])
        l += 1
        while nums[l]==nums[l-1] and l < r:
          l += 1
  return res
# Driver code
def main():
    nums = [
        [-1,0,1,2,-1,-4],
        [0,1,1],
        [0,0,0]
    ]
    for i in range(len(nums)):
        print(i + 1, ". \t Input Array: ", nums[i], sep="")
        print("\t Unique triplets that sum up to zero: ",
                (threeSum(nums[i])))
        print("-" * 95)
if __name__ == "__main__":
    main()

Code implementation in six langauges