Problem editorial

3Sum

MediumTwo PointersArrayTwo PointersSorting

Editorial

Core insight

3Sum · Two Pointers

Core Insight for 3Sum

The key intuition is to reduce the dimension of the problem. 3Sum is essentially 2Sum wrapped in a loop. If we fix one number, say nums[i], we simply need to find two other numbers, nums[left] and nums[right], such that:

nums[left] + nums[right] = -nums[i]

For the Two Pointers - Converging strategy to work, the array must be sorted. Sorting provides two critical advantages:

Monotonicity: We can make deterministic decisions about moving pointers. If the sum is too small, we must move the left pointer to the right to increase the sum. If the sum is too large, we must move the right pointer to the left to decrease it.
Duplicate Avoidance: Sorting places identical elements adjacent to each other. This allows us to easily skip duplicates by checking if the current element is the same as the previous one, ensuring the uniqueness of triplets without using a Hash Set.

Visual Description: Imagine the array is sorted in ascending order. We iterate through the array with index i. For each i, we define a search window for the remaining two numbers starting at i + 1 (left pointer) and ending at length - 1 (right pointer).

If nums[i] + nums[left] + nums[right] < 0, the sum is too low. Because the array is sorted, the only way to increase the sum is to increment the left pointer.
If nums[i] + nums[left] + nums[right] > 0, the sum is too high. We must decrement the right pointer to find a smaller number.
If the sum is 0, we record the triplet and shrink the window from both sides, skipping any duplicate values to prevent redundant outputs.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 15: 3Sum Solution & Explanation

Problem Overview

TL;DR: The optimal solution involves sorting the array and iterating through it, using the Two Pointers technique to find two other numbers that sum to the negative of the current number.

The 3Sum problem asks us to identify all unique triplets [nums[i], nums[j], nums[k]] within an integer array such that their sum equals zero. The indices must be distinct, and the result set must not contain duplicate triplets. This is a classic variation of the subset sum problem and a foundational interview question often referred to as LeetCode 15. It serves as a direct extension of the 2Sum problem but introduces complexity regarding duplicate handling and time efficiency.

Brute Force Approach for 3Sum

The most intuitive approach is to check every possible combination of three numbers to see if they sum to zero. This involves three nested loops.

Pseudo-code:

text

sort(nums) // Optional for brute force, but helps with duplicates
Initialize set results
For i from 0 to n-1:
    For j from i+1 to n-1:
        For k from j+1 to n-1:
            If nums[i] + nums[j] + nums[k] == 0:
                Add {nums[i], nums[j], nums[k]} to results
Return list(results)

Time Complexity: $O(N^3)$ The algorithm iterates through the array three times. If $N = 3000$ (the upper constraint), this results in approximately $2.7 \times 10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed in coding interviews.

Why it fails:

Time Limit Exceeded (TLE): The cubic complexity is inefficient for the given constraints ( $N \le 3000$ ).
Duplicate Management: Without careful logic or a Set data structure, this approach generates duplicate triplets (e.g., if the input has multiple -1s), which violates the problem requirements.

Algorithm Strategy: Two Pointer Patterns

Sort the Input: Begin by sorting the array nums. This is a prerequisite for the converging pointers pattern.
Iterate and Fix: Loop through the array with index i from 0 to n-3. The element nums[i] acts as the fixed pivot.
Skip Outer Duplicates: If nums[i] is the same as nums[i-1], skip this iteration to avoid generating duplicate triplets based on the same first element.
Initialize Pointers: Set left = i + 1 and right = n - 1.
Converge: While left < right:
- Calculate sum = nums[i] + nums[left] + nums[right].
- Target Hit: If sum == 0, add the triplet to the result. Then, increment left and decrement right. Crucially, continue incrementing left while nums[left] == nums[left-1] and decrementing right while nums[right] == nums[right+1] to skip inner duplicates.
- Too Low: If sum < 0, increment left.
- Too High: If sum > 0, decrement right.

Execution Flow

Let's trace nums = [-1, 0, 1, 2, -1, -4].

