3Sum

Difficulty: Medium | Acceptance: 37.56% | Paid: No

Topics: Array, Two Pointers, Sorting

• Examples
• Constraints
• Brute Force with Sorting and Skipping Duplicates
• Hash Map for Two-Sum Lookup
• Optimized Two-Pointer Technique

Examples

Input

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

Output

[[-1,-1,2],[-1,0,1]]

Explanation

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.

Input

nums = [0,1,1]

Output

[]

Explanation

The only possible triplet does not sum up to 0.

Input

nums = [0,0,0]

Output

[[0,0,0]]

Explanation

The only possible triplet sums up to 0.

Constraints

- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5

Brute Force with Sorting and Skipping Duplicates

Intuition

A straightforward approach is to examine all combinations of triplets using three nested loops. We can sort the array upfront to make checking for duplicates easier and to simplify the skipping logic.

Steps

• Sort the input array to bring like elements together and allow efficient duplicate skipping.
• Use three nested loops: i to fix the first element, j for the second, and k for the third.
• For each triplet, check if nums[i] + nums[j] + nums[k] equals zero.
• If the sum is zero, add the triplet to our result list.
• Crucially, before moving an index to its next value, skip over any duplicate elements to avoid adding duplicate triplets to the result.
• A duplicate for i is nums[i] == nums[i-1] (after i > 0). For j and k, the check is similar but depends on their valid iteration space.

def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k-1]:
                    continue
                if nums[i] + nums[j] + nums[k] == 0:
                    res.append([nums[i], nums[j], nums[k]])
    return res

Complexity

• Time: O(N^3), where N is the length of the array. The three nested loops dominate the runtime.
• Space: O(1) if we don’t count the space required for the output. For sorting in-place algorithms like heapsort, the auxiliary space is constant. However, sorting typically requires O(log N) space implicitly.
• Notes: This approach is correct but inefficient for larger inputs due to its cubic time complexity. It’s sufficient to pass basic tests but will be too slow for arrays with lengths close to the constraint’s upper limit of 3000.

Hash Map for Two-Sum Lookup

Intuition

We can fix one number a and then reframe the problem as a classic Two-Sum: find two numbers b and c such that b + c = -a. A hash map can efficiently find such pairs in a single pass.

Steps

• Iterate through the array with an index i to fix the first number a = nums[i].
• For the subarray nums[i+1..n-1], solve the Two-Sum problem for a target of -a.
• Create a hash map to store the value-to-index mappings of elements in the subarray.
• Iterate through the subarray again. For each element b = nums[j], calculate c = -a - b.
• Check if c exists in the hash map (and has an index different from j). If so, we have found a valid triplet (a, b, c).
• To handle duplicates, store found triplets in a set of sorted tuples. A set automatically handles uniqueness.
• Convert the final set of sorted tuples to a list of lists.

def threeSum(nums):
    nums.sort()
    res = set()
    n = len(nums)
    for i in range(n - 2):
        a = nums[i]
        seen = {}
        for j in range(i + 1, n):
            b = nums[j]
            c = -a - b
            if c in seen:
                triplet = (a, b, c)
                res.add(triplet)
            seen[b] = j
    return [list(triplet) for triplet in res]

Complexity

• Time: O(N^2), where N is the length of the array. The outer loop runs O(N) times, and the inner loop runs O(N) times for each outer loop iteration.
• Space: O(N) for the hash map seen and the set resSet. The hash map stores up to O(N) elements.
• Notes: This is a significant improvement over brute force. It leverages the efficiency of hash map lookups. The set helps in managing duplicates, although the initial sort is still beneficial for deterministic output format and can help with duplicate skipping in a 2-pointer version.

Optimized Two-Pointer Technique

Intuition

After sorting the array, we can use a two-pointer technique to find pairs that sum up to a specific target, reducing the inner loop’s complexity. For 3Sum, fix the first element and use two pointers for the rest.

Steps

• Sort the array. This allows for a deterministic two-pointer search and easy duplicate skipping.
• Iterate through the array with index i to fix the first number of the triplet, nums[i].
• To avoid duplicate triplets, skip i if nums[i] == nums[i-1] (after i > 0).
• For the remaining subarray nums[i+1..n-1], use two pointers: left starting at i+1 and right starting at n-1.
• Calculate the sum sum = nums[i] + nums[left] + nums[right].
• If sum < 0, we need a larger number; increment left.
• If sum > 0, we need a smaller number; decrement right.
• If sum == 0, we have found a valid triplet. Add it to the result. Then, to skip duplicates for left and right, increment left and decrement right as long as they point to the same values.
• Continue the two-pointer search until left < right.

def threeSum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                res.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 res

Complexity

• Time: O(N^2), where N is the length of the array. Sorting takes O(N log N). The outer loop runs O(N) times. For each outer loop iteration, the two-pointer search takes O(N) time, leading to O(N * N) for the nested loops.
• Space: O(1) if we don’t count the space for the output. The sorting can be done in-place, and the two-pointer technique uses only a constant amount of extra space.
• Notes: This is the standard optimal solution for the 3Sum problem. It’s efficient and correct, leveraging the sorted order for early loop exits and structured search. The duplicate skipping logic is crucial for correctness.