Mastering the 3Sum Algorithm: Two-Pointer Solution & Code

Stuck on LeetCode 15? You're not alone. The 3Sum problem is a rite of passage for every developer preparing for technical interviews. I've seen candidates—often sharp engineers with solid systems design experience—stumble here. The gap isn't lack of coding ability; it's the subtle trap of duplicate handling and the shift from "finding an answer" to "enumerating unique answers efficiently."

The 3sum algorithm is deceptively simple on the surface. "Find triplets that add up to zero" sounds like a three-loop brute force job. But do that in an interview, and you'll likely hit Time Limit Exceeded (TLE) before you finish explaining your logic. The real test lies in optimizing that brute force approach down to $O(n^2)$ using the two pointers technique, all while rigorously deduplicating results. This guide will walk you through exactly how to bridge that gap.

---

What is the 3Sum Problem? Understanding the Core Challenge

At its heart, the 3Sum problem asks you to find all unique triplets $[nums[i], nums[j], nums[k]]$ in an integer array such that $i \neq j$, $i \neq k$, $j \neq k$, and $nums[i] + nums[j] + nums[k] == 0$.

Let's look at a concrete example. If the input is nums = [-1, 0, 1, 2, -1, -4], the sorted version becomes [-4, -1, -1, 0, 1, 2]. The valid unique triplets are [[-1, -1, 2], [-1, 0, 1]]. Notice that even though -1 appears twice in the input, we only output the triplet [-1, -1, 2] once. The constraint "unique triplets" is what transforms this from a trivial search into a nuanced algorithmic challenge.

Why is 3Sum Considered Medium Difficulty?

In the hierarchy of 3sum leetcode problems, 3Sum sits squarely in the "Medium" bucket. Why? Because it requires composing two well-known concepts: sorting and the two-pointer pattern. It’s not about inventing a new data structure; it’s about recognizing when to apply them together.

The difficulty spikes when you consider edge cases. An array with all identical elements (e.g., [0, 0, 0]) requires strict deduplication. An array with no valid triplets (e.g., [1, 2, 3]) must return an empty list. The most common pitfall I see isn't getting the sum wrong—it's returning duplicate triplets like [[-1, 0, 1], [-1, 0, 1]] because the deduplication logic was skimpy.

Compared to 2Sum (Easy), which can be solved with a hash map in $O(n)$, 3Sum adds a dimension. Compared to 4Sum (Hard/Medium depending on platform), 3Sum is the foundational pattern. Mastering 3Sum gives you the template to solve any $K$-Sum problem.

---

Brute Force vs. Optimal Approach: Time Complexity Breakdown

To appreciate the optimal solution, we first need to understand why the naive approach fails. This contrast is crucial for coding interview prep because interviewers often ask you to start with the brute force method before refining it.

The Brute Force Method (O(n³))

The most obvious way to solve this is to check every possible combination of three numbers. We can use three nested loops:

1. The outer loop fixes the first element at index i.
2. The middle loop fixes the second element at index j (where j > i).
3. The inner loop checks the third element at index k (where k > j).

If the sum equals zero, we store the triplet. In a set, to handle uniqueness automatically.

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if nums[i] + nums[j] + nums[k] == 0:
                add to results

While this is correct in terms of logic, the time complexity is $O(n^3)$. For an array of size 1,000, that's roughly one billion operations. In modern coding platforms, this will almost certainly result in a Time Limit Exceeded error. The space complexity is also higher if we use a Set to store results to avoid duplicates.

The Optimal Two-Pointer Solution (O(n²))

The breakthrough comes from reducing the problem. If we fix one number, say nums[i], the problem becomes: "Find two numbers in the remaining array that sum to -nums[i]." This is exactly the 2Sum problem.

However, instead of using a hash map (which costs $O(n)$ space), we can use the two pointers technique if we sort the array first. Sorting takes $O(n \log n)$, and then for each fixed element, we scan the rest of the array with two pointers in $O(n)$ time. This brings the total time complexity down to $O(n^2)$.

---

How to Solve 3Sum in Python, Java, and C++: Code Deep Dive

Let's look at how the 3sum solution python implementation differs from Java and C++. The logic is identical, but syntax and standard library choices vary.

Python Implementation

Python is often the preferred language for interviews due to its readability. The sort() method is highly optimized (Timsort).

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()  # Sorts in-place, O(n log n)
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Early exit: if the smallest number is positive, sum can't be 0
        if nums[i] > 0:
            break
            
        # Skip duplicate first elements
        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:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for left and right pointers
                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 result

Python's dynamic typing hides some boilerplate, but the core algorithm remains transparent. Note the use of while loops to skip duplicates immediately after finding a match.

Java and C++ Implementations

In Java, we use ArrayList and Arrays.sort(). In C++, we use vector and std::sort(). The logic for pointer movement and deduplication is unchanged.

Java:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break; // Optimization
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int right = n - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

C++:

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1;
        int right = n - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

A key difference in C++ is pass-by-reference (vector<int>& nums) which avoids copying the large input array, preserving the $O(1)$ extra space claim (excluding output). In Java, arrays are objects passed by reference, so Arrays.sort() modifies the original array.

---

Handling Duplicates: The Key to Passing All Test Cases

