Log inSign up
mediumLeetCodeNot Started

3Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return all the unique 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 · Standard Mixed Array:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The distinct triplets that sum to 0 are [-1, -1, 2] and [-1, 0, 1]. Notice that [-1, 0, 1] and [0, 1, -1] are the same triplet and only appear once.

Example 2 · No Valid Triplet:

Input: nums = [0, 1, 1]
Output: []
Explanation: The only possible triplet has sum = 0 + 1 + 1 = 2 != 0.

Example 3 · All Zeros Array:

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: The only valid triplet is [0, 0, 0].

Constraints:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two Sum II (Two Pointers on sorted arrays)
  • Array sorting techniques and custom comparators
  • Duplicate element avoidance strategies

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the pivot-fixing strategy to decompose O(N3) problems into O(N2).
  • Prune duplicate results cleanly during pointer advancement without relying on expensive hash sets.
  • Apply early termination optimizations to eliminate impossible sub-problems.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding 3 elements in an array that add up to a fixed target (such as 0 or K).
  • Constraint N <= 3000 hints that an O(N2) time complexity is expected.
  • Requirement to strictly avoid duplicate triplets in the output.

Algorithmic Decision Tree:

  • When finding unique triplets summing to target: Sort the array first, fix one element as a pivot in an outer loop, and use Two Pointers to find matching pairs in the remaining subarray.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Three Nested Loops with Hash Set (Brute Force)

Intuition

Check every possible triplet combination (i, j, k) with three nested loops and store sorted triplets in a set to avoid duplicates.

Algorithm

  1. 1. Initialize a hash set to store unique triplets.
  2. 2. Loop i from 0 to N - 1.
  3. 3. Nested loop j from i + 1 to N - 1.
  4. 4. Nested loop k from j + 1 to N - 1.
  5. 5. If nums[i] + nums[j] + nums[k] == 0, sort the triplet [nums[i], nums[j], nums[k]] and add it to the set.
  6. 6. Return the list of all triplets in the set.

Brute Force Three Nested Loops Enumeration

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-4, -1, -1, 0, 1, 2]
Current operationSTEP 1 OF 7
Triplet (0, 1, 5): Sum is -3
Visual state
Values and pointers at this exact step
pointers
S
-4
-1
-1
0
1
2
0
↑ i=0
1
↑ j=1
2
3
4
5
↑ k=5
Variables at this step
i
-4
j
-1
k
2
Sum
-3
Match
No
Check / comparison
nums[0] + nums[1] + nums[5] = -4 + (-1) + 2 = -3 != 0
Decision / next transition
Sum -3 != 0. Advance k.
Why this step matters

Triplet (0, 1, 5): Sum is -3. No triplet starting with index 0 sums to 0.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> threeSum(vector<int>& nums) {
17 int n = nums.size();
18 set<vector<int>> st;
19 for (int i = 0; i < n; i++) {
20 for (int j = i + 1; j < n; j++) {
21 for (int k = j + 1; k < n; k++) {
22 if (nums[i] + nums[j] + nums[k] == 0) {
23 vector<int> temp = {nums[i], nums[j], nums[k]};
24 sort(temp.begin(), temp.end());
25 st.insert(temp);
26 }
27 }
28 }
29 }
30 return vector<vector<int>>(st.begin(), st.end());
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> nums = {-1, 0, 1, 2, -1, -4};
37 vector<vector<int>> res = sol.threeSum(nums);
38 cout << "Unique Triplets:" << endl;
39 for (const auto& triplet : res) {
40 cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "] ";
41 }
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N^3 * log 3) = O(N^3) — Three nested loops yield N*(N-1)*(N-2)/6 triplet checks. Inserting and sorting each triplet takes constant time.
  • Space complexity: O(2 * K) where K is number of unique triplets — Requires a set to store unique triplets, taking memory proportional to the number of valid triplets.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Two Loops with Hash Set (Better)

Intuition

Fix index i, then for every index j, check if target third value -(nums[i] + nums[j]) exists in a hash set of visited intermediate elements.

Algorithm

  1. 1. Initialize an outer set uniqueTriplets.
  2. 2. Loop i from 0 to N - 1.
  3. 3. Create a local hash set seen.
  4. 4. Loop j from i + 1 to N - 1: - third = -(nums[i] + nums[j]) - If third is in seen: sort [nums[i], nums[j], third] and insert into uniqueTriplets. - Insert nums[j] into seen.
  5. 5. Return list of unique triplets.

Hash Set Inner Complement Lookup for 3Sum

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-4, -1, -1, 0, 1, 2]
Current operationSTEP 1 OF 7
Iteration i=0: Fix -4
Visual state
Values and pointers at this exact step
table
Input array
S
-4
-1
-1
0
1
2
0
↑ Fixed i=0
1
2
3
4
5
Hash map state
Execution state
Fixed i-4
Target Sum4
FoundNone
Inner loop scans for pairs summing to 4. None found.
Variables at this step
Fixed i
-4
Target Sum
4
Found
None
Check / comparison
Target complement = -nums[0] = -(-4) = 4.
Decision / next transition
Inner loop scans for pairs summing to 4. None found.
Why this step matters

