[Leetcode]15. 3Sum

Given an array nums of n integers, are there elements abc 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
guest
0 Comments
Inline Feedbacks
View all comments