Finding Three Elements in an Array Whose Sum Is Closest to a Given Number

1. Introduction

In this tutorial, we’ll see how to find three elements in an array such that the sum is closest to a given number.

2. Problem Description

Given a number array $\mathbf {A}$ and a target number $\mathbf {t}$ , we want to find three numbers in $\mathbf {A}$ such that their sum is closest to $\mathbf {t}$ . For example, if the array is $\{-1, 2, 1, -4\}$ and our target number is $1$ , then the closest sum is 2. Also, the 3 numbers that produce the closest sum are $\{-1, 2, 1\}$ .

3. Brute Force Approach

Let’s uppose the number index of the array $A$ starts with $0$ , i.e., $A = \{A[0], A[1], ..., A[n-1]\}$ . We can explore all the possible 3 numbers based on their indexes, and keep a track of the difference between $\mathbf {t}$ and the sum of the 3 numbers:

This algorithm uses three nested loops to go through all possible combinations of 3 numbers in the array $A$ . In each iteration, we calculate the difference between the sum of the three numbers and the target number $t$ . If the difference is less than the minimum difference we have so far, we’ll record the 3 numbers and update the minimum difference.

Since we have three nested loops over the array $A$ , the overall time complexity of this algorithm is $O(n^3)$ , where $n$ is the number of elements in the array $A$ .

4. Two-pointer Approach

We can solve this problem with the two-pointer approach. Since the two-pointer approach works on a sorted array, we first need to sort the array $A$ . To calculate the closest sum of three numbers, we can first fix one number, $\mathbf {A[i]}$ , and then use the two-pointer approach to find the closest sum that contains the fixed number $\mathbf {A[i]}$ :

In this algorithm, we first sort the array in ascending order. Then, we go through each number of $A$ to find the closest sum for this number. For a number $A[i]$ , we construct two pointers: $j=i+1$ and $k=n-1$ . These two pointers indicate the indexes of the other two numbers, i.e. $A[j]$ and $A[k]$ . Then, we use the two-pointer approach to find the closet sum.

In each iteration of the two-pointer approach, we compare the $sum$ of the three numbers $\{A[i], A[j], A[k]\}$ with our target number $t$ . If the $sum$ is less than $t$ , we should increase the pointer $j$ to make the next $sum$ bigger. Otherwise, we can decrease the pointer $k$ to make the next $sum$ smaller. In this way, we can get the $sum$ close to the target number $t$ as much as possible.

In the meantime, we also check the difference between the $sum$ and the target number $t$ . If the difference is less than the minimum difference we have so far, we’ll record the 3 numbers and update the minimum difference.

In this algorithm, we scan the entire array keeping one element fixed. For each element, we use the two-pointer approach to find the closest sum. The two-pointer approach takes $O(n)$ time for a fixed element. Since we have $O(n)$ possible fixed elements, the overall time complexity is $O(n^2)$ . The sorting takes $O(n log n)$ time. Therefore, the total running time is $O(n log n + n^2)$ which still comes down to $O(n^2)$ .

5. Conclusion

In this tutorial, we showed two algorithms to find three elements such that the sum is closest to a given number. The brute force approach takes $O(n^3)$ time to solve the problem. We can also use a two-pointer approach to solve this problem with a better performance of $O(n^2)$ .

Full Archive

About Baeldung

1. Introduction

2. Problem Description

3. Brute Force Approach

4. Two-pointer Approach

5. Conclusion