## Nearest Pair

### March 13, 2018

Today’s exercise is an interview question:

You are given a list of integers and must find the nearest pair that sum to a given target. For instance, given the list (1 5 3 6 4 2), if the target is 7, there are three pairs with the required sum, (1 6), (5 2) and (3 4), but pair (1 6) has two intervening numbers, pair (5 2) has three intervening numbers, and pair (3 4) has only one intervening number, so (3 4) is the nearest pair.

Your task is to write a program to find the nearest pair. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

var a = [1, 5, 3, 6, 4, 2];

var p = [];

var q = [];

for(i=0;i<a.length;i++){

for(j=i+1;j<a.length;j++){

if(a[i] + a[j] === 7){

var k = j – i;

p.push([k]);

q.push([k,[a[i],a[j]]]);

}

This being an interview question, you’d definitely want to ask if you can assume the numbers in the list are unique.

is second iteration necessary ” for(s=0;s<item.length;s++){

A Haskell version.

it can be done in O(N) using hash tables

Here’s a solution in Python.

Output:

Line 13 can be removed from my prior solution, as the defaultdict will return an empty list.

O(n) solution: