Watch 10 video solutions for 3Sum, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 980,205 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 not just finding triplets but avoiding duplicates while keeping the algorithm efficient.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) extra space)
The most direct approach checks every possible combination of three numbers. Use three nested loops and test whether nums[i] + nums[j] + nums[k] == 0. To avoid duplicates, you must sort each triplet and store results in a set or manually check before insertion. This approach works for understanding the problem but becomes impractical once the array size grows because the runtime grows cubically.
Approach 2: Hashing with Fixed Element (O(n^2) time, O(n) space)
Fix one element and reduce the problem to a 2‑sum search. For each index i, iterate through the remaining elements and store visited values in a hash set. When processing nums[j], check if -(nums[i] + nums[j]) already exists in the set. If it does, a valid triplet is found. Sorting the array first helps manage duplicates, while a secondary set ensures each triplet appears once. This method improves runtime to quadratic but still uses additional memory for hash lookups. It heavily relies on fast lookups from hashing.
Approach 3: Two-Pointer Technique After Sorting (O(n^2) time, O(1) extra space)
Sort the array first using sorting. Then iterate through the array and treat each element as the first number of a triplet. For the remaining portion of the array, place two pointers: one at left = i + 1 and one at the end. Compute the sum of the three values. If the sum is zero, record the triplet and move both pointers while skipping duplicates. If the sum is smaller than zero, move the left pointer forward; if larger, move the right pointer backward. This pattern leverages the sorted order to eliminate the inner search loop. The result is an efficient O(n^2) solution with constant extra memory using two pointers.
Recommended for interviews: Interviewers typically expect the sorted two‑pointer solution. It demonstrates understanding of array manipulation, duplicate handling, and pointer movement patterns. Starting with the brute force explanation shows problem‑solving reasoning, but implementing the O(n^2) two‑pointer approach signals strong algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Three Nested Loops) | O(n^3) | O(1) | Conceptual baseline or very small arrays |
| Hashing with Fixed Element | O(n^2) | O(n) | When hash lookups are acceptable and simpler logic is preferred |
| Sorting + Two Pointers | O(n^2) | O(1) | Optimal approach for interviews and large inputs |