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] <= 105The 3Sum problem asks you to find all unique triplets in an array whose sum equals 0. A naive approach would check every possible combination of three numbers, but that results in O(n^3) time and is inefficient for large inputs.
A more optimized strategy uses sorting and the two-pointer technique. First, sort the array so that values are processed in order. Then iterate through the array, treating each element as a potential first element of a triplet. For the remaining part of the array, use two pointers—one starting just after the current element and another at the end of the array—to search for pairs that complete the required sum.
Because the array is sorted, you can move pointers inward depending on whether the current sum is too large or too small. Careful handling of duplicate values is important to ensure only unique triplets are returned. This approach significantly reduces the time complexity compared to brute force while keeping additional space usage minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all triplets) | O(n^3) | O(1) |
| Sorting + Two Pointers | O(n^2) | O(1) (excluding output) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!
For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmp(const void *a, const void *b) {
5
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.
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, 3Sum is a classic interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of sorting, two-pointer techniques, and handling duplicates in arrays.
The optimal approach sorts the array and then uses a two-pointer technique while iterating through each element as the first value of the triplet. This reduces the time complexity from O(n^3) to O(n^2). Sorting also helps efficiently skip duplicate values and avoid repeated triplets.
Sorting enables the two-pointer strategy, which allows you to adjust pointers based on whether the current sum is too large or too small. It also makes it easy to skip duplicate numbers and ensure that only unique triplets are included in the result.
Most optimized solutions rely primarily on arrays with the two-pointer technique after sorting. Some alternative approaches may use hash sets to detect complements, but the sorting plus two-pointer method is generally preferred for clarity and efficiency.
This C implementation incorporates a hash-like boolean array (seen) to track output triplets, ensuring each triplet is considered uniquely despite sorting-based overlap.