Iteration i=0: Fix -4. Inner loop checks for elements summing to 4. Seen set contains no complement matching 4.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> threeSum(vector<int>& nums) {
17 int n = nums.size();
18 set<vector<int>> st;
19 for (int i = 0; i < n; i++) {
20 unordered_set<int> seen;
21 for (int j = i + 1; j < n; j++) {
22 int third = -(nums[i] + nums[j]);
23 if (seen.find(third) != seen.end()) {
24 vector<int> temp = {nums[i], nums[j], third};
25 sort(temp.begin(), temp.end());
26 st.insert(temp);
27 }
28 seen.insert(nums[j]);
29 }
30 }
31 return vector<vector<int>>(st.begin(), st.end());
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> nums = {-1, 0, 1, 2, -1, -4};
38 vector<vector<int>> res = sol.threeSum(nums);
39 cout << "Unique Triplets:" << endl;
40 for (const auto& triplet : res) {
41 cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "] ";
42 }
43 cout << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N^2 * log(no. of unique triplets)) — Two nested loops run in O(N2). Hash set lookups and insertions take O(1) on average.
  • Space complexity: O(N) for hash set + O(2 * K) for output set — The inner hash set consumes O(N) memory, and the outer set stores unique triplets.

3. Sorting + Converging Two Pointers (Optimal)

Intuition

Sort the array, fix pivot nums[i], and use two converging pointers (left, right) with duplicate skipping to achieve O(N2) time and O(1) extra space.

Algorithm

  1. 1. Sort array nums in ascending order.
  2. 2. Loop i from 0 to N - 3: - If i > 0 and nums[i] == nums[i-1], continue. - left = i + 1, right = N - 1. - While left < right: - sum = nums[i] + nums[left] + nums[right] - If sum < 0: left++ - Else if sum > 0: right-- - Else: record [nums[i], nums[left], nums[right]], increment left while nums[left]==nums[left-1], decrement right while nums[right]==nums[right+1].
  3. 3. Return the result list.

Sorted Two-Pointer Traversal Trace for 3Sum

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [-4, -1, -1, 0, 1, 2]
Current operationSTEP 1 OF 7
Iteration 1 — Fix i = 0 (-4): After sorting [-4, -1, -1, 0, 1, 2], we fix i=0 (-4)
Visual state
Values and pointers at this exact step
pointers
S
-4
-1
-1
0
1
2
0
↑ i (Fixed)
1
↑ L
2
3
4
5
↑ R
Variables at this step
i (Fixed)
-4 (Idx 0)
L Pointer
-1 (Idx 1)
R Pointer
2 (Idx 5)
Current Sum
-3
Action
L++ (Too Small)
Check / comparison
nums[i] + nums[L] + nums[R] = -4 + (-1) + 2 = -3 < 0.
Decision / next transition
Sum too small (-3 < 0). Increment L to seek larger values.
Why this step matters

Iteration 1 — Fix i = 0 (-4): After sorting [-4, -1, -1, 0, 1, 2], we fix i=0 (-4). Inner pointers start at L=1 (-1) and R=5 (2). Sum = -3. Since sum < 0, we must increase the sum by advancing L to index 2.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> threeSum(vector<int>& nums) {
17 vector<vector<int>> ans;
18 int n = nums.size();
19 sort(nums.begin(), nums.end());
20
21 for (int i = 0; i < n; i++) {
22 if (i > 0 && nums[i] == nums[i - 1]) continue;
23 int left = i + 1, right = n - 1;
24 while (left < right) {
25 long long sum = (long long)nums[i] + nums[left] + nums[right];
26 if (sum < 0) {
27 left++;
28 } else if (sum > 0) {
29 right--;
30 } else {
31 ans.push_back({nums[i], nums[left], nums[right]});
32 left++;
33 right--;
34 while (left < right && nums[left] == nums[left - 1]) left++;
35 while (left < right && nums[right] == nums[right + 1]) right--;
36 }
37 }
38 }
39 return ans;
40 }
41};
42
43int main() {
44 Solution sol;
45 vector<int> nums = {-1, 0, 1, 2, -1, -4};
46 vector<vector<int>> res = sol.threeSum(nums);
47 cout << "Unique Triplets:" << endl;
48 for (const auto& triplet : res) {
49 cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "] ";
50 }
51 cout << endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N log N + N^2) = O(N^2) — Sorting takes O(N log N). The outer loop runs N times and the inner two-pointer scan takes O(N) total per pivot, leading to O(N2) overall runtime.
  • Space complexity: O(1) auxiliary (or O(log N) for sorting stack) — Only a few pointer variables are used. No hash sets or extra data structures are required.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Three Nested Loops with Hash Set (Brute Force)O(N^3 * log 3) = O(N^3)O(2 * K) where K is number of unique tripletsCheck every possible triplet combination (i, j, k) with three nested loops and store sorted triplets in a set to avoid duplicates.Repeated redundant scans over the input.
2.Approach 2: Two Loops with Hash Set (Better)O(N^2 * log(no. of unique triplets))O(N) for hash set + O(2 * K) for output setFix index i, then for every index j, check if target third value -(nums[i] + nums[j]) exists in a hash set of visited intermediate elements.Auxiliary memory allocation or sorting step.
3.Approach 3: Sorting + Converging Two Pointers (Optimal)OptimalO(N log N + N^2) = O(N^2)O(1) auxiliary (or O(log N) for sorting stack)Sort the array, fix pivot nums[i], and use two converging pointers (left, right) with duplicate skipping to achieve O(N2) time and O(1) ...None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All Zeros [0, 0, 0, 0, 0] — Input: `, Expected: ` —
  • No Valid Triplet [1, 2, 3, 4] — Input: `, Expected: ` —
  • Multiple Negative and Positive Combinations — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for 3Sum?

2.Why is the brute force approach suboptimal for large inputs in 3Sum?

3.Which data structure or technique enables the optimal solution for 3Sum?

Back to DSA Sheet