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 and a target number
, we want to find three numbers in
such that their sum is closest to
. For example, if the array is
and our target number is
, then the closest sum is 2. Also, the 3 numbers that produce the closest sum are
.
3. Brute Force Approach
Let’s uppose the number index of the array starts with
, i.e.,
. We can explore all the possible 3 numbers based on their indexes, and keep a track of the difference between
and the sum of the 3 numbers:
algorithm threeSumClosest(A, n, t):
// INPUT
// A = an integer array with size n
// t = the target number
// OUTPUT
// Three numbers in A whose sum is closest to t
minDiff <- infinity
result <- []
for i <- 0 to n - 3:
for j <- i + 1 to n - 2:
for k <- j + 1 to n - 1:
sum <- A[i] + A[j] + A[k]
diff <- abs(sum - t)
if diff < minDiff:
minDiff <- diff
result <- [A[i], A[j], A[k]]
return result
This algorithm uses three nested loops to go through all possible combinations of 3 numbers in the array . In each iteration, we calculate the difference between the sum of the three numbers and the target number
. 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 , the overall time complexity of this algorithm is
, where
is the number of elements in the array
.
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 . To calculate the closest sum of three numbers, we can first fix one number,
, and then use the two-pointer approach to find the closest sum that contains the fixed number
:
algorithm threeSumClosest(A, n, t):
// INPUT
// A = an integer array with size n
// t = the target number
// OUTPUT
// Three numbers in A whose sum is closest to t
Sort A in ascending order
minDiff <- infinity
result <- []
for i <- 0 to n - 3:
j <- i + 1
k <- n - 1
while j < k:
sum <- A[i] + A[j] + A[k]
diff <- abs(sum - t)
if diff < minDiff:
minDiff <- diff
result <- [A[i], A[j], A[k]]
if sum < t:
j <- j + 1
else:
k <- k - 1
return result
In this algorithm, we first sort the array in ascending order. Then, we go through each number of to find the closest sum for this number. For a number
, we construct two pointers:
and
. These two pointers indicate the indexes of the other two numbers, i.e.
and
. Then, we use the two-pointer approach to find the closet sum.
In each iteration of the two-pointer approach, we compare the of the three numbers
with our target number
. If the
is less than
, we should increase the pointer
to make the next
bigger. Otherwise, we can decrease the pointer
to make the next
smaller. In this way, we can get the
close to the target number
as much as possible.
In the meantime, we also check the difference between the and the target number
. 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 time for a fixed element. Since we have
possible fixed elements, the overall time complexity is
. The sorting takes
time. Therefore, the total running time is
which still comes down to
.
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 time to solve the problem. We can also use a two-pointer approach to solve this problem with a better performance of
.