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.