3Sum LeetCode Solution: Complete Problem Walkthrough

If you have solved Two Sum, 3Sum (#15) is the natural next step — and a significant jump in difficulty. It is one of the most frequently asked Medium problems on LeetCode, showing up in interviews at virtually every top tech company.

The problem asks you to find all unique triplets in an array that sum to zero. Sounds simple, but the duplicate-handling requirement is where most candidates stumble. Getting the logic right under interview pressure separates prepared candidates from everyone else.

This walkthrough covers the optimal sort + two pointers approach that interviewers expect. You will understand not just the how, but the why behind every step — from sorting the array to skipping duplicate values at each pointer.

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 nums = [-1, 0, 1, 2, -1, -4], the answer is [[-1, -1, 2], [-1, 0, 1]]. Notice that [-1, 0, 1] appears only once even though there are two -1 values in the input. This uniqueness constraint is the core challenge.

The problem is essentially asking: for every element in the array, can you find a pair among the remaining elements that sums to the negative of that element? That reframing connects 3Sum directly to the Two Sum pattern you already know.

The naive approach is three nested loops: try every combination of three indices and check if they sum to zero. This runs in O(n^3) time, which is far too slow for n = 3000 (that is 27 billion operations).

Even if you could tolerate the time complexity, you still need to handle duplicates. Using a HashSet of sorted triplets adds memory overhead and complicates the logic. Interviewers will not be impressed by this approach.

Some candidates try an O(n^2) approach using a hash map for the third element — similar to Two Sum. This works but makes duplicate handling messy and error-prone. The sort + two pointers method is cleaner, faster in practice, and what interviewers expect to see.

The key insight is that sorting the array unlocks the two-pointer technique. Once the array is sorted, you fix one element and use two pointers to find the remaining pair — exactly like Two Sum II (sorted input).

Here is the algorithm step by step. First, sort the array in ascending order. Then iterate through the array with index i. For each nums[i], set a left pointer at i + 1 and a right pointer at the end of the array. Calculate the sum of all three elements.

If the sum equals zero, you found a valid triplet — add it to the result. If the sum is less than zero, move the left pointer right to increase the sum. If the sum is greater than zero, move the right pointer left to decrease the sum. Continue until left and right meet.

The outer loop runs O(n) times and the two-pointer scan is O(n) for each iteration, giving O(n^2) total time. Sorting takes O(n log n) which is dominated by the quadratic term. Space complexity is O(1) excluding the output array.

Duplicate handling is where 3Sum gets tricky and where most bugs live. There are two places you need to skip duplicates: at the fixed element (i) and at both pointers (left and right) after finding a valid triplet.

For the fixed element: after processing nums[i], skip all subsequent values that are equal. In code, that means if i > 0 and nums[i] == nums[i - 1], continue. This prevents the same first element from generating duplicate triplet sets.

For the pointers: after finding a valid triplet where sum == 0, advance the left pointer past all duplicate values (while left < right and nums[left] == nums[left + 1], increment left). Do the same for the right pointer in the opposite direction. Then move both pointers one more step inward.

Missing either of these skip steps is the most common mistake candidates make. The fixed-element skip prevents starting from the same value twice. The pointer skips prevent finding the same pair twice for a given starting value. Both are necessary for a correct solution.

Interviewers love follow-up questions about edge cases. The most obvious one: if the array has fewer than three elements, return an empty list immediately. No triplets are possible.

If every element is zero, like [0, 0, 0, 0], the only valid triplet is [0, 0, 0] and it should appear exactly once. Your duplicate-skipping logic handles this automatically — after finding the triplet, all pointers skip past the zeros.

If all elements are positive or all elements are negative, no triplet can sum to zero. After sorting, you can add an early termination: if nums[i] > 0 during the outer loop, break — no three positive numbers can sum to zero. This is a nice optimization to mention in an interview.

The 3Sum problem is a gateway to an entire family of problems. The same sort + two pointers pattern applies to 3Sum Closest (#16), 4Sum (#18), and any K-sum variant. Once you master the template, you can adapt it to handle different target sums and different values of K.

More broadly, 3Sum teaches you that sorting is a powerful preprocessing step. Many problems that seem to require brute force become tractable after sorting — it enables binary search, two pointers, and greedy approaches that would not work on unsorted input.

Practice recognizing when a problem reduces to finding pairs in a sorted array. That pattern appears in container with most water, trapping rain water, and dozens of other two-pointer problems. YeetCode flashcards help you drill these pattern connections through spaced repetition, so the recognition becomes automatic during interviews.