15. 3Sum

Medium

Problem:

Given an array, output three elements that can make the sum zero.

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.

https://leetcode.com/problems/3sum/

Solutions:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []

        left, right = 0, len(nums) - 1

        while left < len(nums) - 2:
            ptr = left + 1
            while ptr < right:
                if nums[left] + nums[ptr] + nums[right] == 0:
                    tmp = sorted([nums[left], nums[ptr], nums[right]])
                    # check duplicates
                    if tmp not in res:
                        res.append(tmp)
                    ptr += 1
                    while ptr < right and nums[ptr] == nums[ptr - 1]:
                        ptr += 1
                elif nums[left] + nums[ptr] + nums[right] < 0:
                    ptr += 1
                else:
                    right -= 1
            left += 1
            # Reset the right pointer
            right = len(nums) - 1

        return res

Two Pointers

1. Sort the array to easily handle the case where there are the same values back and forth.

2. The two pointers narrow the gap and calculate the sum: if the sum is less than 0, the value needs to be increased, so the left pointer moves to the right. If the sum is greater than 0, the value needs to be decreased, so the right pointer moves to the left.

3. As there can be the same values on both sides of the left and right, it is handled to skip these.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.append((nums[i], nums[left], nums[right]))
                    while left < right and nums[left] == nums[left + 1]
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        return results