Three-Sum: Sorting and Two-Pointers

In our last lesson, we mastered the opposite-end two-pointer pattern for finding pairs in a sorted array. Now, we'll build directly on that foundation to tackle a more complex and classic interview problem: 3-Sum.

The challenge is to find all unique triplets in an unsorted array that sum to zero. This lesson will show you how to elegantly solve this by transforming the problem into a series of two-sum problems. You will learn to combine sorting with the two-pointer technique you've just practiced, paying special attention to the crucial step of handling duplicates—a key detail in coding interviews.

From Three Numbers to Two

The 3-Sum problem (as seen on LeetCode as problem 15) asks:

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that nums[i] + nums[j] + nums[k] == 0.

A brute-force solution would involve three nested loops to check every possible combination of three numbers. This would have a time complexity of O(n³), which is too slow for typical constraints.

The key insight is to reduce the problem's dimensionality. If we fix one number, a, in the triplet, the problem becomes finding two other numbers, b and c, such that b + c = -a. This is exactly the Two Sum problem we've been working on!

To make this efficient, our first step is to sort the input array. Sorting accomplishes two critical things:

1. It allows us to use the fast O(n) two-pointer technique for the b + c = -a subproblem.
2. It groups duplicate numbers together, which makes them much easier to identify and skip.

The overall strategy is:

1. Sort the array nums.
2. Iterate through the sorted array with an index i, picking nums[i] as our first element, a.
3. For each nums[i], run the opposite-end two-pointer algorithm on the remainder of the array (from i+1 to the end) to find a pair (b, c) that sums to -nums[i].

This approach reduces the complexity from a brute-force O(n³) down to O(n²), which is a significant improvement. The following image provides a high-level comparison of the brute-force, a binary search variant, and our target two-pointer approach, clearly showing the gains in efficiency.

The Optimal Two-Pointer Algorithm in Action

Let's dive into the mechanics of the optimal solution. The "take U forward" channel provides one of the clearest and most intuitive walkthroughs of this algorithm. The video first covers the brute-force and hash-based methods, but we will focus on the optimal approach that directly builds on our previous lesson.

As you saw in the video, handling duplicates is the most intricate part of this problem. Let's formalize the logic for skipping them:

• Skipping duplicate i: The outer loop iterates through nums to pick the first element of the triplet. If we encounter a number that is the same as the one before it (e.g., nums[i] == nums[i-1]), we must skip it. Why? Because we would have already generated all unique triplets starting with that value in the previous iteration.
• Skipping duplicates for j and k: After finding a valid triplet (nums[i], nums[j], nums[k]), we add it to our results. We then need to move both pointers (j++ and k--) to continue searching for other potential triplets. However, before resuming the search, we must advance the j and k pointers past any duplicates of their current values. For example, if we just used nums[j] and the next element nums[j+1] is identical, we must skip it to avoid generating a duplicate triplet.

Step-by-Step Implementation Guide

The AlgoMonster article provides a fantastic, systematic breakdown of the implementation logic. It cleanly separates the algorithm into distinct, understandable steps, reinforcing the concepts from the video.

From Algorithm to Code

Now that you have a firm grasp of the logic, let's look at a complete implementation. The following resource provides well-commented code in multiple languages, along with detailed notes on complexity and common pitfalls.

The time complexity is dominated by the nested loop structure, resulting in O(n²), plus the initial O(n log n) for sorting. The space complexity is O(1) (ignoring the space for the output list), as we only use a few variables for pointers. This is highly efficient compared to alternatives that might require O(n) space for hash sets.

Conclusion

In this lesson, you've leveled up from the Two Sum pattern to the more advanced 3-Sum. You learned how to combine sorting with the opposite-end two-pointer technique to solve a problem that initially seems to require three nested loops.

Key Takeaways:

• Reduction: The 3-Sum problem a + b + c = 0 can be reduced to a series of Two Sum problems b + c = -a by fixing a.
• Sorting is Key: Sorting the array is the essential first step that enables both the efficient two-pointer scan and a straightforward strategy for handling duplicates.
• The Pattern: The complete pattern is Sort -> Outer Loop (for i) -> Two-Pointer Subproblem (for left and right).
• Duplicate Handling: The most critical detail for a correct solution is to systematically skip duplicate values for the outer loop index (i) and for the two inner pointers (left, right) after finding a valid triplet.

In our next lesson, we'll continue exploring the two-pointer technique but in a different context: the "Container with Most Water" problem. This will demonstrate the versatility of the pattern beyond simple sum-finding tasks.