The Three Sum problem asks us to find all unique triplets in an array that sum to zero. Since checking all combinations would be too slow for large arrays, we use a more efficient approach by combining sorting with the two-pointer technique.
Understanding the Problem
We are looking for three numbers (a, b, c) such that a + b + c = 0
. Importantly, we must not return duplicate triplets. This means if two triplets contain the same numbers in the same order, we should only return one of them.
How We Solve It
First, we sort the input array. This helps us identify and skip duplicates easily and apply the two-pointer strategy efficiently.
We fix one number at a time using a loop (let's call it i
) and then look for the other two numbers using two pointers: left
starting from i + 1
and right
starting from the end of the array.
Depending on the total sum of arr[i] + arr[left] + arr[right]
, we have three scenarios:
- If the sum is 0: It's a valid triplet. We add it to the result and skip any duplicate values to avoid repeating the same triplet.
- If the sum is less than 0: It means the numbers are too small. We move the
left
pointer to the right to increase the sum.
- If the sum is greater than 0: It means the numbers are too large. We move the
right
pointer to the left to reduce the sum.
Handling Edge Cases
- If the array has less than three elements, it's impossible to form a triplet—return an empty list.
- If all elements are zero and there are at least three of them, then
[0, 0, 0]
is the only valid triplet.
- If the array is empty, simply return an empty list.
- We must be careful not to include duplicate triplets, which is why we skip over elements that are the same as the previous one (for
i
, left
, and right
).
This optimal method ensures that the time complexity is O(n²) instead of the brute force O(n³), making it suitable for large inputs.