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:

1. Problem Statement Definition
2. Method 1: Naive approach
   1. Approach
   2. Algorithm
   3. Implementation
   4. Complexity
3. Method 2: Using Python Bisect
   1. Approach
   2. Function-Code
   3. Complexity
4. Method 3: Sorting and Two Pointer Approach
   1. Approach
   2. Algorithm
   3. Implementation
   4. Complexity
5. Comparison of Approaches
6. 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.

Example-1

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]]

Example-2

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 |sum-temp| 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(temp-sum) ){
                       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 bisect-module 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=target-a-b
                    ic=bisect.bisect_left(nums,c,lo=j+1)
                    if j+1<ic<=N-1:
                        diffp=abs(target-a-b-nums[ic-1])
                        diffn=abs(target-a-b-nums[ic])
                        currclosest=a+b+nums[ic-1] 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(currclosest-target)<abs(closest-target):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 two-pointer 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 |sum-temp| is equal to |arr[i] +arr[j] + arr[k] -sum|, store the three elements in an array
    • Else if |sum-temp| 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 |sum-temp| is equal to |arr[i] +arr[j] + arr[k] -sum|, store the three elements in an array
      • Else if |sum-temp| 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.
  • Else, if the sum of elements at two-pointer is equal to given sum then print the triplet and break.

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(temp-sum))){
                    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(temp-sum))){
                    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

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 3-SUM hardness
• It finds many uses in computational geometry

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.