Sort: nums becomes [-4, -1, -1, 0, 1, 2].
i = 0, nums[i] = -4:
- Target for 2Sum is 4.
- left at -1 (index 1), right at 2 (index 5).
- Sum is -4 + (-1) + 2 = -3 (Too low). Increment left.
- ... (Continue converging). No pairs sum to 4.
i = 1, nums[i] = -1:
- Target for 2Sum is 1.
- left at -1 (index 2), right at 2 (index 5).
- Sum is -1 + (-1) + 2 = 0. Match found: [-1, -1, 2].
- Move left to 0 (index 3), right to 1 (index 4).
- Sum is -1 + 0 + 1 = 0. Match found: [-1, 0, 1].
- Pointers cross.
i = 2, nums[i] = -1:
- Check duplicate condition: nums[2] == nums[1]. Skip to avoid duplicate triplets.
i = 3, nums[i] = 0:
- Target is 0.
- left at 1, right at 2. Sum is 3. Too high.
- Pointers cross.
End: Return [[-1, -1, 2], [-1, 0, 1]].

Proof of Correctness

The correctness relies on the sorted nature of the array and the exhaustive search of the solution space.

Completeness: By iterating i through the array, we consider every number as a potential first element of the triplet. For each i, the Two Pointer approach scans the entire valid range (i+1 to n-1) to find all pairs completing the sum. Since the function f(left, right) = nums[left] + nums[right] is monotonically increasing with left and decreasing with right, the converging pointers are guaranteed not to miss any valid pair for the fixed nums[i].
Uniqueness: By sorting and explicitly skipping adjacent identical values for both the fixed pivot i and the pointers left and right after a match, we ensure that no triplet combination is processed more than once.

Pattern Reuse Notes

The Two Pointers - Converging pattern used in this LeetCode 15 solution is highly versatile. It applies directly to:

LeetCode 167: Two Sum II - Input Array Is Sorted: The inner loop of 3Sum is exactly this problem.
LeetCode 16: 3Sum Closest: Same logic, but instead of checking sum == 0, we track the minimum difference from the target.
LeetCode 18: 4Sum: Adds one more layer of nested loops, reducing 4Sum to 3Sum, and then to 2Sum.
LeetCode 11: Container With Most Water: Uses converging pointers to maximize area, moving the pointer pointing to the shorter line.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 15

cpp

1class Solution {
2public:
3    vector<vector<int>> threeSum(vector<int>& nums) {
4        vector<vector<int>> result;
5        int n = nums.size();
6        
7        // Step 1: Sort the array
8        sort(nums.begin(), nums.end());
9        
10        for (int i = 0; i < n - 2; ++i) {
11            // Step 3: Skip duplicates for the fixed element
12            if (i > 0 && nums[i] == nums[i - 1]) {
13                continue;
14            }
15            
16            int left = i + 1;
17            int right = n - 1;
18            
19            while (left < right) {
20                int total = nums[i] + nums[left] + nums[right];
21                
22                if (total == 0) {
23                    result.push_back({nums[i], nums[left], nums[right]});
24                    
25                    // Skip duplicates for the second element
26                    while (left < right && nums[left] == nums[left + 1]) {
27                        left++;
28                    }
29                    // Skip duplicates for the third element
30                    while (left < right && nums[right] == nums[right - 1]) {
31                        right--;
32                    }
33                    
34                    left++;
35                    right--;
36                } else if (total < 0) {
37                    left++; // Need a larger sum
38                } else {
39                    right--; // Need a smaller sum
40                }
41            }
42        }
43        
44        return result;
45    }
46};

Java Solution for LeetCode 15

java

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> threeSum(int[] nums) {
7        List<List<Integer>> result = new ArrayList<>();
8        // Step 1: Sort the array
9        Arrays.sort(nums);
10        
11        for (int i = 0; i < nums.length - 2; i++) {
12            // Step 3: Skip duplicates for the fixed element
13            if (i > 0 && nums[i] == nums[i - 1]) {
14                continue;
15            }
16            
17            int left = i + 1;
18            int right = nums.length - 1;
19            
20            while (left < right) {
21                int sum = nums[i] + nums[left] + nums[right];
22                
23                if (sum == 0) {
24                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
25                    
26                    // Skip duplicates for the second element
27                    while (left < right && nums[left] == nums[left + 1]) {
28                        left++;
29                    }
30                    // Skip duplicates for the third element
31                    while (left < right && nums[right] == nums[right - 1]) {
32                        right--;
33                    }
34                    
35                    left++;
36                    right--;
37                } else if (sum < 0) {
38                    left++; // Sum too low, move right
39                } else {
40                    right--; // Sum too high, move left
41                }
42            }
43        }
44        
45        return result;
46    }
47}

Python Solution for LeetCode 15

python

