Closest 3 Sum problem (Find all triplets close to the given sum)
Get FREE domain for 1st year and build your brand new site
Reading time: 20 minutes  Coding time: 30 minutes
In this article, we have explored an insightful approach/ algorithm to find the 3 elements in an array whose sum is equal to or close to the required answer. This is an extension of the 3 Sum problem where the resulting sum needed not be exact.
Table of contents:
 Problem Statement Definition
 Method 1: Naive approach
 Approach
 Algorithm
 Implementation
 Complexity
 Method 2: Using Python Bisect
 Approach
 FunctionCode
 Complexity
 Method 3: Sorting and Two Pointer Approach
 Approach
 Algorithm
 Implementation
 Complexity
 Comparison of Approaches
 Applications
PROBLEM STATEMENT DEFINITION
Given an array , the sum to be extracted (S) we have to find three elements whose sum is equal to S. If it is not possible then we find three elements whose sum is closest to S.
Example1
Let the array be [7, 12, 3, 1, 2, 6, 5, 8, 6]
Let S = 0
It is possible to find three elements whose sum = 0
Then the output is [[2, 8, 6], [3, 5, 8], [1, 6, 5]]
Example2
Let the array be [1, 2, 3, 9, 6]
Let S = 7
It is not possible to find three elements whose sum = 7. But [1, 2, 3] whose sum = 6 is the closest sum and is the output
There are three methods for solving the closest 3 sum problem
 Method 1: Naive approach
 Method 2: Using Python Bisect
 Method 3: Sorting and Two Pointer Approach
Let us look at all three methods.
Method 1: Naive approach
APPROACH
A simple method is to generate all possible triplets and compare the sum of every triplet with the given value. If it is not found then we return the closest 3 elements.
ALGORITHM
 Given an array of length n and a sum s
 Create three nested loop first loop runs from start to end (loop counter i), second loop runs from i+1 to end (loop counter j) and third loop runs from j+1 to end (loop counter k)
 The counter of these loops represents the index of 3 elements of the triplets.
 Find the sum of ith, jth and kth element and store it in temp variable.
 If temp equals sum, print the triplet and break.
 Else repeat the process and compare new sum with temp. If sumtemp is lesser than arr[i] +arr[j] + arr[k] sum, store the three elements.
 After exiting the loop, print the 3 elements
IMPLEMENTATION
Let us have a look at the C++ program for the problem
#include <bits/stdc++.h>
using namespace std;
void find3Numbers(int A[], int arr_size, int sum)
{
int l, r, count=0, arr[20],temp=0;
for (int i = 0; i < arr_size  2; i++)
{
for (int j = i + 1; j < arr_size  1; j++)
{
for (int k = j + 1; k < arr_size; k++)
{
if (A[i] + A[j] + A[k] == sum)
{
count=0;
cout<<"["<<A[i]<<", "<<A[j]<<", "<<A[k]<<"]"<<endl;
temp = sum;
}
else if ((A[i] + A[j] + A[k]) ==temp) {
arr[count]= A[i];
count++;
arr[count]= A[j];
count++;
arr[count]= A[k];
count++;
temp = A[i] + A[j] + A[k];
}
else{
if (abs(A[i] + A[j] + A[k]sum) < abs(tempsum) ){
count=0;
arr[count]= A[i];
count++;
arr[count]= A[j];
count++;
arr[count]= A[k];
count++;
temp = A[i] + A[j] + A[k];
}
}
}
}
}
for(int i=0;i<count;i+=3){
cout<<"["<<arr[i]<<", "<<arr[i+1]<<", "<<arr[i+2]<<"]"<<endl;
}
cout<<"The sum is: "<<temp;
}
int main()
{
int A[] = { 1, 2, 3, 9, 6 };
int sum = 7;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
OUTPUT
[1, 2, 3]
The sum is: 6
Complexity
 Worst case time complexity:
Î˜(n^3)
 Average case time complexity:
Î˜(n^3)
 Best case time complexity:
Î˜(n^3)
 Space complexity:
Î˜(3*h) (where h is the number of solutions )
Method 2: USING PYTHON BISECT
APPROACH
Sorting the array the efficiency of the algorithm can be improved but performing sort operations after every insertion on a long list may be expensive in terms of time consumed by processor. The bisect module ensures that the list remains automatically sorted after insertion. For this purpose, it uses bisection algorithm.
The bisectmodule has following functions:
bisect_left()
This method locates insertion point for a given element in the list to maintain sorted order. If it is already present in the list, the insertion point will be before (to the left of) any existing entries. The return value can be used as the first parameter to list.insert()
bisect_right()
This method is similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.
bisect.insort_left()
This method insert given value in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x)
bisect.insort_right()
This method insert given value in a in sorted order. This is equivalent to a.insert(bisect.bisect_right(a, x, lo, hi), x)
bisect.insort()
Bothe methods are similar to insort_left(), but inserting given value in the list after any existing entries of same value.
In this approach however, we will only use the bisect_left() function
FUNCTION CODE
class Solution:
def threeSumClosest(self, nums: List[int], target: int) > int:
import bisect
closest=10**8
nums.sort()
N=len(nums)
for i in range(len(nums)2):
for j in range(i+1,len(nums)1):
a,b=nums[i],nums[j]
c=targetab
ic=bisect.bisect_left(nums,c,lo=j+1)
if j+1<ic<=N1:
diffp=abs(targetabnums[ic1])
diffn=abs(targetabnums[ic])
currclosest=a+b+nums[ic1] if diffp<diffn else a+b+nums[ic]
elif ic==j+1:
currclosest=a+b+nums[ic]
else:
currclosest=a+b+nums[1]
if abs(currclosesttarget)<abs(closesttarget):closest=currclosest
return closest
Complexity
 Worst case time complexity:
