3 Sum Solution In C++/Java/Python/JS
Problem Description
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.
Examples:
Input : nums = [-1, 0, 1, 2, -1]
Output : [[-1, -1, 2], [-1, 0, 1]]
Explanation:
- First Triplet : nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0The first triplet is [-1, 0, 1]. This adds up to zero, so it's a valid triplet.
- Second Triplet : nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0The second triplet is [-1, -1, 2]. This also sums up to zero, so it’s another valid triplet.
- No Duplicate Triplets:We only count distinct triplets. If we encounter the same set of numbers in a different order (like [-1, 0, 1] and [0, -1, 1]), they would be considered duplicates, and we do not include them in the result.
Thus, the distinct triplets in the array are [-1, -1, 2] and [-1, 0, 1].
Input : nums = [0, 1, 1]
Output : []
Explanation : The only possible triplet does not sum up to 0.
Constraints:
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
The problem can be approached using a simple yet efficient method. We need to find three numbers in the array that sum up to zero. Unlike the "two-sum" problem, where we look for a single pair of numbers, here, we must extend our logic to handle triplets while ensuring we avoid duplicate results.
Brute Force Approach
Intuition
The brute force approach is straightforward: we need to find sets of three numbers from the array that sum up to zero. To achieve this, we check every possible combination of three numbers by using three nested loops. The first loop picks the first number, the second loop picks the second number, and the third loop picks the third number. For each set of three numbers, we check if their sum equals zero.
By using three loops, we ensure that every potential combination is checked. This guarantees that no valid triplet is missed, as we are exhaustively going through the entire array to find all possible triplets that add up to zero. However, this approach may involve a lot of redundant checks, especially when the same triplet is encountered multiple times.
To eliminate duplicate triplets, we store the valid triplets in a set. A set is a special data structure that only keeps unique elements. If we try to add the same triplet again, the set will automatically ignore it, ensuring that only distinct triplets are stored and returned.
What is Set?
A set is a collection in programming that automatically enforces uniqueness. Unlike arrays or lists, where duplicates can exist, a set ensures that each element appears only once. This is particularly useful in scenarios where you need to eliminate repeated values, such as ensuring all triplets are unique in this problem.
Approach
Step 1: Initialize an empty set to store unique triplets
First, we create an empty set to store the unique triplets that we find. The reason we use a set is that it automatically handles duplicates, ensuring that no triplet is stored more than once.
Step 2: Loop through the array to pick the first number
We start by looping through the array, picking the first number at each position i. This number will be the first element of the triplet. The loop will run from the first to the last element, and for each element nums[i], we will attempt to find two other numbers that sum with it to zero.
Step 3: Loop through the remaining numbers to pick the second number
Once we’ve selected the first number at position i, we move to the second loop, which picks the second number. This second number must come after the first one, so we start the second loop from j = i + 1. For each second number at position j, we will look for a third number that will complete the triplet.
Step 4: Loop through the remaining numbers to pick the third number
Next, for each pair of the first two numbers (at positions i and j), we move to the third loop to pick the third number. This third number must come after the second, so we start the third loop from k = j + 1. For each value of k, we now have a triplet of numbers (nums[i], nums[j], nums[k]).
Step 5: Check if the sum of the triplet is zero
At this point, we have three numbers: nums[i], nums[j], and nums[k]. We now check if their sum is zero. If the sum equals zero, this means we’ve found a valid triplet.
Step 6: Add the triplet to the result set
If the sum is zero, we sort the triplet in ascending order and add it to our result set. Sorting is necessary to ensure that triplets with the same numbers but in different orders are treated as the same.
Step 7: Convert the set to a list and return the result
Finally, once all possible combinations of triplets have been checked, we convert the set result into a list. We then return this list as the result.
3Sum Dry Run - BruteForce
Input : nums = [-1, 0, 1, 2, -1]
Step 1 - Outer Loop (i = 0):
The outer loop runs with i = 0 to 4, picking the first number nums[i] each time.
i = 0 (first element = -1):
- We pick nums[i] = -1.
Step 2 - Inner Loop (j = 1 to 4):
The inner loop runs for j from i + 1 to 4 (i.e., from j = 1 to j = 4).
j = 1 (second element = 0):
- We pick nums[j] = 0.
Step 3 - Inner-Inner Loop (k = 2 to 4):
Now, we check for a third number nums[k] by looping k from j + 1 to 4 (i.e., k = 2 to k = 4).
k = 2 (third element = 1):
- We check nums[i] + nums[j] + nums[k] = -1 + 0 + 1 = 0.
- The sum is zero, so we have found a valid triplet: [-1, 0, 1].
- We sort and add the triplet to the set: result.add(tuple(sorted([-1, 0, 1]))), so result = {(-1, 0, 1)}.
k = 3 (third element = 2):
- We check nums[i] + nums[j] + nums[k] = -1 + 0 + 2 = 1.
- The sum is not zero, so we skip this combination.
k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = -1 + 0 + (-1) = -2.
- The sum is not zero, so we skip this combination.
j = 2 (second element = 1):
- We pick nums[j] = 1.
k = 3 (third element = 2):
- We check nums[i] + nums[j] + nums[k] = -1 + 1 + 2 = 2.
- The sum is not zero, so we skip this combination.
k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = -1 + 1 + (-1) = -1.
- The sum is not zero, so we skip this combination.
j = 3 (second element = 2):
- We pick nums[j] = 2.
k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = -1 + 2 + (-1) = 0.
- The sum is zero, so we have found a valid triplet: [-1, -1, 2].
- We sort and add the triplet to the set: result.add(tuple(sorted([-1, -1, 2]))), so result = {(-1, 0, 1), (-1, -1, 2)}.
Step 1 - Outer Loop (i = 1):
i = 1 (first element = 0):
- We pick nums[i] = 0.
Step 2 - Inner Loop (j = 2 to 4):
The inner loop runs for j from i + 1 = 2 to 4.
j = 2 (second element = 1):
- We pick nums[j] = 1.
Step 3 - Inner-Inner Loop (k = 3 to 4):
k = 3 (third element = 2):
- We check nums[i] + nums[j] + nums[k] = 0 + 1 + 2 = 3.
- The sum is not zero, so we skip this combination.
k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = 0 + 1 + (-1) = 0.
- The sum is zero, but [-1, 0, 1] is already in the result set, so we don’t add it again.
j = 3 (second element = 2):
- We pick nums[j] = 2.
k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = 0 + 2 + (-1) = 1.
- The sum is not zero, so we skip this combination.
Step 1 - Outer Loop (i = 2):
- i = 2 (first element = 1):
- We pick nums[i] = 1.
Step 2 - Inner Loop (j = 3 to 4):
The inner loop runs for j from i + 1 = 3 to 4.
- j = 3 (second element = 2):
- We pick nums[j] = 2.
Step 3 - Inner-Inner Loop (k = 4):
- k = 4 (third element = -1):
- We check nums[i] + nums[j] + nums[k] = 1 + 2 + (-1) = 2.
- The sum is not zero, so we skip this combination.
Step 1 - Outer Loop (i = 3):
- i = 3 (first element = 2):
- We pick nums[i] = 2.
Step 2 - Inner Loop (j = 4):
The inner loop runs for j from i + 1 = 4 to 4.
Step 1 - Outer Loop (i = 4):
- i = 4 (first element = -1):
- We pick nums[i] = -1.
Final Result:
After completing the loops, we have found two unique triplets in the set: (-1, 0, 1) and (-1, -1, 2).
3Sum - Code for All Languages - BruteForce
C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> result;
int n = nums.size();
// Sort the array first
sort(nums.begin(), nums.end());
// Loop through the array to pick the first number
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicate elements
int left = i + 1, right = n - 1;
// Use two pointers to find the other two numbers
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.insert({nums[i], nums[left], nums[right]});
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return vector<vector<int>>(result.begin(), result.end());
}
};
3Sum Code in Java - BruteForce
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums.length < 3) return result;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}3Sum Code in Python - BruteForce
class Solution:
def threeSum(self, nums):
# Sort the array first
nums.sort()
result = []
# Loop through the array to pick the first number
for i in range(len(nums) - 2):
# Skip the same elements to avoid duplicates for the first number
if i > 0 and nums[i] == nums[i - 1]:
continue
# Use two pointers for the other two numbers
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
# We found a valid triplet
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
# Skip duplicates for the second and third numbers
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < 0:
left += 1 # Move the left pointer to the right
else:
right -= 1 # Move the right pointer to the left
return result
3Sum Code in JavaScript - BruteForce
function threeSum(nums) {
// Set to store unique triplets
let result = new Set();
let n = nums.length;
// Loop through the array to pick the first number
for (let i = 0; i < n - 2; i++) {
// Loop to pick the second number
for (let j = i + 1; j < n - 1; j++) {
// Loop to pick the third number
for (let k = j + 1; k < n; k++) {
// Check if the sum of the triplet is zero
if (nums[i] + nums[j] + nums[k] === 0) {
// Sort the triplet and convert it to a string for uniqueness
let triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
// Add the triplet to the set
result.add(JSON.stringify(triplet));
}
}
}
}
// Convert the set back to an array of arrays
return Array.from(result).map(JSON.parse);
}Time Complexity : O(N^3 log N)
- Outer loop: The outer loop runs N times, where N is the length of the array. This loop iterates through each element in the array one by one.
Inner loop: For each element in the outer loop, the inner loop runs through the remaining elements in the array. In the worst case, for the first element, the inner loop runs N-1 times, for the second element it runs N-2 times, and so on. This gives us a total of O(N^2) iterations for the two loops combined.
Triplet generation and set insertion: For each pair of elements generated by the outer and inner loops, we find the third element needed to form a triplet that sums to zero. In the worst case, there are O(N^3) possible triplets in the array.
- Set operations: We then try to insert each found triplet into a set. Sets are implemented in such a way that they check if an element already exists before adding it. This check and insertion operation takes O(log M) time, where M is the number of elements in the set. In the worst case, there can be up to O(N^3) unique triplets, so each insertion will take O(log N^3) time, which simplifies to O(log N).
Total Complexity:
- The outer loop runs O(N) times.
- The inner loop runs O(N^2) times in total.
- For each pair, we perform an O(log N) operation (insertion into the set).
- Therefore, the total time complexity becomes O(N^3 log N).
Space Complexity : O(N^3)
Auxiliary Space Complexity
Set (result) for storing unique triplets:
Each triplet consists of 3 numbers, and in the worst case, there can be O(N³) unique triplets.
Thus, the auxiliary space complexity is O(N³).
Total Space Complexity (Including input storage)
The input array nums takes O(N) space.
Adding the auxiliary space O(N³), the total space complexity remains O(N³), since O(N³) dominates O(N).
Instead of checking all triplets with a brute force approach, we can optimize by tracking numbers we've seen. This helps us find the required triplets more efficiently without redundant checks.
Optimal Approach - Hashmap
Intuition
The intuition behind using a hashmap comes from the observation that once we've picked two elements, we can directly check if the third element (the complement) exists. For example, in the triplet nums[i] + nums[j] + nums[k] = 0, after selecting nums[i] and nums[j], we only need to check if nums[k] equals -(nums[i] + nums[j]). Instead of searching for this complement in a third loop, we store the elements we've already processed in a hashmap. As we iterate through the array, we check if the complement for the current pair is already in the hashmap.
The hashmap helps manage duplicates efficiently. As we process the elements, the hashmap keeps track of the values we've already encountered. This allows us to skip checking the same values again and ensures that we only count unique triplets. We might count duplicate triplets without this feature, reducing the algorithm's efficiency.
By utilizing the hashmap to store values and check for complements, we reduce the need for a third loop. Instead of checking all possible triplets, we only need to check pairs of numbers, cutting the time complexity from O(N^3) to O(N^2). This makes the solution more scalable and faster, especially for large datasets.
what is a hashmap ?
A hashmap (also known as a hash table) is a data structure that stores data in key-value pairs. Each key is unique, and values are accessed using the key. The hashmap uses a hash function to map the keys to indices in an underlying array, which allows for very fast retrieval, insertion, and deletion operations—typically in constant time, O(1). This makes hashmaps extremely efficient for tasks where you need to quickly look up values based on a key.
What exactly does the hashmap do in this case?
The hashmap stores the elements we've already processed, and for each new pair (nums[i], nums[j]), we check if the complement -(nums[i] + nums[j]) exists in the hashmap. If it does, we've found a valid triplet.
Implementation
Step 1: Sort the Input Array
We begin by sorting the array. Sorting the array serves two key purposes:
- Avoiding Duplicates: Sorting helps us easily skip duplicate elements in the first iteration. If nums[i] is the same as nums[i-1], we can skip this value to avoid counting duplicate triplets. By sorting, identical values are grouped together, making it simple to skip duplicates.
- Optimizing Pair Search: Sorting ensures that the elements are processed in a consistent order. This allows us to check pairs efficiently, ensuring that we don’t check unnecessary pairs and helps improve performance when looking for complements using the hashmap.
Step 2: Initialize the Result List
We initialize a list called the result to store all the valid triplets we find during the iteration. This will be the final output.
Step 3: Iterate Through the Array
We start by iterating through the array with the first element, i, and treating it as the first number in the triplet. We will check this element against pairs of other numbers in the array. Since we are looking for unique triplets, we skip any duplicate values for i to avoid counting the same triplet multiple times.
Step 4: Use a Hashmap to Track Complements
For each element nums[i], we need to find pairs in the remaining part of the array that sum to -nums[i]. We use a hashmap (seen) to store the elements we encounter as we iterate through the array. For each new element nums[j], we calculate the complement complement = -nums[i] - nums[j] and check if this complement exists in the seen hashmap.
If the complement exists in the hashmap, we have found a valid triplet: [nums[i], nums[j], complement].
Step 5: Return the Result
After we finish iterating through the array, the result list will contain all the unique triplets that sum to zero. We return this list as the final answer.
Let us understand this with a video,
3 Sum-Optimal-Hashmap-Approach
3Sum Dry Run - Optimised (Hashmap)
Input : nums = [-1, 0, 1, 2, -1]
sort the input array , we get: nums = [-1, -1, 0, 1, 2]
We now iterate over the array with index i, treating nums[i] as the first element of the triplet. We want to find two numbers that sum to -nums[i].
First iteration (i = 0):
- nums[i] = -1
- We want to find two numbers that sum to 1 (-nums[i] = 1).
We initialize an empty hashmap seen to track numbers we’ve encountered so far as we iterate through the rest of the array.
Inner loop (j = 1):
- nums[j] = -1
- The complement is 1 - (-1) = 2. We check if 2 is in the seen hashmap. It’s not, so we add -1 (value of nums[j]) to the hashmap. seen = {-1: 1}
Inner loop (j = 2):
- nums[j] = 0
- The complement is 1 - 0 = 1. We check if 1 is in the seen hashmap. It’s not, so we add 0 (value of nums[j]) to the hashmap. seen = {-1: 1, 0: 2}
Inner loop (j = 3):
- nums[j] = 1
- The complement is 1 - 1 = 0. We check if 0 is in the seen hashmap. It is, so we found a valid triplet: [-1, 0, 1]. We add it to the result list. result = [[-1, 0, 1]]
Inner loop (j = 4):
- nums[j] = 2
- The complement is 1 - 2 = -1. We check if -1 is in the seen hashmap. It is, so we found a valid triplet: [-1, -1, 2]. We add it to the result list. result = [[-1, 0, 1], [-1, -1, 2]]
At this point, the first iteration ends and we move on to the next element.
Second iteration (i = 1):
- nums[i] = -1
- Since nums[i] == nums[i - 1], we skip this element to avoid checking the same triplet again.
Third iteration (i = 2):
- nums[i] = 0
- We want to find two numbers that sum to 0 (-nums[i] = 0).
We initialize an empty hashmap again.
Inner loop (j = 3):
- nums[j] = 1
- The complement is 0 - 1 = -1. We check if -1 is in the seen hashmap. It’s not, so we add 1 to the hashmap. seen = {1: 3}
Inner loop (j = 4):
- nums[j] = 2
- The complement is 0 - 2 = -2. We check if -2 is in the seen hashmap. It’s not, so we add 2 to the hashmap. seen = {1: 3, 2: 4}
At this point, the second iteration ends.
Fourth iteration (i = 3):
- nums[i] = 1
- Since nums[i] == nums[i - 1], we skip this element to avoid checking the same triplet again.
Fifth iteration (i = 4):
- nums[i] = 2
- Since nums[i] == nums[i - 1], we skip this element to avoid checking the same triplet again.
At the end of the iterations, the result list contains the following unique triplets: result = [[-1, 0, 1], [-1, -1, 2]]
3Sum - Code for All Languages - Optimised (Hashmap)
C++
class Solution {
public:
// Function to find unique triplets that sum to zero
vector<vector<int>> threeSum(vector<int>& nums) {
// Step 1: Sort the array
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int n = nums.size();
// Loop through the array to pick the first number
for (int i = 0; i < n - 2; i++) {
// Skip duplicate elements
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Hashset to track complements
unordered_set<int> seen;
// Loop to pick the second number
for (int j = i + 1; j < n; j++) {
// Calculate the complement
int complement = -nums[i] - nums[j];
// If complement is found in the set, add the triplet to result
if (seen.count(complement)) {
// Add the triplet
result.push_back({nums[i], nums[j], complement});
// Skip duplicate pairs
while (j + 1 < n && nums[j] == nums[j + 1]) j++;
}
// Insert the second number into the set
seen.insert(nums[j]);
}
}
// Return the result containing unique triplets
return result;
}
};
3Sum code in Java - Optimised (Hashmap)
public class Solution {
// Function to find unique triplets that sum to zero
public List<List<Integer>> threeSum(int[] nums) {
// Step 1: Sort the array
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// Loop through the array to pick the first number
for (int i = 0; i < n - 2; i++) {
// Skip duplicates
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Hashset to track complements
Set<Integer> seen = new HashSet<>();
// Loop to pick the second number
for (int j = i + 1; j < n; j++) {
// Calculate the complement
int complement = -nums[i] - nums[j];
// If complement is found in the set, add the triplet to result
if (seen.contains(complement)) {
result.add(Arrays.asList(nums[i], nums[j], complement));
// Skip duplicate pairs
while (j + 1 < n && nums[j] == nums[j + 1]) j++;
}
// Add the second number to the set
seen.add(nums[j]);
}
}
// Return the result containing unique triplets
return result;
}3Sum Code in Python - Optimised (Hashmap)
class Solution:
def threeSum(self, nums):
# Step 1: Sort the array
nums.sort()
# List to store the unique triplets
result = []
# Length of the input array
n = len(nums)
# Loop through the array to pick the first number
for i in range(n - 2):
# Skip duplicates for the first number
if i > 0 and nums[i] == nums[i - 1]:
continue
# Hashset to track complements of the second number
seen = set()
# Loop through the array to pick the second number
for j in range(i + 1, n):
# Calculate the complement to complete the triplet
complement = -nums[i] - nums[j]
# If complement is found in the set, we have a valid triplet
if complement in seen:
result.append([nums[i], nums[j], complement]) # Add the triplet
# Skip duplicate pairs for the second number
while j + 1 < n and nums[j] == nums[j + 1]:
j += 1
# Add the second number to the set for complement lookup
seen.add(nums[j])
# Return the list of unique triplets
return result
3Sum Code in JavaScript - Optimised (Hashmap)
function threeSum(nums) {
// Step 1: Sort the array
nums.sort((a, b) => a - b);
// Initialize the result array to store unique triplets
let result = [];
// Length of the input array
let n = nums.length;
// Loop through the array to pick the first number
for (let i = 0; i < n - 2; i++) {
// Skip duplicates for the first number
if (i > 0 && nums[i] === nums[i - 1]) continue;
// Hashset to track complements for the second number
let seen = new Set();
// Loop through the array to pick the second number
for (let j = i + 1; j < n; j++) {
// Calculate the complement to complete the triplet
let complement = -nums[i] - nums[j];
// If complement is found in the set, we have a valid triplet
if (seen.has(complement)) {
result.push([nums[i], nums[j], complement]); // Add the triplet
// Skip duplicate pairs for the second number
while (j + 1 < n && nums[j] === nums[j + 1]) j++;
}
// Add the second number to the set for complement lookup
seen.add(nums[j]);
}
}
// Return the list of unique triplets
return result;
}
Time Complexity : O(N^2)
Sorting the Array: Sorting the array takes O(N log N) time, where N is the number of elements.
Iterating through the Array: We iterate through the array once, from i = 0 to i = N-1, which takes O(N) time.
Inner Loop (Checking Pairs): For each i, we iterate over the remaining elements from j = i + 1 to j = N-1. This iteration has a time complexity of O(N).
Hashmap Operations: Checking if the complement exists in the hashmap and inserting new values both take O(1) time on average due to constant-time operations for hashmaps.
Overall Time Complexity:
- Sorting the array takes O(N log N), and iterating and checking pairs takes O(N^2).
- Therefore, the overall time complexity is O(n^2).
Space Complexity : O(n^2)
Auxiliary Space Complexity (Extra space used apart from input storage)
- Sorting the array (sort(nums.begin(), nums.end())): Sorting is typically O(1) extra space for in-place sorting, the worst case is O(n) extra space.
- result vector storing triplets: The maximum number of unique triplets is O(n²), leading to O(n²) space usage in the worst case.
Auxiliary Space Complexity: O(n²)
Total Space Complexity (Including input storage)
- The input array nums itself takes O(n) space.
- Adding auxiliary space, the total space complexity is: O(n)+O(n^2 )=O(n^2)
Optimal Approach - Two Pointer
Intuition
The intuition behind using the two-pointer approach comes from the observation that once we've picked one element, we can efficiently search for the other two that sum to zero using a sorted array. For example, in the triplet nums[i] + nums[low] + nums[high] = 0, after selecting nums[i], we only need to find two numbers that sum to -nums[i]. Instead of searching for these elements with a third nested loop, we use two pointers—one starting from the left (`ow) and the other from the right (high). As we iterate, we adjust these pointers based on whether their sum is too small or too large. This eliminates the need for an extra loop and reduces the complexity significantly.
Sorting the array helps manage duplicates efficiently. As we iterate, we skip over repeated elements to ensure that we only count unique triplets. This prevents unnecessary computations and ensures that our final list does not contain duplicate results. Without this step, we might include the same triplet multiple times, making the algorithm less efficient. Additionally, inside the two-pointer loop, we further avoid duplicate pairs by moving the pointers past repeated values, ensuring that each unique triplet is considered only once.
By utilizing sorting and the two-pointer technique, we reduce the need for a third nested loop. Instead of checking all possible triplets in O(N³), we only need to iterate through the array once (O(N)) while using a two-pointer search (O(N)), resulting in an overall time complexity of O(N²). This makes the solution much more scalable and efficient, especially for large datasets.
Implementation
Step 1: Sort the Input Array
We begin by sorting the input array. Sorting serves two important purposes:
- Avoiding Duplicates: Since identical values are grouped together, we can easily skip duplicate elements when selecting the first number (nums[i]). This ensures that we don’t count the same triplet multiple times.
- Optimizing Two-Pointer Search: Sorting allows us to use the two-pointer approach efficiently. When searching for two numbers that sum to -nums[i], we can move the pointers (low and high) based on whether the sum is too small or too large.
Step 2: Initialize the Result List
We initialize an empty list called output, which will store all valid triplets. This list ensures that only unique triplets are included in the final result.
Step 3: Iterate Through the Array
We iterate through the sorted array and treat each element nums[i] as the first number in the triplet.
- If nums[i] is the same as nums[i-1], we skip it to avoid duplicate triplets.
- We then initialize two pointers: low (starting from i+1) and high (starting from the last index), which will be used to find the remaining two numbers that sum to -nums[i].
Step 4: Use Two-Pointer Technique to Find Pairs
Instead of using a third loop, we use the two-pointer approach to find two numbers (nums[low] and nums[high]) such that their sum equals -nums[i]:
- If the sum of nums[i] + nums[low] + nums[high] is less than zero, we increase low to get a larger sum.
- If the sum is greater than zero, we decrease high to reduce the sum.
- If we find a valid triplet, we add it to output and move both pointers past any duplicate values to ensure unique triplets.
Step 5: Return the Result
Once all elements have been processed, output contains all unique triplets that sum to zero. We return this list as the final answer.
Let us understand this with a video,
3 Sum-Optimal-Pointer-Approach
3Sum Dry Run - Optimised (Two Pointer)
Sort the array: nums = [-1, -1, 0, 1, 2]
Initialize `output = []
First iteration (i = 0, nums[i] = -1):
- low = 1, high = 4
- nums[i] + nums[low] + nums[high] = -1 + (-1) + 2 = 0, so add [-1, -1, 2] to output
- Move low to 2 and high to 3
- nums[i] + nums[low] + nums[high] = -1 + 0 + 1 = 0, so add [-1, 0, 1] to output
- Move low to 3 and high to 2 (loop ends)
Second iteration (i = 1, nums[i] = -1):
- Since nums[i] == nums[i-1], skip this iteration to avoid duplicates
Third iteration (i = 2, nums[i] = 0):
- low = 3, high = 4
- nums[i] + nums[low] + nums[high] = 0 + 1 + 2 = 3, greater than 0, so move high to 3 (loop ends)
Final output = [[-1, -1, 2], [-1, 0, 1]]
3Sum - Code for All Languages Optimised (Two Pointer)
3Sum problem solution in C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> output;
for(int i = 0; i < n - 1; i++) {
int low = i + 1, high = n - 1;
while(low < high) {
int sum = nums[i] + nums[low] + nums[high];
if(sum < 0) {
low++;
}
else if(sum > 0) {
high--;
}
else {
output.push_back({nums[i], nums[low], nums[high]});
int temp1 = nums[low], temp2 = nums[high];
while(low < high && nums[low] == temp1) low++;
while(low < high && nums[high] == temp2) high--;
}
}
while(i + 1 < n && nums[i] == nums[i + 1]) i++;
}
return output;
}
};3Sum problem solution in Java - Optimised (Two Pointer)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> output;
for(int i = 0; i < n - 1; i++) {
int low = i + 1, high = n - 1;
while(low < high) {
int sum = nums[i] + nums[low] + nums[high];
if(sum < 0) {
low++;
}
else if(sum > 0) {
high--;
}
else {
output.push_back({nums[i], nums[low], nums[high]});
int temp1 = nums[low], temp2 = nums[high];
while(low < high && nums[low] == temp1) low++;
while(low < high && nums[high] == temp2) high--;
}
}
while(i + 1 < n && nums[i] == nums[i + 1]) i++;
}
return output;
}
};3Sum problem solution in Python - Optimised (Two Pointer)
class Solution:
def threeSum(self, nums):
nums.sort()
output = []
n = len(nums)
for i in range(n - 1):
low, high = i + 1, n - 1
while low < high:
total = nums[i] + nums[low] + nums[high]
if total < 0:
low += 1
elif total > 0:
high -= 1
else:
output.append([nums[i], nums[low], nums[high]])
temp1, temp2 = nums[low], nums[high]
while low < high and nums[low] == temp1:
low += 1
while low < high and nums[high] == temp2:
high -= 1
while i + 1 < n and nums[i] == nums[i + 1]:
i += 1
return output
3Sum problem solution in JavaScript - Optimised (Two Pointer)
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
let output = [];
let n = nums.length;
for(let i = 0; i < n - 1; i++) {
let low = i + 1, high = n - 1;
while(low < high) {
let sum = nums[i] + nums[low] + nums[high];
if(sum < 0) {
low++;
}
else if(sum > 0) {
high--;
}
else {
output.push([nums[i], nums[low], nums[high]]);
let temp1 = nums[low], temp2 = nums[high];
while(low < high && nums[low] === temp1) low++;
while(low < high && nums[high] === temp2) high--;
}
}
while(i + 1 < n && nums[i] === nums[i + 1]) i++;
}
return output;
};Time Complexity : O(N^2)
Sorting the array takes O(n log n) time.
We use a loop to iterate through the array, and for each element nums[i], we use the two-pointer technique (low and high). The inner while loop iterates through the remaining array elements in O(n), leading to O(n^2) iterations in total.
Thus, the overall time complexity is O(n²), dominated by the two-pointer search inside the loop.
Space Complexity : O(1)
Auxiliary Space Complexity : O(1)
The two-pointer approach only uses a few integer variables (low, high, tempIndex1, tempIndex2), which take constant space O(1).
Total Space Complexity : O(n²)
The input array takes O(n) space.
The output list can take up to O(n²) space in the worst case (when all triplets are unique).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to the target. Return the sum of the three integers.
Given an array nums of nn integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 ≤ a,b,c,d < n
a,b,c and d are distinct indices
nums[a] + nums[b] + nums[c] + nums[d] = target