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
. Space complexity of 3sum problem is
or .
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.
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.
3 <= nums.length
<= 3000
-105 <= nums[i]
<= 105
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.
Let’s test if you’ve got the hang of the problem with a short quiz.
Which of the following are the unique triplets that sum to zero?
Input: nums = [-1, 0, 1, 2, -1, -4]
[-1, 0, 1], [1, 2, -3]
[0, 0, 0], [-1, 0, 1]
[-1, 0, 1], [-1, -1, 2]
[-4, 0, 4], [1, 1, -2]
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:
Sort the input array nums
in non-decreasing order.
Initialize result:
Create an empty list, res
, to store the unique triplets.
Iterate through array elements:
For each element a
at index i
in the array:
If a
is the same as the previous element, skip this iteration to avoid duplicate triplets.
Two pointer search:
For each element a
, set two pointers:
l
as the element immediately after a
.
r
as the last element in the array.
While l
is less than r
:
Calculate the sum of the triplet formed by a
, nums[l]
, and nums[r]
.
If the sum is greater than zero, move the right pointer r
to the left (decrement r
).
If the sum is less than zero, move the left pointer l
to the right (increment l
).
If the sum equals zero, add the triplet [a, nums[l], nums[r]]
to the result list res
.
Move the left pointer l
to the right, skipping over duplicate values to ensure unique triplets.
Return result:
After completing the iterations, return the list res
containing all unique triplets that sum to zero.
Let’s have a look at the code for the problem we just discussed:
def threeSum(nums):res = []nums.sort()for i, a in enumerate(nums):if i > 0 and a == nums[i-1]:continuel, r = i+1, len(nums)-1while l < r:threeSum = a + nums[l] + nums[r]if threeSum > 0:r -= 1elif threeSum < 0:l += 1else:res.append([a, nums[l], nums[r]])l += 1while nums[l]==nums[l-1] and l < r:l += 1return res# Driver codedef 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()
The above solution has a time complexity of
The above solution has a space complexity of
Free Resources