3Sum - Solution & Explanation
Problem Statement
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Approach Overview
Problem Overview: Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The challenge is avoiding duplicate triplets while keeping the algorithm efficient for large inputs.
Approach 1: Hashing to Track Complements (O(n^2) time, O(n) space)
Fix one element and reduce the problem to a two-sum search for the remaining values. For each index i, iterate through the rest of the array and maintain a hash set of numbers you've seen. For each element nums[j], compute the required complement target = -nums[i] - nums[j] and check the set with an O(1) lookup. If the complement exists, you found a valid triplet. Sorting each discovered triplet or using a set of tuples prevents duplicates. This approach demonstrates the classic array + hashing pattern but uses extra memory and duplicate handling logic.
Approach 2: Two-Pointer Technique After Sorting (O(n^2) time, O(1) extra space)
Sort the array first, which enables an efficient two-pointer search. Iterate through the array and treat each element as the first number of the triplet. For each index i, initialize two pointers: left = i + 1 and right = n - 1. Compute the sum of nums[i] + nums[left] + nums[right]. If the sum is too small, move left forward; if it's too large, move right backward. When the sum equals zero, record the triplet and skip duplicates by advancing pointers past repeated values. Sorting ensures duplicate detection is simple and guarantees each triplet appears only once. This approach combines sorting with the classic two pointers pattern.
The key insight is that once the array is sorted, the remaining search space can be pruned quickly. Increasing the left pointer always increases the sum, and decreasing the right pointer reduces it. That monotonic behavior makes the search deterministic and avoids checking every pair combination.
Recommended for interviews: The sorted two-pointer approach is the expected solution in most coding interviews. It achieves O(n^2) time with O(1) extra space and demonstrates strong understanding of pointer techniques and duplicate handling. Mentioning the hashing variant shows awareness of alternative strategies, but the two-pointer method is cleaner and easier to reason about under interview constraints.
Approach 1: Two-Pointer Technique after Sorting
This approach involves first sorting the array. With the array sorted, you can iterate through the array with a fixed element and use two pointers to find pairs that sum to the negative of the fixed element, effectively finding triplets. This takes advantage of the sorted order to efficiently eliminate duplicates and explore potential solutions.
The solution first sorts the input array. It iterates through each element, while using two pointers to find two numbers that form a zero-sum triplet with the selected number. The two-pointer strategy makes it efficient to skip duplicates and quickly adjust to find valid pairs.
Complexity
Time Complexity: O(n^2), where n is the length of the array. Sorting the array takes O(n log n) and each element is processed with O(n) operations using the two-pointer technique.
Space Complexity: O(n) due to the space used for the output list and auxiliary storage for pointers.
Approach 2: Hashing to Avoid Duplicates
This approach employs a hash set to track previously seen elements during pointer adjustment. This helps guide pointer movement and ensures uniqueness without repetitive triplet computation by leveraging stored hash values.
This C implementation incorporates a hash-like boolean array (seen) to track output triplets, ensuring each triplet is considered uniquely despite sorting-based overlap.
Complexity
Time Complexity: O(n^2). Each combination is checked in the sorted array, similar to the two-pointer method.
Space Complexity: O(n) for auxiliary arrays supporting hash checks.
Approach 3: Sort + Two Pointers
We notice that the problem does not require us to return the triplet in order, so we might as well sort the array first, which makes it easy to skip duplicate elements.
Next, we enumerate the first element of the triplet nums[i], where 0 leq i \lt n - 2. For each i, we can find j and k satisfying nums[i] + nums[j] + nums[k] = 0 by maintaining two pointers j = i + 1 and k = n - 1. In the enumeration process, we need to skip duplicate elements to avoid duplicate triplets.
The specific judgment logic is as follows:
If i \gt 0 and nums[i] = nums[i - 1], it means that the element currently enumerated is the same as the previous element, we can skip it directly, because it will not produce new results.
If nums[i] \gt 0, it means that the element currently enumerated is greater than 0, so the sum of three numbers must not be equal to 0, and the enumeration ends.
Otherwise, we let the left pointer j = i + 1, and the right pointer k = n - 1. When j \lt k, the loop is executed, and the sum of three numbers x = nums[i] + nums[j] + nums[k] is calculated and compared with 0:
- If
x \lt 0, it means thatnums[j]is too small, we need to movejto the right. - If
x \gt 0, it means thatnums[k]is too large, we need to movekto the left. - Otherwise, it means that we have found a valid triplet, add it to the answer, move
jto the right, movekto the left, and skip all duplicate elements to continue looking for the next valid triplet.
After the enumeration is over, we can get the answer to the triplet.
The time complexity is O(n^2), and the space complexity is O(log n). The n is the length of the array.
Code
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique after Sorting | Time Complexity: O(n^2), where n is the length of the array. Sorting the array takes O(n log n) and each element is processed with O(n) operations using the two-pointer technique. Space Complexity: O(n) due to the space used for the output list and auxiliary storage for pointers. |
| Hashing to Avoid Duplicates | Time Complexity: O(n^2). Each combination is checked in the sorted array, similar to the two-pointer method. Space Complexity: O(n) for auxiliary arrays supporting hash checks. |
| Sort + Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashing with Fixed Element | O(n^2) | O(n) | When you want a direct extension of the Two Sum hash map technique |
| Sorting + Two Pointers | O(n^2) | O(1) extra | Best general solution; clean duplicate handling and standard interview expectation |
| Brute Force Triple Loop | O(n^3) | O(1) | Only useful for explaining the baseline before optimization |
Video Solution
3Sum - Leetcode 15 - Python • NeetCode • 1,275,247 views views
Watch 9 more video solutions →Frequently Asked Questions
Is 3Sum easy or hard?
How to solve 3Sum in O(n)?
What is the best approach for 3Sum?
What data structure is used in 3Sum?
What is the time complexity of 3Sum?
3Sum Python or Java solution approach?
Is 3Sum asked at Google, Amazon, or Meta interviews?
Ready to solve this problem?
Practice 3Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor