Introduction to the 3Sum Problem
The 3Sum problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. Given an array of integers, the task is to find all unique triplets in the array that sum up to zero. While the problem statement sounds simple, solving it efficiently requires a solid understanding of sorting, two-pointer techniques, and careful handling of duplicates.
In this tutorial, we will walk through the 3Sum problem from first principles, implement a clean and efficient solution in Go, and discuss best practices that will help you write production-ready code. By the end, you will not only be able to solve 3Sum confidently but also apply the same patterns to a family of related problems such as 4Sum, 3Sum Closest, and Triangle Triplets.
What Is the 3Sum Problem?
Formally, the 3Sum problem is defined as follows: given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.
For example, given the input [-1, 0, 1, 2, -1, -4], the expected output is [[-1, -1, 2], [-1, 0, 1]]. Notice that although -1 appears twice in the input, the triplet [-1, 0, 1] is only listed once. This uniqueness constraint is what trips up many developers on their first attempt.
Why It Matters
The 3Sum problem matters for several reasons. First, it is a staple of technical interviews at major technology companies because it tests multiple skills at once: array manipulation, algorithmic optimization, and edge-case handling. Second, the techniques used to solve it — particularly the two-pointer approach — generalize to many other problems. Third, in real-world applications, similar problems arise in computational geometry, financial analysis, and data mining whenever you need to find combinations that satisfy a constraint.
Understanding how to reduce a brute-force O(n^3) solution down to O(n^2) is a valuable lesson in algorithmic thinking. It demonstrates how sorting can unlock dramatic performance improvements by enabling smarter traversal strategies.
Approaches to Solving 3Sum
Before jumping into code, let us examine the main approaches to solving this problem and their trade-offs.
Brute Force
The naive approach uses three nested loops to consider every possible triplet. This runs in O(n^3) time and is impractical for arrays larger than a few hundred elements. It also requires extra logic to deduplicate triplets, typically by storing them in a set keyed by a sorted representation.
Hash Set Approach
A slightly better approach fixes one element and then uses a hash set to find pairs that sum to the negation of that element. This reduces the time complexity to O(n^2) but still requires careful deduplication and uses O(n) extra space for the hash set. While acceptable, it is not the most elegant solution.
Two-Pointer Approach
The optimal and most idiomatic solution sorts the array first and then uses the two-pointer technique. Sorting takes O(n log n), and the two-pointer scan for each fixed element takes O(n), giving an overall time complexity of O(n^2). The space complexity is O(1) aside from the output, and deduplication becomes trivial because equal elements are adjacent in a sorted array. This is the approach we will implement.
Step-by-Step Implementation in Go
Let us now build the solution incrementally. We will start with the overall structure, then fill in the core logic, and finally add the deduplication safeguards.
Step 1: Function Signature and Sorting
The function accepts a slice of integers and returns a slice of integer slices. The first step is to sort the input so that we can use the two-pointer technique and easily skip duplicates.
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
result := [][]int{}
n := len(nums)
if n < 3 {
return result
}
sort.Ints(nums)
// Core logic goes here
return result
}
Notice that we handle the edge case where the array has fewer than three elements immediately. Returning early for invalid input is a best practice that keeps the main logic clean.
Step 2: Fixing the First Element
We iterate through the array, treating each element as the first element of a potential triplet. For each fixed element nums[i], we need to find two other elements that sum to -nums[i].
for i := 0; i < n-2; i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
// Two-pointer search goes here
}
There are two important optimizations here. First, if nums[i] is greater than zero, we can break out of the loop entirely because the array is sorted and no three positive numbers can sum to zero. Second, if the current element is the same as the previous one, we skip it to avoid duplicate triplets.
Step 3: Two-Pointer Search
For each fixed nums[i], we initialize two pointers: left just after i, and right at the end of the array. We then move the pointers inward based on the sum of the three elements.
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
When the sum equals zero, we record the triplet and then skip over any duplicate values on both sides before moving the pointers. When the sum is less than zero, we need a larger value, so we move left to the right. When the sum is greater than zero, we need a smaller value, so we move right to the left.
Complete Solution
Putting it all together, here is the complete, runnable Go program:
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
result := [][]int{}
n := len(nums)
if n < 3 {
return result
}
sort.Ints(nums)
for i := 0; i < n-2; i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return result
}
func main() {
testCases := [][]int{
{-1, 0, 1, 2, -1, -4},
{},
{0},
{0, 0, 0, 0},
{-2, 0, 1, 1, 2},
}
for _, tc := range testCases {
fmt.Printf("Input: %v\nOutput: %v\n\n", tc, threeSum(tc))
}
}
When you run this program, you should see output like the following:
Input: [-1 0 1 2 -1 -4]
Output: [[-1 -1 2] [-1 0 1]]
Input: []
Output: []
Input: [0]
Output: []
Input: [0 0 0 0]
Output: [[0 0 0]]
Input: [-2 0 1 1 2]
Output: [[-2 0 2] [-2 1 1]]
How to Use This Solution
The solution above is self-contained and can be dropped directly into any Go project. To use it, simply call the threeSum function with your integer slice. The function returns a slice of triplets, each represented as a slice of three integers.
If you are working within a larger application, consider wrapping this logic in a package. For example, you might create a package called triplets with an exported FindZeroSum function. This keeps your code organized and makes it easier to write unit tests.
package triplets
import "sort"
func FindZeroSum(nums []int) [][]int {
result := [][]int{}
n := len(nums)
if n < 3 {
return result
}
sort.Ints(nums)
for i := 0; i < n-2; i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return result
}
Writing Tests
Testing is essential for algorithmic code. Here is an example test file using Go's standard testing package:
package triplets
import (
"reflect"
"testing"
)
func TestFindZeroSum(t *testing.T) {
tests := []struct {
name string
input []int
want [][]int
}{
{"standard case", []int{-1, 0, 1, 2, -1, -4}, [][]int{{-1, -1, 2}, {-1, 0, 1}}},
{"empty input", []int{}, [][]int{}},
{"single element", []int{0}, [][]int{}},
{"all zeros", []int{0, 0, 0, 0}, [][]int{{0, 0, 0}}},
{"no triplets", []int{1, 2, 3}, [][]int{}},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := FindZeroSum(tt.input)
if !reflect.DeepEqual(got, tt.want) {
t.Errorf("got %v, want %v", got, tt.want)
}
})
}
}
Best Practices
Now that you have a working solution, let us review some best practices that will make your code more robust and maintainable.
- Always handle edge cases first. Check for arrays with fewer than three elements, empty arrays, and nil inputs. Returning early keeps your main logic focused on the happy path.
- Sort before searching. Sorting is a one-time
O(n log n)cost that enables theO(n^2)two-pointer scan and makes deduplication trivial. This is almost always worth it. - Skip duplicates at every level. Duplicate triplets can arise from repeated values at the fixed element, the left pointer, or the right pointer. Make sure to skip duplicates in all three positions.
- Use early termination. If the smallest element in a sorted array is greater than zero, no triplet can sum to zero. Breaking early saves unnecessary work.
- Avoid mutating the input. If the caller expects the input slice to remain unchanged, make a copy before sorting. This is especially important in library code.
- Write table-driven tests. Go's testing framework makes table-driven tests natural. Cover standard cases, edge cases, and cases with many duplicates.
- Profile before optimizing further. The two-pointer solution is already optimal in terms of asymptotic complexity. Micro-optimizations like avoiding slice allocations are rarely worth the added complexity unless profiling shows a real bottleneck.
Common Pitfalls
Even experienced developers make mistakes with 3Sum. Here are a few pitfalls to watch out for:
- Forgetting to skip duplicates after finding a valid triplet. If you find a triplet and move the pointers without skipping duplicates, you will record the same triplet multiple times.
- Using
left <= rightinstead ofleft < right. The two pointers must point to distinct elements, so the loop condition must be strictly less than. - Not checking
i > 0before comparingnums[i]andnums[i-1]. Without this guard, you will access index-1on the first iteration, causing a panic or undefined behavior. - Mutating the input slice.
sort.Intssorts in place. If the caller needs the original order, your function will silently break their code.
Extending to Variants
The two-pointer pattern you learned here generalizes to many related problems. For example, the 3Sum Closest problem asks for the triplet whose sum is closest to a target value. You can adapt the solution by tracking the closest sum instead of collecting triplets. The 4Sum problem extends the idea by adding another outer loop. Once you internalize the two-pointer technique, these variants become straightforward modifications rather than entirely new problems.
Here is a quick sketch of how you might adapt the code for a generalized kSum problem:
func kSum(nums []int, target int, k int) [][]int {
sort.Ints(nums)
return kSumHelper(nums, target, k, 0)
}
func kSumHelper(nums []int, target int, k int, start int) [][]int {
result := [][]int{}
n := len(nums)
if k == 2 {
left, right := start, n-1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
result = append(result, []int{nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < target {
left++
} else {
right--
}
}
return result
}
for i := start; i < n-k+1; i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
subResults := kSumHelper(nums, target-nums[i], k-1, i+1)
for _, r := range subResults {
result = append(result, append([]int{nums[i]}, r...))
}
}
return result
}
This recursive approach reduces kSum to 2Sum as the base case and is a powerful demonstration of how algorithmic patterns compose.
Conclusion
The 3Sum problem is a perfect vehicle for learning the two-pointer technique, one of the most versatile tools in an algorithm developer's toolkit. By sorting the array and carefully managing pointers and duplicates, you can solve the problem in O(n^2) time with minimal extra space. The Go implementation we built is clean, efficient, and easy to test. More importantly, the patterns you practiced here — sorting to enable smarter traversal, skipping duplicates to ensure uniqueness, and reducing a problem to a simpler base case — will serve you well across a wide range of algorithmic challenges. Take the time to implement the solution yourself, write tests for edge cases, and experiment with the variants. With practice, solving 3Sum and its relatives will become second nature.