Î˜(n^2)
 Average case time complexity:
Î˜(n^2)
 Best case time complexity:
Î˜(n^2)
 Space complexity:
Î˜(3*h) (where h is the number of solutions )
Method 3: SORTING AND TWO POINTER APPROACH
APPROACH
Sorting the array the efficiency of the algorithm can be improved. This efficient approach uses the twopointer technique. Traverse the array and fix the first element of the triplet. Now use the Two Pointers algorithm to find if there is a pair whose sum is equal to or closest to x â€“ array[i].
Two pointers algorithm take linear time so it is better than a nested loop. This approach is efficient because, we continually make sure that the sum of the 3 elements is as close as possible to sum with each iteration.
ALGORITHM
 Sort the given array.
 Loop over the array and fix the first element of the possible triplet, arr[i].
 Then fix two pointers, one at i + 1 and the other at n â€“ 1. And look at the sum,
 If the sum is smaller than the required sum, compare temp to sum.
 If sumtemp is equal to arr[i] +arr[j] + arr[k] sum, store the three elements in an array
 Else if sumtemp is lesser than arr[i] +arr[j] + arr[k] sum , then overwrite the previously stored elements with the 3 elements found now
 increment the first pointer.
 Else, If the sum is bigger, Decrease the end pointer to reduce the sum.

 If sumtemp is equal to arr[i] +arr[j] + arr[k] sum, store the three elements in an array
 Else if sumtemp is lesser than arr[i] +arr[j] + arr[k] sum , then overwrite the previously stored elements with the 3 elements found now
 increment the second pointer.
 If sumtemp is equal to arr[i] +arr[j] + arr[k] sum, store the three elements in an array
 Else, if the sum of elements at twopointer is equal to given sum then print the triplet and break.
 If the sum is smaller than the required sum, compare temp to sum.
IMPLEMENTATION
Let us have a look at the C++ program for the problem
#include <bits/stdc++.h>
using namespace std;
void find3Numbers(int A[], int arr_size, int sum)
{
int l, r, count=0, arr[20],temp=0;
sort(A, A + arr_size);
for (int i = 0; i < arr_size  2; i++) {
l = i + 1;
r = arr_size  1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum){
count=0;
cout<<"["<<A[i]<<", "<<A[l]<<", "<<A[r]<<"]"<<endl;
temp = sum;
}
else if (A[i] + A[l] + A[r] < sum){
if (temp!=sum && ( (A[i] + A[l] + A[r]) ==temp) ) {
arr[count]= A[i];
count++;
arr[count]= A[l];
count++;
arr[count]= A[r];
count++;
temp = A[i] + A[l] + A[r];
}
if (temp!=sum && (abs(A[i] + A[l] + A[r]sum) < abs(tempsum))){
count=0;
arr[count]= A[i];
count++;
arr[count]= A[l];
count++;
arr[count]= A[r];
count++;
temp = A[i] + A[l] + A[r];
}
l++;
}
else{
if (temp!=sum && ( (A[i] + A[l] + A[r]) ==temp) ) {
arr[count]= A[i];
count++;
arr[count]= A[l];
count++;
arr[count]= A[r];
count++;
temp = A[i] + A[l] + A[r];
}
if (temp!=sum && (abs(A[i] + A[l] + A[r]sum) < abs(tempsum))){
count=0;
arr[count]= A[i];
count++;
arr[count]= A[l];
count++;
arr[count]= A[r];
count++;
temp = A[i] + A[l] + A[r];
}
r;
}
}
}
for(int i=0;i<count;i+=3){
cout<<"["<<arr[i]<<", "<<arr[i+1]<<", "<<arr[i+2]<<"]"<<endl;
}
cout<<"The sum is: "<<temp;
}
int main()
{
int A[] = { 1, 6, 5, 9, 2};
int sum = 7;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
OUTPUT
[1, 2, 5]
The sum is: 8
Complexity
 Worst case time complexity:
Î˜(n^2)
 Average case time complexity:
Î˜(n^2)
 Best case time complexity:
Î˜(n^2)
 Space complexity:
Î˜(3*h) (where h is the number of solutions )
COMPARISON OF APPROACHES
Complexity  Naive Approach  Python bisect approach  Sorting and two pointer 

TimeComplexity  n^3  n^2  n^2 
SpaceComplexity  3 * h  1  3 * h 
Where h is the number of solutions.
APPLICATIONS
 This problem is the most basic of a class of algorithms called quadratic algorithms
 A variation of this problem is used in various other problems like convolution and 3SUM hardness
 It finds many uses in computational geometry
Question
Why is the two pointer technique efficient in this problem?
With this article at OpenGenus, you must have the complete idea of how to solve the Closest 3 Sum problem (Find all triplets close to the given sum) efficiently.