[Leetcode]15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

This is extended from [Leetcode]1. Two Sum – if we fix one number nums[i] at a time, then it’s a Two Sum now: to find two numbers a and b such that a+b=nums[i].

Logic 1 – Two pointers

Since it asks for the number but not index, we can sort the array first and apply two pointers: to find two numbers a and b such that a+b=nums[i], we use two pointers left=i+1 (instead of 0 to avoid repetition) and right=len(nums)-1; if nums[a]+nums[b]<nums[i], we move left to the right; if nums[a]+nums[b]>nums[i], we move right towards the left.

Python:

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ret = []
for i in range(n-2):
# nums[i]>0 means nums[l] and nums[r]
# will be larger than 0. Not possible.
if nums[i] > 0:
break
# to avoid repetition
if i > 0 and nums[i] == nums[i-1]:
continue
l,r = i+1,n-1
while l<r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l+=1
elif total > 0:
r -= 1
else:
ret.append([nums[i], nums[l], nums[r]])
# to avoid repetition
while l < r and nums[l]==nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return ret


Logic 2 – Binary search

Logic 1 achieves O(n^2) and it performs well in C++ and Java: it beats >90\%. However, in Python, it only beats <30\%. Therefore I looked into some of the fast submissions and found the following solution. I cannot track the author so I have nowhere to refer to, yet I’d like to declare that the following solution is borrowed from Leetcode.

Generally speaking, it also selects one element num at a time and search for the other two a and b if they exist. What’s different is that, instead of applying two-pointer to check the subarray, it stores the collections.Counter of the array first, then uses binary search to set a search range, and search through that range.

1. With using counter, it needs to handle different cases separately to avoid redundancy:
case i. three numbers are the same – the only possible solution is [0,0,0]
case ii. two numbers are the same – needs to check against counter to ensure counter[num] > 1 and -2 * num in counter
case iii. all of them are different
2. bisect_left
the leftmost boundary for searching would be the smallest element to the right of i+1, that’s why the value is set to opposite - nums[-1]
3. bisect_right
we choose opposite / 2 over opposite-nums[left] to deal with repeated solutions.
For example, given [-1,0,1], and num=-1, we only wish to search [0] to get [-1,0,1], instead of searching [0,1] which leads to [-1,0,1],[-1,1,0]
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
counter = collections.Counter(nums)
nums = sorted(counter)
ret = []
for i, num in enumerate(nums):
# case i. three numbers are the same - [0,0,0]
if num==0:
if counter[num] > 2:
ret.append([0, 0, 0])
# case ii. two numbers are the same
elif counter[num] > 1 and -2 * num in counter:
ret.append([num, num, -2 * num])
# case iii. not any of the three numbers are the same
if num < 0:
opposite = -num
left = bisect_left(nums, opposite - nums[-1], i + 1)
right = bisect_right(nums, opposite / 2, left)
for a in nums[left:right]:
b = opposite - a
if b in counter and a!=b:
ret.append([num, a, b])
return ret

Subscribe
Notify of