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.
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 |
|---|---|---|---|
| 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 |
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