Leetcode 15: 3Sum

A classic use case of “sort, loop, and two pointers” pattern for arrays

Link to problem descriptions

Importance of sorting to 3sum problem

The most important trick in improving performance is to sort the input array in place before proceeding with array iterations. Sorting has an unavoidable cost — a good sorting algorithm such as quicksort or Timsort typically has a time complexity of O(nlogn) (average complexity of quicksort; worse-case complexity of python’s Timsort). However, the benefits outweigh the costs during array iterations:

1. For deduplication, sorting guarantees that repeating elements are next to each other, and thus only accounting for the first occurrence is easy to achieve by advancing the pointer until it points to a different element
2. For using two pointers to find element pairs that sum to a target value, a sorted array makes the movement much more predictable than a randomly ordered array. For a randomly ordered array, one would need to two a double loop to check each possible pair; for a sorted array, however, we check the sum against the target value and move the left or right pointers one increment at a time

“Two pointers” in brief

The two pointers method is an efficient method for solving array problems that aim at:

1. Finding two elements that satisfy a constraint (e.g., finding value pairs that sum to a target number)
2. Finding a contiguous subarray that satisfies a constraint (e.g., finding contiguous subarrays that sum to a target number)

Two pointers specific to 3Sum problem

Two pointers method takes different shape when solving different problems. Specific to 3Sum problem, we break down the main steps into the following:

1. Sort the input array in place
2. Set up outer loop to iterate through the sorted array from left to right
3. For each element we iterate at in the outer loop in 2 (i.e., element i), we apply two pointers method to the remaining elements in an inner loop to find all pairs that could sum to its additive inverse (i.e., -1 * element i)

More specifically, the individual steps of the two-pointers iterations are:

1. We place left pointer at the beginning of the sorted array (smallest value) and right pointer at the end of the sorted array (largest value). At each step, calculate the sum of the numbers at the left and right pointers
2. If the sum of the two numbers equals to target, we have found a pair; and we move the left pointer rightward by one step and the right pointer leftward by one step to find other possible pairs
3. If the sum of the two numbers is smaller than the target, we keep the right pointer unmoved and move the left pointer rightward by one step with the hope of using a larger value to match the targeted sum
4. Similarly, if the sum of the two numbers is larger than the target, we keep the left pointer unmoved and move the right pointer leftward by one step with the hope of using a smaller value to match the targeted sum
5. The pointer adjustments continue until the left and right pointers meet each other (i.e., when element[left] < element[right] is no longer satisfied). At this pointer we have completed one round of iteration in the remaining elements

Note that by using the two pointers to iterate the array in step 3, we reduce the time complexity to O(n) within each inner loop whereas brute force would require O(n²).

Operations for deduplication

Deduplication is crucial to this problem. And we need to handle it in both the outer and the inner loop.

• In the outer loop, the next repeating value must be skipped to avoid duplication because all doublets would have been located for any given target value once we have worked on a first occurrence. This translate to:

if i > 0 and nums[i] == nums[i - 1]:
    continue

• In the inner loop where we use two pointers, similar deduplication needs to be applied to both the left and right pointers:

# For the left pointer that moves rightward,
#.   its previous neighbour's index is `left - 1`
while left < right and nums[left] == nums[left - 1]:
    left += 1
# For the right pointer that moves leftward,
#.   its previous neighbour's index is `right + 1`
while left < right and nums[right] == nums[right + 1]:
    right -= 1

Implementation

Putting all these together, we get the following implementation:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # IMPORTANT! First, sort the input array inplace
        #   Time complexity of Timsort: O(nlogn)
        #   Space complexity of inplace sort: Neglected since temporary storage is used
        nums.sort()
        
        # Initialize results collector
        triplets = []
        
        # Assign array length to a variable for reuse
        array_len = len(nums)
        
        
        # Outer loop determins the target number for inner loop two pointers iteration
        for i in range(array_len):
            
            # Deduplication for outer loop:
            #   i > 0 to avoid index out-of-bound error
            #   nums[i] == nums[i - 1] indidates releating values and we should only
            #   only operates on first occurrence to avoid duplication
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            # Applies two pointers to inner loop
            
            # Initialize left and right pointers
            #   Start at beginning and end
            left, right = i + 1, array_len - 1

            while left < right:
                target = -nums[i]
                
                if nums[left] + nums[right] == target:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    
                    # Deduplication in inner loop
                    #   For the left pointer that moves rightwards, its previous element is `left - 1`
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    #   For the right pointer that moves leftwards, its previous element is `right + 1`
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                    
                    
                if nums[left] + nums[right] < target:
                    left += 1
                if nums[left] + nums[right] > target:
                    right -= 1
        
        return triplets

Space and time complexity

With n denotes the number of elements in input array:

• Space complexity: If storage required for the output collector is counted for, we need O(n/3) ~ O(n) space. Otherwise, we only need flat variables and thus the space complexity is O(1)
• Time complexity: With outer loop’s O(n) and inner loop two pointers’ O(n), we have a time complexity of O(n²). Sorting at the beginning takes O(nlogn) time. Collectivly, we have a time complexity of O(n²) + O(nlogn) = O(n²)

Example unit test with pytest

def test_three_sum():
    solution = Solution()
    assert solution.threeSum([]) == []
    assert solution.threeSum([1, 2, 3, 4]) == []
    assert solution.threeSum([0, 0, 0]) == [[0, 0, 0]]
    assert solution.threeSum([0, 0, 0, 0]) == [[0, 0, 0]]
    assert solution.threeSum([-1, 0, 1, 2, -1, -4]) == [
        [-1, -1, 2],
        [-1, 0, 1],
    ]