Is 3Sum easy or hard?

3Sum is generally classified as a medium-level problem. The logic becomes manageable once you recognize that sorting allows a two-pointer search, but handling duplicates and avoiding repeated triplets requires careful pointer movement.

How to solve 3Sum in O(n)?

An O(n) solution for the general 3Sum problem is not possible because at least two nested scans are required to examine combinations of three elements. The best known solution is O(n^2) using sorting and the two-pointer technique, which significantly improves over the O(n^3) brute force approach.

What is the best approach for 3Sum?

The most efficient and commonly expected solution uses sorting followed by the two-pointer technique. After sorting the array, fix one element and search for the remaining two numbers using pointers from both ends. This reduces the problem to O(n^2) time and O(1) extra space while making duplicate removal straightforward.

What data structure is used in 3Sum?

The problem primarily uses arrays along with either a hash set for complement lookup or the two-pointer technique after sorting. The hash-based approach relies on O(1) average-time lookups, while the optimized solution leverages the sorted array structure to move pointers efficiently.

What is the time complexity of 3Sum?

The optimal algorithm runs in O(n^2) time. Sorting takes O(n log n), and then each element is used as a fixed value while two pointers scan the rest of the array in linear time. Since this happens for up to n elements, the overall complexity becomes O(n^2).

3Sum Python or Java solution approach?

Both Python and Java implementations typically sort the array and apply the two-pointer method. Iterate through the array, fix one number, and move two pointers inward while skipping duplicates. This produces all unique triplets in O(n^2) time.

Is 3Sum asked at Google, Amazon, or Meta interviews?

3Sum and its variations appear frequently in technical interviews at companies like Amazon, Meta, Google, and Microsoft. Interviewers use it to test array manipulation, duplicate handling, sorting strategies, and mastery of the two-pointer pattern.

Description Hints 3 Solution Video 12:54

15. 3Sum

Medium40.1% acceptance57 companies

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
-10⁵ <= nums[i] <= 10⁵

Asked at top 20 of 57 companies

Cisco Vimeo Gojek Quince Works Applications Garena Goto Singlestore Shipsy Adobe Visa Accenture

+8 more

Qualcomm Wix Autodesk Myntra Roku Cloudflare Oyo WarnerMedia

Topics

Hints open one at a time

Hint 1

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!

Hint 2

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?

Hint 3

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?

12:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution