Three Sum

Array
Medium

Approach

Sort

nums

and iterate to

len(nums) - 2

tracking

middlePointer

. Continue if

nums[middlePointer]

equals

nums[middlePointer - 1]

to prevent duplicates. Use two pointers:

leftPointer

and

rightPointer

. Because

nums

is sorted,

nums[rightPointer]

will always be greater than

nums[middlePointer]

. Calculate

curSum

by adding the numbers at each of our pointers. If

curSum

is too small, increment

leftPointer

and continue. If

curSum

is too large, decrement

rightPointer

and continue. Otherwise, we have three new numbers that sum to zero. Add them to

uniqueTriplets

. To prevent duplicates, increment

leftPointer

and decrement

rightPointer

until they point to new numbers.

Diagrams

Analysis

Time

O(n^2)

Space

O(n)
class Solution:
    def threeSum(self, nums):
        uniqueTriplets = []
        nums.sort()
        
        # Stop at len(nums) - 2 because searching for 3 numbers
        # middlePointer and rightPointer cannot point to same number
        for middlePointer in range(len(nums) - 2):
            curNum = nums[middlePointer]
            prevNum = nums[middlePointer - 1]

            if middlePointer > 0 and curNum == prevNum:
                continue

            leftPointer, rightPointer = middlePointer + 1, len(nums) - 1

            while leftPointer < rightPointer:
                curSum = nums[middlePointer] + nums[leftPointer] + nums[rightPointer]
                if curSum < 0:
                    leftPointer += 1
                elif curSum > 0:
                    rightPointer -= 1
                else:
                    uniqueTriplets.append((nums[middlePointer], nums[leftPointer], nums[rightPointer]))
                    while leftPointer < rightPointer and nums[leftPointer] == nums[leftPointer + 1]:
                        leftPointer += 1
                    while leftPointer < rightPointer and nums[rightPointer] == nums[rightPointer - 1]:
                        rightPointer -= 1
                    leftPointer += 1
                    rightPointer -= 1

        return uniqueTriplets

Learn

#Two Pointers

Videos