15. 3 Sum

Description

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

Solution

This builds off of the Two Sum problem that uses the two pointer solution. I found these posts helpful to understand 3Sum:

• https://en.wikipedia.org/wiki/3SUM

• https://fizzbuzzed.com/top-interview-questions-1/

Below are two implementations. The first uses a set to handle duplicates results. The other handles duplicates results by skipping them using the two pointer trick.

Set solution

The first step is to sort the array. This will let us skip duplicate numbers in the nums array. We don't need to process duplicate numbers as we already found the solution(s) for that number. The sorted array will also allow us to look for solution items.

We want to find three numbers that sum to zero: a + b + c = 0. We can set 'a' to be the current item when iterating through the array. Then we need to find b,c that when added with 'a' will equal zero. Since 'a' is fixed for the iteration, we can then use a start and an end pointer to scan the rest of the array to see if there are b,c values that will satisfy the condition.

If the result of a + b + c > 0 then the end pointer will be decremented in an attempt to find zero in the next iteration. If the sum in less than zero then the start pointer will be incremented.

When a solution is found, a + b + c = 0, then we add it to the set. We continue looking in that iteration for other b,c that may satisfy the condition.

Example:

nums = [-1,0,1,2,-1,-4]

nums sorted = [-4, -1, -1, 0, 1, 2]

The below table shows the first two iterations. The first iteration does not find a solution. The second iteration finds a solution.

iteration	a	start index	end index	b	c
0	-4	1	5	-1	2
		2	5	-1	2
		3	5	0	2
		4	5	1	2
1	-1	2	5	-1	2

 class Solution:   
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()
        for i in range(len(nums) - 2):
            a = nums[i]
            # skip duplicate numbers
            if i > 0 and a == nums[i - 1]:
                continue
            start = i + 1
            end = len(nums) - 1
            while start < end:
                b = nums[start]
                c = nums[end]
                if a + b + c == 0:
                    result.add((a, b, c))
                    start += 1
                    end -= 1
                elif a + b + c > 0:
                    end -= 1
                else:
                    start += 1
        return list(map(list, result))

Skipping "Two pointer trick" Solution

The main algorithm is the same as above. However, instead of using a set to store the result, an array is used to store the result. Duplicate results are avoided by skipping duplicate numbers. In the outer loop we skip duplicate numbers. But in the inner while loop we can skip duplicate numbers as well. We do this by incrementing the start pointer past any duplicates. We also decrement the end pointer before any duplicates as well.

Example

nums = [-1,0,1,2,-1,-4, 2]

nums sorted = [-4, -1, -1, 0, 1, 2, 2]

In the second iteration, when the index is 1, and a = -1, the algorithm will find a solution of [-1, -1, 2]. In order to not get a duplicate result, start will increment past the second -1. The start index will be 3. The end pointer will decrement to before the first 2.The end index will be 4.

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            a = nums[i]
            # skip duplicate numbers
            if i > 0 and a == nums[i - 1]:
                continue
            start = i + 1
            end = len(nums) - 1
            while start < end:
                b = nums[start]
                c = nums[end]
                summ = a + b + c
                if summ == 0:
                    result.append([a, b, c])
                    # the while loops below are what lets us use an array rather than a set to store the result (since
                    # duplicates are not allowed). Here duplicate numbers are skipped by.
                     while start < end and b == nums[start]:
                        start += 1
                    while start < end and c == nums[end]:
                        end -= 1
                elif summ > 0:
                    end -= 1
                else:
                    start += 1

        return result

Test Cases

input	result
[-1, 0, 1, 2, -1, -4]	[[-1, -1, 2], [-1, 0, 1]]
[]	[]
[0]	[]
[-25, -10, -7, -3, 2, 4, 8, 10]	[-10, 2, 8], [-7, -3, 10]