If there is one thing that separates a working solution from a correct solution in 3Sum, it is duplicate handling. I've reviewed countless code samples where the logic is sound, but the output contains redundant triplets. Let's dissect why this happens and how to prevent it.

Why Duplicates Matter in 3Sum

The problem statement explicitly forbids duplicate triplets in the output. Consider the array [-1, -1, 0, 1]. After sorting, we have [-1, -1, 0, 1].

If we don't handle duplicates:

1. Fix i=0 (-1). Two pointers find [-1, 0, 1].
2. Fix i=1 (-1). Two pointers also find [-1, 0, 1].

You've now returned the same triplet twice. To the interviewer, this is a logical error. The sorting step groups identical values together, which gives us the opportunity to skip them.

Strategies for Deduplication

There are three layers of deduplication we must implement:

1. First Element (i): Before processing nums[i], check if it's the same as nums[i-1]. If so, skip. This ensures we don't start the same triplet search twice.

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

2. Left Pointer (left): After finding a valid triplet, increment left past any identical values.

   while left < right and nums[left] == nums[left + 1]:
       left += 1
   

3. Right Pointer (right): Similarly, decrement right past any identical values.

   while left < right and nums[right] == nums[right - 1]:
       right -= 1
   

Alternative Approach: Hash Set Deduplication You might be tempted to use a HashSet to store results and let the set handle duplicates. While this works, it increases space complexity to $O(n^2)$ in the worst case (when many triplets exist) and adds overhead for hashing. The sorting-based skip strategy is generally preferred in interviews because it maintains $O(1)$ auxiliary space and leverages the sorted property directly.

---

3Sum Variants: 4Sum vs. 3Sum Closest Explained

Once you've mastered the 3sum algorithm, the natural next step is to explore its variants. These problems test whether you truly understand the pattern or just memorized the code for LeetCode 15.

Extending to 4Sum

4Sum (LeetCode 18) asks for unique quadruplets that sum to a target. The logic extends seamlessly. You add another outer loop to fix two elements, and then use the two-pointer technique for the remaining two.

Solving 3Sum Closest

3Sum Closest (LeetCode 16) changes the goal. Instead of finding a sum exactly equal to zero, we want the sum closest to a given target.

The algorithm structure is nearly identical:

1. Sort the array.
2. Iterate with i, set left and right.
3. Calculate current_sum.
4. Track the diff = abs(current_sum - target). Keep updating the best answer if diff is smaller.
5. Move pointers based on whether current_sum is less than or greater than target.

This variant is often asked as a follow-up because it demonstrates you can adapt the core logic to a slightly different objective without reinventing the wheel.

---

Common Interview Questions and How to Answer Them

During my years of conducting technical interviews, certain questions about 3Sum come up repeatedly. Here’s how to tackle them with confidence.

Can 3Sum be Solved in O(n) Time?

No, not for a general unsorted array. The lower bound for comparison-based approaches to this problem is $\Omega(n^2)$. While 2Sum can be solved in $O(n)$ using a hash map, 3Sum requires finding pairs for each element, which inherently leads to quadratic complexity. If an interviewer asks this, they are testing your understanding of computational complexity bounds.

What If the Array is Already Sorted?

If the input is guaranteed to be sorted, you can skip the initial sorting step. This saves the $O(n \log n)$ overhead, making the constant factor smaller. However, the time complexity remains $O(n^2)$ because the two-pointer sweep still dominates. In an interview, pointing out this optimization shows attention to detail.

How Does 3Sum Relate to 2Sum?

This is a great chance to show conceptual mapping. 3Sum is essentially "solve 2Sum for every element in the array." By fixing one number, you reduce the dimensionality of the problem from 3D to 2D. This reduction strategy is a powerful pattern in algorithm design. You can generalize this: N-Sum can be reduced to (N-1)-Sum recursively.

---

FAQ

What is the time complexity of the 3Sum algorithm?

The time complexity is $O(n^2)$. This comes from sorting the array ($O(n \log n)$) plus the nested loop structure where the outer loop runs $n$ times and the inner two-pointer scan runs $n$ times in the worst case. The $O(n^2)$ term dominates. The space complexity is $O(1)$ or $O(\log n)$ depending on the sorting implementation, excluding the output storage.

How do you handle duplicates in 3Sum?

Duplicates are handled by sorting the array first and then skipping identical consecutive elements. For the fixed element i, skip if nums[i] == nums[i-1]. After finding a valid triplet, advance the left pointer past duplicates and retreat the right pointer past duplicates. This ensures each unique triplet is added to the result only once.

What is the difference between 3Sum and 4Sum?

3Sum finds triplets (three numbers) that sum to zero, with a time complexity of $O(n^2)$. 4Sum finds quadruplets (four numbers) that sum to a target, requiring two fixed elements and resulting in $O(n^3)$ time complexity. The core two-pointer logic for the inner search is the same.

Can 3Sum be solved without sorting?

Yes, you can use a Hash Set approach. For each pair, check if the complement exists in a hash set. However, this requires $O(n^2)$ space to store the pairs or results, and deduplication becomes more complex (requiring canonical representation of triplets). The sorting + two-pointer method is generally preferred for interviews due to its $O(1)$ extra space efficiency.

---

Conclusion

The 3sum algorithm is more than just a LeetCode problem; it's a master