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:

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

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

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

1. Introduction

2. Problem Description

3. Brute Force Approach

4. Two-pointer Approach

5. Conclusion