1class Solution:
2    def threeSum(self, nums: List[int]) -> List[List[int]]:
3        result = []
4        # Step 1: Sort the array
5        nums.sort()
6        n = len(nums)
7        
8        for i in range(n - 2):
9            # Step 3: Skip duplicates for the fixed element
10            if i > 0 and nums[i] == nums[i - 1]:
11                continue
12            
13            left = i + 1
14            right = n - 1
15            
16            while left < right:
17                total = nums[i] + nums[left] + nums[right]
18                
19                if total == 0:
20                    result.append([nums[i], nums[left], nums[right]])
21                    
22                    # Skip duplicates for the second element
23                    while left < right and nums[left] == nums[left + 1]:
24                        left += 1
25                    # Skip duplicates for the third element
26                    while left < right and nums[right] == nums[right - 1]:
27                        right -= 1
28                        
29                    left += 1
30                    right -= 1
31                elif total < 0:
32                    left += 1
33                else:
34                    right -= 1
35                    
36        return result

AI Coach Insight

For 3Sum, focus on explaining why the structure works, not just naming Two Pointers.

Complexity Analysis

Time Complexity: $O(N^2)$
- Sorting the array takes $O(N \log N)$ .
- The outer loop runs $N$ times.
- The inner Two Pointers loop runs in $O(N)$ time (each element is visited at most once by left or right).
- Total time is $O(N \log N + N^2)$ , which simplifies to $O(N^2)$ .
Space Complexity: $O(1)$ or $O(N)$ (depending on sorting)
- We use a constant amount of extra space for pointers.
- However, the sorting algorithm implementation (e.g., QuickSort or MergeSort) may use $O(\log N)$ or $O(N)$ stack space.
- Note: The space required for the output list is not usually counted towards space complexity in interview settings.

Related Patterns

Pattern: Two Pointer Patterns Subpattern: Two Pointers - Converging (Sorted Array Target Sum)

This problem fits the Converging Two Pointers pattern because, once the array is sorted, the problem of finding three numbers that sum to zero can be reduced to fixing one number and finding two others that sum to a specific target. The sorted property allows us to optimize the search for the remaining two numbers from $O(N)$ to $O(N)$ per iteration, reducing the total complexity significantly.

Common Mistakes & FAQ

Why does my solution output duplicate triplets like [-1, 0, 1] twice?
- Mistake: Failing to skip duplicates after finding a valid triplet or failing to skip duplicates for the outer loop variable i.
- Reasoning: The problem allows identical numbers in the input but forbids identical triplets in the output. If the input is [-1, -1, 0, 1], simply moving pointers one step after a match might process the second -1 as a new unique start.
- Consequence: Incorrect Answer (WA).
Why do I get Time Limit Exceeded (TLE) even with Two Pointers?
- Mistake: Using a Set to handle duplicates instead of manual pointer skipping, or not sorting initially.
- Reasoning: While a Set handles uniqueness, the overhead of hashing and insertion can be significant. More critically, if you don't sort, you cannot use the $O(N)$ two-pointer logic and might inadvertently fall back to $O(N^2)$ for the inner search, resulting in $O(N^3)$ total.
- Consequence: Efficiency failure.
Why does the code fail on [0, 0, 0]?
- Mistake: Strict inequality checks or incorrect loop bounds.
- Reasoning: If the logic strictly requires nums[left] < nums[right] in a way that prevents handling identical values that are distinct indices, it fails.
- Consequence: Missing valid triplets.
Why can't I use a Hash Map for the inner loop (like Two Sum)?
- Mistake: Using a Hash Map approach inside the loop to find the complement.
- Reasoning: While this results in $O(N^2)$ time complexity, handling duplicates becomes much harder. You would likely need to sort the resulting triplets and store them in a Set to ensure uniqueness, which adds overhead and complexity compared to the sorted Two Pointer approach.
- Consequence: Code becomes unnecessarily complex and error-prone regarding duplicates.

Practise 3Sum and the problems around it

3Sum is a Two Pointers problem, in the Converging (Sorted Array Target Sum) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

3Sum · Two Pointers

Core Insight for 3Sum

nums[left] + nums[right] = -nums[i]

For the Two Pointers - Converging strategy to work, the array must be sorted. Sorting provides two critical advantages:

Monotonicity: We can make deterministic decisions about moving pointers. If the sum is too small, we must move the left pointer to the right to increase the sum. If the sum is too large, we must move the right pointer to the left to decrease it.
Duplicate Avoidance: Sorting places identical elements adjacent to each other. This allows us to easily skip duplicates by checking if the current element is the same as the previous one, ensuring the uniqueness of triplets without using a Hash Set.

If nums[i] + nums[left] + nums[right] < 0, the sum is too low. Because the array is sorted, the only way to increase the sum is to increment the left pointer.
If nums[i] + nums[left] + nums[right] > 0, the sum is too high. We must decrement the right pointer to find a smaller number.
If the sum is 0, we record the triplet and shrink the window from both sides, skipping any duplicate values to prevent redundant outputs.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 15: 3Sum Solution & Explanation

Problem Overview

TL;DR: The optimal solution involves sorting the array and iterating through it, using the Two Pointers technique to find two other numbers that sum to the negative of the current number.

Brute Force Approach for 3Sum

The most intuitive approach is to check every possible combination of three numbers to see if they sum to zero. This involves three nested loops.

Pseudo-code:

text

sort(nums) // Optional for brute force, but helps with duplicates
Initialize set results
For i from 0 to n-1:
    For j from i+1 to n-1:
        For k from j+1 to n-1:
            If nums[i] + nums[j] + nums[k] == 0:
                Add {nums[i], nums[j], nums[k]} to results
Return list(results)

Why it fails:

Time Limit Exceeded (TLE): The cubic complexity is inefficient for the given constraints ( $N \le 3000$ ).
Duplicate Management: Without careful logic or a Set data structure, this approach generates duplicate triplets (e.g., if the input has multiple -1s), which violates the problem requirements.

Algorithm Strategy: Two Pointer Patterns

Sort the Input: Begin by sorting the array nums. This is a prerequisite for the converging pointers pattern.
Iterate and Fix: Loop through the array with index i from 0 to n-3. The element nums[i] acts as the fixed pivot.
Skip Outer Duplicates: If nums[i] is the same as nums[i-1], skip this iteration to avoid generating duplicate triplets based on the same first element.
Initialize Pointers: Set left = i + 1 and right = n - 1.
Converge: While left < right:
- Calculate sum = nums[i] + nums[left] + nums[right].
- Target Hit: If sum == 0, add the triplet to the result. Then, increment left and decrement right. Crucially, continue incrementing left while nums[left] == nums[left-1] and decrementing right while nums[right] == nums[right+1] to skip inner duplicates.
- Too Low: If sum < 0, increment left.
- Too High: If sum > 0, decrement right.

Execution Flow

Let's trace nums = [-1, 0, 1, 2, -1, -4].

Sort: nums becomes [-4, -1, -1, 0, 1, 2].
i = 0, nums[i] = -4:
- Target for 2Sum is 4.
- left at -1 (index 1), right at 2 (index 5).
- Sum is -4 + (-1) + 2 = -3 (Too low). Increment left.
- ... (Continue converging). No pairs sum to 4.
i = 1, nums[i] = -1:
- Target for 2Sum is 1.
- left at -1 (index 2), right at 2 (index 5).
- Sum is -1 + (-1) + 2 = 0. Match found: [-1, -1, 2].
- Move left to 0 (index 3), right to 1 (index 4).
- Sum is -1 + 0 + 1 = 0. Match found: [-1, 0, 1].
- Pointers cross.
i = 2, nums[i] = -1:
- Check duplicate condition: nums[2] == nums[1]. Skip to avoid duplicate triplets.
i = 3, nums[i] = 0:
- Target is 0.
- left at 1, right at 2. Sum is 3. Too high.
- Pointers cross.
End: Return [[-1, -1, 2], [-1, 0, 1]].

Proof of Correctness

The correctness relies on the sorted nature of the array and the exhaustive search of the solution space.

Completeness: By iterating i through the array, we consider every number as a potential first element of the triplet. For each i, the Two Pointer approach scans the entire valid range (i+1 to n-1) to find all pairs completing the sum. Since the function f(left, right) = nums[left] + nums[right] is monotonically increasing with left and decreasing with right, the converging pointers are guaranteed not to miss any valid pair for the fixed nums[i].
Uniqueness: By sorting and explicitly skipping adjacent identical values for both the fixed pivot i and the pointers left and right after a match, we ensure that no triplet combination is processed more than once.

Pattern Reuse Notes

The Two Pointers - Converging pattern used in this LeetCode 15 solution is highly versatile. It applies directly to:

LeetCode 167: Two Sum II - Input Array Is Sorted: The inner loop of 3Sum is exactly this problem.
LeetCode 16: 3Sum Closest: Same logic, but instead of checking sum == 0, we track the minimum difference from the target.
LeetCode 18: 4Sum: Adds one more layer of nested loops, reducing 4Sum to 3Sum, and then to 2Sum.
LeetCode 11: Container With Most Water: Uses converging pointers to maximize area, moving the pointer pointing to the shorter line.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 15

cpp

1class Solution {
2public:
3    vector<vector<int>> threeSum(vector<int>& nums) {
4        vector<vector<int>> result;
5        int n = nums.size();
6        
7        // Step 1: Sort the array
8        sort(nums.begin(), nums.end());
9        
10        for (int i = 0; i < n - 2; ++i) {
11            // Step 3: Skip duplicates for the fixed element
12            if (i > 0 && nums[i] == nums[i - 1]) {
13                continue;
14            }
15            
16            int left = i + 1;
17            int right = n - 1;
18            
19            while (left < right) {
20                int total = nums[i] + nums[left] + nums[right];
21                
22                if (total == 0) {
23                    result.push_back({nums[i], nums[left], nums[right]});
24                    
25                    // Skip duplicates for the second element
26                    while (left < right && nums[left] == nums[left + 1]) {
27                        left++;
28                    }
29                    // Skip duplicates for the third element
30                    while (left < right && nums[right] == nums[right - 1]) {
31                        right--;
32                    }
33                    
34                    left++;
35                    right--;
36                } else if (total < 0) {
37                    left++; // Need a larger sum
38                } else {
39                    right--; // Need a smaller sum
40                }
41            }
42        }
43        
44        return result;
45    }
46};

Java Solution for LeetCode 15

java

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> threeSum(int[] nums) {
7        List<List<Integer>> result = new ArrayList<>();
8        // Step 1: Sort the array
9        Arrays.sort(nums);
10        
11        for (int i = 0; i < nums.length - 2; i++) {
12            // Step 3: Skip duplicates for the fixed element
13            if (i > 0 && nums[i] == nums[i - 1]) {
14                continue;
15            }
16            
17            int left = i + 1;
18            int right = nums.length - 1;
19            
20            while (left < right) {
21                int sum = nums[i] + nums[left] + nums[right];
22                
23                if (sum == 0) {
24                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
25                    
26                    // Skip duplicates for the second element
27                    while (left < right && nums[left] == nums[left + 1]) {
28                        left++;
29                    }
30                    // Skip duplicates for the third element
31                    while (left < right && nums[right] == nums[right - 1]) {
32                        right--;
33                    }
34                    
35                    left++;
36                    right--;
37                } else if (sum < 0) {
38                    left++; // Sum too low, move right
39                } else {
40                    right--; // Sum too high, move left
41                }
42            }
43        }
44        
45        return result;
46    }
47}

Python Solution for LeetCode 15

python

1class Solution:
2    def threeSum(self, nums: List[int]) -> List[List[int]]:
3        result = []
4        # Step 1: Sort the array
5        nums.sort()
6        n = len(nums)
7        
8        for i in range(n - 2):
9            # Step 3: Skip duplicates for the fixed element
10            if i > 0 and nums[i] == nums[i - 1]:
11                continue
12            
13            left = i + 1
14            right = n - 1
15            
16            while left < right:
17                total = nums[i] + nums[left] + nums[right]
18                
19                if total == 0:
20                    result.append([nums[i], nums[left], nums[right]])
21                    
22                    # Skip duplicates for the second element
23                    while left < right and nums[left] == nums[left + 1]:
24                        left += 1
25                    # Skip duplicates for the third element
26                    while left < right and nums[right] == nums[right - 1]:
27                        right -= 1
28                        
29                    left += 1
30                    right -= 1
31                elif total < 0:
32                    left += 1
33                else:
34                    right -= 1
35                    
36        return result

3Sum

Core insight

Core Insight for 3Sum

Full breakdown

LeetCode 15: 3Sum Solution & Explanation

Problem Overview

Brute Force Approach for 3Sum

Algorithm Strategy: Two Pointer Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 15

Java Solution for LeetCode 15

Python Solution for LeetCode 15

Practise 3Sum and the problems around it

Related problems

3Sum

Core insight

Core Insight for 3Sum

Full breakdown

LeetCode 15: 3Sum Solution & Explanation

Problem Overview

Brute Force Approach for 3Sum

Algorithm Strategy: Two Pointer Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 15

Java Solution for LeetCode 15

Python Solution for LeetCode 15

Practise 3Sum and the problems around it

Related problems