Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

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:

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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).

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!