#15

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

3Sum

Given an integer array, return all unique triplets where the sum is zero using two-pointer scanning with careful duplicate handling.

array two pointers sorting

Problem Statement

Given an integer array nums, return all distinct triplets [nums[i], nums[j], nums[k]] where i, j, and k are different indices and the sum equals zero. The order of triplets or elements inside triplets does not matter, but duplicates must be avoided. You must find all possible unique combinations efficiently while handling arrays with up to 3000 elements and values ranging from -10^5 to 10^5.

For example, given nums = [-1,0,1,2,-1,-4], the valid triplets are [-1,0,1] and [-1,-1,2]. Arrays with fewer than three elements or no combination summing to zero return an empty list. The problem tests array manipulation, sorting, and two-pointer scanning with invariant tracking to handle sums and skip repeated values effectively.

Examples

Example 1

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

Output: [[-1,-1,2],[-1,0,1]]

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.

Example 2

Input: nums = [0,1,1]

Output: []

The only possible triplet does not sum up to 0.

Example 3

Input: nums = [0,0,0]

Output: [[0,0,0]]

The only possible triplet sums up to 0.

Constraints

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Solution Approach

Sort and Fix One Element

Begin by sorting the array to enable two-pointer scanning. Iterate through each number as a fixed first element, skipping duplicates to maintain unique triplets. Sorting ensures that pointers can move deterministically: left pointer increases and right pointer decreases to reach the target sum, allowing the algorithm to systematically cover all combinations without missing or repeating triplets.

Two-Pointer Scan for Remaining Pair

After fixing the first element, initialize two pointers: one immediately after the fixed element and one at the end of the array. Calculate the sum of the three elements. If the sum is zero, record the triplet and skip any duplicates by advancing the left pointer and decreasing the right pointer. If the sum is less than zero, move the left pointer to increase the sum; if greater than zero, move the right pointer to decrease it. This preserves the invariant that all pairs are checked once.

Handle Duplicates and Collect Results

After each valid triplet is found, continue scanning while skipping over identical elements on both ends to prevent duplicate triplets in the result. Repeat this process for all positions of the fixed element. This approach ensures that each distinct combination is captured exactly once, leveraging the sorted array property and two-pointer invariant tracking. Edge cases, like multiple zeros or repeated negative numbers, are managed naturally by the duplicate skipping logic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n), and each fixed element triggers a two-pointer scan of O(n), giving an overall time complexity of O(n^2). The space complexity is O(1) excluding the output array, as only a few pointers and temporary storage for triplets are used. This analysis aligns with the provided complexities and highlights that extra memory is minimal beyond storing results.

What Interviewers Usually Probe

Do you see how sorting simplifies duplicate management in two-pointer scanning?
Can you explain why moving both pointers inward maintains the sum invariant?
Will you handle cases with multiple zeros or repeated numbers correctly?

Common Pitfalls or Variants

Common pitfalls

Failing to skip duplicate fixed elements leads to repeated triplets in output.
Not advancing pointers past duplicate values after finding a triplet can cause repeated results.
Assuming unsorted arrays allow direct two-pointer scans without first sorting, breaking the invariant logic.

Follow-up variants

Find all triplets that sum to a specific target value instead of zero, still avoiding duplicates.
Return the count of unique triplets instead of the actual triplet arrays, focusing on optimization.
Extend to 4Sum by fixing two elements and using two-pointer scanning for the remaining pair, managing duplicates carefully.

FAQ

What pattern does 3Sum primarily use?

3Sum leverages two-pointer scanning with invariant tracking after sorting the array, allowing systematic sum checks and duplicate management.

How do I avoid duplicate triplets in 3Sum?

Skip duplicate elements when fixing the first number and after finding valid triplets, move left and right pointers past identical values to maintain uniqueness.

Can 3Sum handle arrays with multiple zeros?

Yes, the algorithm naturally handles multiple zeros by skipping duplicates while scanning, ensuring only unique triplets like [0,0,0] are included once.

Why is sorting necessary in 3Sum?

Sorting ensures that the two-pointer scan works correctly, enabling deterministic pointer movements and simplifying duplicate detection to prevent repeated triplets.

What is the time and space complexity of 3Sum?

The overall time complexity is O(n^2) due to nested loops with two-pointer scanning, and space complexity is O(1) excluding the output list storing the triplets.

terminal

Solution

Solution 1: Sort + Two Pointers

We notice that the problem does not require us to return the triplet in order, so we might as well sort the array first, which makes it easy to skip duplicate elements.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x < 0:
                    j += 1
                elif x > 0:
                    k -= 1
                else:
                    ans.append([nums[i], nums[j], nums[k]])
                    j, k = j + 1, k - 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
        return ans

Continue Practicing

#16 3sum closest #18 4sum #75 sort colors