LeetCode · #15

3Sum Solution

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i ≠ j ≠ k and nums[i] + nums[j] + nums[k] == 0. No duplicate triplets.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #15

🏗️

Pattern

Sort + Two Pointers

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. The solution set must not contain duplicate triplets.

Example

 Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
// Two unique triplets that sum to 0 

Constraints

 • 3 ≤ nums.length ≤ 3000 • -10⁵ ≤ nums[i] ≤ 10⁵ • No duplicate triplets in the result 

Section Two · Approach 1

Brute Force — O(n³)

Three nested loops checking all triplets. Use a set or sort each triplet to deduplicate. Correct but far too slow for n = 3000.

Problem: O(n³) is ~27 billion operations for n = 3000. By sorting the array first, we fix one element and reduce the remaining two-element search to a two-pointer scan — dropping to O(n²).

Java — Brute Force

 import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++)
for (int j = i+1; j < nums.length; j++)
for (int k = j+1; k < nums.length; k++)
if (nums[i]+nums[j]+nums[k] == 0)
                        result.add(List.of(nums[i], nums[j], nums[k]));
return new ArrayList<>(result);
    }
}

Python — Brute Force

 class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = set()
for i in range(len(nums)):
for j in range(i+1, len(nums)):
for k in range(j+1, len(nums)):
if nums[i]+nums[j]+nums[k] == 0:
                        result.add((nums[i], nums[j], nums[k]))
return [list(t) for t in result]

Metric	Value
Time	O(n³)
Space	O(n) for dedup set

Section Three · Approach 2

Sort + Two Pointers — O(n²)

Sort the array. For each element nums[i], use two pointers on the remaining subarray to find pairs that sum to -nums[i]. Skip duplicates at all three positions to avoid repeated triplets.

💡 Mental model: Think of it as anchoring one number, then solving Two Sum II on the rest. You fix one person in a group photo, then find two others whose combined effect balances the first. Sorting lets you skip duplicates and use converging pointers.

Algorithm

Step 1: Sort the array.
Step 2: For each index i from 0 to n−3:
Step 3: Skip if nums[i] == nums[i-1] (avoid duplicate first element).
Step 4: If nums[i] > 0 → break (no three positives sum to 0).
Step 5: Set left = i+1, right = n-1. Run Two Sum II for target -nums[i].
Step 6: When a triplet is found, skip duplicate values for both left and right pointers.

🎯 Duplicate skipping is the hard part.:

Three places to skip: (1) skip duplicate nums[i] in the outer loop, (2) after finding a triplet, skip duplicate nums[left] moving right, (3) skip duplicate nums[right] moving left.
Missing any one produces duplicate triplets.

Section Four · Trace

Visual Walkthrough

Trace through nums = [-1, 0, 1, 2, -1, -4] → sorted: [-4, -1, -1, 0, 1, 2]:

Sort + fix i, two-pointer scan for complement pair

Section Five · Implementation

Code — Java & Python

Java — Sort + Two Pointers

 import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // no positives sum to 0 if (i > 0 && nums[i] == nums[i - 1]) continue; // skip dup i int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) left++;
else if (sum > 0) right--;
else {
                    result.add(List.of(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
return result;
    }
}

Python — Sort + Two Pointers

 class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []
for i in range(len(nums) - 2):
if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue
left, right = i + 1, len(nums) - 1 while left < right:
                total = nums[i] + nums[left] + nums[right]
if total < 0:    left += 1 elif total > 0: right -= 1 else:
                    result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1
right -= 1 return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n³)	O(n)	Check all triplets; dedup with set
HashMap per pair	O(n²)	O(n)	Fix i, HashMap for j+k; harder dedup
Sort + Two Pointers ← optimal	O(n²)	O(1)*	Clean dedup via pointer skipping. *Excluding output.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All zeros	`[0, 0, 0, 0]`	Only one triplet [0,0,0]. Duplicate skipping prevents repeats.
No solution	`[1, 2, 3]`	All positive — no triplet sums to 0. Early break at nums[i] > 0.
Minimum length	`[-1, 0, 1]`	Exactly one triplet. i=0, L=1, R=2.
Many duplicates	`[-2,-2,0,0,2,2]`	Multiple valid triplets but each only once: [-2,0,2].
All same negative	`[-1,-1,-1]`	Sum = -3 ≠ 0. No valid triplet → empty result.

⚠ Common Mistake: Forgetting to skip duplicates in all three positions. Skipping only at the outer loop but not after finding a triplet produces duplicate results. After each found triplet, always advance left past its duplicates AND advance right past its duplicates before continuing.

← Back to Two Pointers problems

LearningTree

LC 15 · 3Sum — Solution & Explanation | DSA Guide