3Sum
Return every distinct triplet whose values sum to zero without duplicating answers.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
Given an integer array, return all distinct triplets whose sum is zero.
The difficulty is not only finding triplets fast enough. You also need to avoid duplicate answers when the input contains repeated values.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a sorting + two pointers problem.
In interviews, recognize it when:
you need unique pairs or triplets
the order of the array does not matter
sorting lets you reason about sums moving left or right
duplicate handling is part of the difficulty
Key Idea
The main invariant or observation that makes the clean solution work.
Sort the array first. Then fix one index \(i\) and solve a two-sum problem on the suffix \([i + 1, n - 1]\) with two pointers.
Because the array is sorted:
if the current sum is too small, move the left pointer right
if the current sum is too large, move the right pointer left
after finding a valid triplet, skip duplicates on both sides
Sorting turns duplicate control from a bookkeeping mess into a local pointer rule.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The direct brute-force solution tries every triple, which costs \(O(n^3)\).
A better but still clumsy idea is to fix one number and use a hash set for the remaining two-sum search. That reduces the time to \(O(n^2)\), but keeping the output unique becomes awkward.
Sorting improves both issues at once. Once the numbers are ordered, moving a pointer has a predictable effect on the sum, and duplicate values sit next to each other, so they are easy to skip.
That is the key transition: instead of treating uniqueness as a separate cleanup pass, build it into the scan itself.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n^2)\) overall
Space: \(O(1)\) auxiliary, ignoring the output and the sort implementation details
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <algorithm>
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> triplets;
for (int index = 0; index < static_cast<int>(nums.size()); ++index) {
if (nums[index] > 0) {
break;
}
if (index > 0 && nums[index] == nums[index - 1]) {
continue;
}
int left = index + 1;
int right = static_cast<int>(nums.size()) - 1;
while (left < right) {
const int sum = nums[index] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
triplets.push_back({nums[index], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
}
}
}
return triplets;
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Forgetting to skip duplicate anchors creates repeated triplets.
After finding one triplet, failing to skip duplicate left or right values also creates repeats.
Using the two-pointer pattern on an unsorted array does not work.
Missing the early stop when the anchor becomes positive wastes time, because three positive numbers cannot sum to zero in a sorted array.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This pattern generalizes directly to 3Sum Closest, 4Sum, and the broader \(k\)-sum family.
The main reusable lesson is that sorting is often worth it when uniqueness and pointer movement need to be handled at the same time.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.