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] <= 105Problem 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
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 | 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. |
| 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 |
3Sum - Leetcode 15 - Python • NeetCode • 980,205 views views
Watch 9 more video solutions →Practice 3Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor