3Sum Closest Problem Statement
Given a target number and a list of numbers, find a triplet of numbers from the list such that the sum of that triplet is the closest to the target. Return that sum.
Example One
{
"target": 9,
"numbers": [2, 8, 3, 2]
}
Output:
- 2 + 3 + 2 = 7 is closer to the target than all other triplets.
- 2 + 3 + 3 = 8 is an example of a triplet that we cannot pick because the number 3 appears in the list only once.
Example Two
{
"target": 16,
"numbers": [11, -2, 17, -6, 9]
}
Output:
There are two triplets that sum up to a number that is 2 away from the target: 11 - 6 + 9 = 14 and 11 - 2 + 9 = 18. No triplets sum up to anything closer than that. Therefore, 14 and 18 are correct outputs.
Notes
Constraints:
- -109 <= target <= 109
- -107 <= a number in the list <= 107
- 3 <= size of the given list <= 2*104
Learn what Combination Sum is and how to generate all combinations with sum equal to target problem.
3Sum Closest Code 1: Brute force
/*
Asymptotic complexity in terms of list's size `n`:
* Time: O(n^3).
* Auxiliary space: O(1).
* Total space: O(n).
*/
int find_closest_triplet_sum(int target, vector &numbers) {
int size = numbers.size();
// We'll consider all the possible triplets `(i, j, k)` and try to find the closest triplet sum.
int closest_triplet = numbers[0] + numbers[1] + numbers[2];
for (int i = 0; i + 2 < size; ++i) {
for (int j = i + 1; j + 1 < size; ++j) {
for (int k = j + 1; k < size; ++k) {
int current_triplet_sum = numbers[i] + numbers[j] + numbers[k];
if (abs(target - current_triplet_sum) < abs(target - closest_triplet)) {
closest_triplet = current_triplet_sum;
}
}
}
}
return closest_triplet;
}
Learn how you can find 2 Sum in a Sorted Array problem.
3Sum Closest Code 2: Two Pointers Solution
/*
Asymptotic complexity in terms of list's size `n`:
* Time: O(n^2).
* Auxiliary space: O(n).
* Total space: O(n).
* These assume that std::sort() takes O(n log n) time and O(n) auxiliary space.
*/
int find_closest_triplet_sum(int target, vector &numbers) {
int size = numbers.size();
sort(numbers.begin(), numbers.end());
// For every index `i`, we'll find a pair `(left, right)` of other indices
// from right side of `i` using two-pointers technique.
// Such that for that fixed 'i', sum of the triplet`(numbers[i] + numbers[left] + numbers[right])`
// is as close as possible to the `target`.
int closest_triplet = numbers[0] + numbers[1] + numbers[2];
for (int i = 0; i + 2 < size; ++i) {
int left = i + 1, right = size - 1;
while (left < right) {
int current_triplet_sum = numbers[i] + numbers[left] + numbers[right];
if (current_triplet_sum == target) {
return target;
}
else if (current_triplet_sum > target) {
right--;
}
else {
left++;
}
if (abs(current_triplet_sum - target) < abs(closest_triplet - target)) {
closest_triplet = current_triplet_sum;
}
}
}
return closest_triplet;
}
Learn how you can divide two subsequences with equal sums by solving the Equal Subset Sum Partition Problem.
3Sum Closest Code 3: Binary Search Solution
/*
Asymptotic complexity in terms of list's size `n`:
* Time: O(n^2 * log n).
* Auxiliary space: O(n).
* Total space: O(n).
* These assume that std::sort() takes O(n log n) time and O(n) auxiliary space.
*/
// This function returns the smallest index in the sublist `[numbers[left],...,numbers[right]]`
// whose value is greater than the `target_value`.
int find_best_k(vector &numbers, int left, int right, int target_value) {
int low = left, high = right;
while (low <= high) {
int mid = (low + high) / 2;
if (numbers[mid] <= target_value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
int find_closest_triplet_sum(int target, vector &numbers) {
int size = numbers.size();
sort(numbers.begin(), numbers.end());
// For every pair of indices `(i, j)`, we'll find one more index `k` using binary search
// such that the triplet_sum `(numbers[i] + numbers[j] + numbers[k])`
// is as close as possible to the `target`.
int closest_triplet = numbers[0] + numbers[1] + numbers[2];
for (int i = 0; i + 2 < size; ++i) {
for (int j = i + 1; j + 1 < size; ++j) {
int current_pair_sum = numbers[i] + numbers[j];
int current_triplet_sum;
// Finding the best `k` for the current `(i, j)` using binary search.
// such that the `current_triplet_sum` is just greater than the target.
int k = find_best_k(numbers, j + 1, size - 1, target - current_pair_sum);
// Considering the case when `current_triplet_sum` > `target`.
if (k < size) {
current_triplet_sum = current_pair_sum + numbers[k];
if (abs(target - current_triplet_sum) < abs(target - closest_triplet)) {
closest_triplet = current_triplet_sum;
}
}
// Considering the case when `current_triplet_sum` <= `target`.
if (k - 1 > j) {
k--;
current_triplet_sum = current_pair_sum + numbers[k];
if (abs(target - current_triplet_sum) < abs(target - closest_triplet)) {
closest_triplet = current_triplet_sum;
}
}
}
}
return closest_triplet;
}
We hope that these solutions to the 3Sum Closest problem will help you level up your Two Pointers technique. Companies such as Amazon, Facebook, Microsoft, LinkedIn, Airbnb, Oracle, etc., include 3Sum Closest interview questions in their tech interviews.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE Webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview.
We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE Webinar.
.png)
