15. 3Sum

3Sum (LeetCode 15) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

• Blind 75 · #10 of 75 · Two Pointers
• NeetCode 150 · #12 of 150 · Two Pointers
• NeetCode 250 · #30 of 250 · Two Pointers

How to solve 3Sum

3Sum is a Converging Two Pointers problem, part of Two Pointers. Learn converging two pointers for sorted arrays. Solve two sum, three sum, and container problems efficiently.

Work towards the solution in these steps:

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!
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?
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?

The reference solution runs in O(n^2) time and O(1) space.

The 3Sum solution and editorial walks through the full approach with reference code.

Problem statement

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] <= 105

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Amazon, Facebook, Microsoft, Bloomberg, Apple, Adobe, VMware, Google, Cisco, Tesla, Goldman Sachs, eBay.

How to practise 3Sum on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(1) space.

Open 3Sum in the code editor, or read the 3Sum editorial for a worked solution with its approach and complexity analysis.

Where 3Sum sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet

Problems related to 3Sum

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Boats to Save People — Medium, same subpattern
• Container With Most Water — Medium, same subpattern
• 4Sum — Medium, same subpattern
• Squares of a Sorted Array — Easy, same subpattern
• 3Sum Closest — Medium, same subpattern
• 3Sum Smaller — Medium, same subpattern

3Sum FAQ