Watch 10 video solutions for 3Sum, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 1,212,400 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |