# Finding the Closest-Sum Pair in a Sorted Array of Integers

There’s something to love about finding an interesting new way to solve a programming problem. Every time I learn about a new algorithm, I can just feel the horizons expanding in my brain.

Weird introduction aside, here’s a straightforward algorithm for solving a pretty common programming challenge. This algorithm certainly won’t blow the pants off of any intermediate- or advanced-level programmers, but I hope beginner programmers will learn a thing or two after reading.

Suppose we were given a sorted array of integers and a number, as a separate integer. We’re asked to find the two integers in the array whose sum comes closest to the separate integer we’re given. How would we go about doing that?

Before tackling the problem in earnest, consider some edge cases:

• What do we do with negative integers in the array?
• What do we do if the separate integer is negative?
• What if we get multiple pairs?

Let’s dive in.

### A “Naive” Solution

If you’ve just started out with programming, you’re most likely suffering from a case of nested-loop-itis, like I did in the past. In other words, your solution (adapted to Ruby) probably looks something like this:

`def closest_sum(int_array, goal_sum)     pair = [int_array[0], int_array[1]]  delta = (goal_sum - (int_array[0] + int_array[1])).abs    int_array[0..-2].each_with_index do |int_1, i|    int_array[i+1..-1].each do |int_2|      if (goal_sum - (int_1 + int_2)).abs < delta        delta = (goal_sum - (int_1 + int_2)).abs        pair = [int_1, int_2]        return pair if delta == 0      end    end  end    return pair  end`

This solution is pretty straightforward. We first initialize a `pair` array with the first two values of `int_array` (assuming, for the sake of the exercise, that `int_array` has a length of at least 2). We also set an initial `delta` value, which is the absolute difference between the given integer `goal_sum` and the sum of the first two values in `int_array`.

After that, we loop through `int_array` and look for any two integers whose `delta` is smaller than the initially-set `delta`, in which case we update `delta` accordingly. We keep iterating until we find the smallest `delta` possible, returning immediately if `delta` is zero, since we’ve found a “perfect” pair in that case. If a `delta` of zero is not possible, we eventually exit the nested loop and return the pair of integers whose sum is as close as possible to the given `goal_sum`.

This solution works, but it certainly isn’t winning any awards in the efficiency category. We do take a few good precautions with the implementation — a number is never compared to itself, and the same pair is never checked twice. Still, we’re looking at something akin to a polynomial time complexity O(n²), which is common for nested-loop scenarios such as these.

Let’s look at a more efficient way to solve the problem.

### A Clever-er Solution

Instead of trying to attack our array of integers from just one direction, what if we were to try and attack it from both sides? Here’s a Ruby implementation that describes what I mean.

`def closest_sum(int_array, goal_sum)`
`left, right = 0, int_array.length - 1  left_final, right_final = left, right  delta = (goal_sum - (int_array[left] + int_array[right])).abs      while left < right    if (goal_sum - (int_array[left] + int_array[right])).abs < delta      delta = (goal_sum - (int_array[left] + int_array[right])).abs      left_final, right_final = left, right      break if delta == 0    elsif int_array[left] + int_array[right] < goal_sum      left += 1    else      right -= 1    end  end    [int_array[left_final], int_array[right_final]]  end`

First, we initialize variables `left` and `right` to be the first and last index of `int_array`. We also initialize variables `left_final` and `right_final` with `left` and `right`, respectively. These “final” variables will be the index locations of the pair of integers that we’re looking for. We initialize `delta` just as we did in the naive solution, but we’re using `left` and `right` as our indices, rather than 0 and 1.

Then, we jump into a while loop that contains an if-elsif-else statement. The first check in our if statement is pretty much identical to the if statement in the naive solution — we try and find an integer pair whose `delta` is smaller than our initial value, and we keep track of the `left` and `right` indices that pass this check.

If this first check isn’t met, then we need to figure out which integers in our array to evaluate next — we need to modify our `left` and `right` indices somehow. Since the array is sorted, we can simply check to see if the current sum of `int_array[left]` and `int_array[right]` is less than the `goal_sum` we’re looking for. If it is, then we increment `left` by one. Doing so helps us “crawl” our way to an integer pair that has a smaller `delta`. Worse case scenario, the `delta` determined from the new pair is the exact same as the `delta` determined from the previous pair.

Similarly, if the sum of `int_array[left]` and `int_array[right]` is greater than or equal to the `goal_sum` we're looking for, then we decrement `right` by one. The reasoning for this is identical to the reasoning for incrementing `left` by one, expect in the opposite direction!

As you can see, our indices get closer and closer to each other through each iteration in the while loop. The loop eventually breaks if one of the following happens:

• We hit a `delta` of zero, which means we found the indices of our “perfect pair”, or
• Our `left` and `right` indices match, meaning we’ve crawled through the entire array.

Regardless, the integer pair whose sum is closest to the `goal_sum` argument is returned, and we’ve accomplished our goal!

This approach is significantly more efficient than our naive approach. Worst case scenario, we iterate through our array just once, resulting in a linear time complexity, or O(n). Definitely preferable over the polynomial time complexity of our nested-loop solution!

### Conclusion

While the second solution is certainly more efficient than the first, neither solution accounts for a multiple-pair solution — they both grab the last pair whose sum is closed to the separate integer. Finding a collection of pairs rather than a single pair isn’t too difficult, however — give it a try and see if you can do it!

It can be hard to see past the nested-loop solution for these types of problems, especially when starting out as a programmer. If you ever come across this problem, or a similar one, ask yourself the following: is there something clever I can do with the indices?

A lot of algorithms can be used and understood if you just approach them with this “what about the index” mentality. In fact, it’s pretty amazing just how far that mentality can take you. Keep it in mind for any future problems you encounter, especially when dealing with arrays and/or searching and sorting algorithms.

Happy coding!

Like what you read? Give Pramod Jacob a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.