## Nearest Pair

### March 13, 2018

Our solution first stores each value in the list with its position, then iterates through the input list, looking up the position of the conjugate and saving the pair if it is nearer than the current best solution:

```(define (nearest-pair xs target)
(let ((pos (list)))
(do ((i 0 (+ i 1)) (ys xs (cdr ys))) ((null? ys))
(set! pos (cons (cons (car ys) i) pos)))
(let loop ((i 0) (xs xs) (np #f) (dist #e1e9))
(if (null? xs) np
(let ((j (assoc (- target (car xs)) pos)))
(cond ((not j) (loop (+ i 1) (cdr xs) np dist))
((= i (cdr j)) (loop (+ i 1) (cdr xs) np dist))
((< (abs (- i (cdr j))) dist)
(loop (+ i 1) (cdr xs) (cons (car xs) (car j)) (abs (- i (cdr j)))))
(else (loop (+ i 1) (cdr xs) np dist))))))))```

For no particular reason, we use association lists rather than hash tables to store the `pos` dictionary. There are several important quantities with similar definitions: `(- target (car xs))` is the number that must be added to the current item to make the desired total, `(car j)` is that number, and `(cdr j)` is the position of that number, if it exists in the input list. `(abs (- i (cdr j)))` is the distance between the current item and its conjugate. It’s easy to get those confused; I did while writing this program.

You car run the program at https://ideone.com/5t2k65.

Pages: 1 2

### 9 Responses to “Nearest Pair”

1. Rutger said
```l = [1,5,3,6,4,2]
target = 7

print(min([(d2-d1, (l[d1],l[d2])) for d1 in range(len(l)) for d2 in range(d1+1, len(l)) if l[d1]+l[d2] == target]))
```
2. Azi said

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]]]);
}

``````        }
}
var min = Math.min.apply(Math, p);

q.forEach(function(item,index){

for(s=0;s<item.length;s++){

if(item[s]===min){
console.log(item[s+1]);
}
}
});
``````
3. Scott McMaster said

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

4. harish said

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

``````        if(item[s]===min){
console.log(item[s+1]);
}" , as we know that  there is only two items in inner array so it could be  "  q.forEach(function(item,index){

if(item===min){
console.log(item);
}
``````
5. Globules said

```import Data.Function (on)
import Data.List (minimumBy, tails)

-- A position and value.
data PV a b = PV { pos :: a, val :: b }

-- The nearest pairs of values from xs that sum to s, or nothing if no values
-- have that sum.
nearestPair :: Real a => a -> [a] -> Maybe (a, a)
nearestPair s xs = let ps = filter (sumTo s) \$ pairs \$ mkPVs xs
in case ps of
[] -> Nothing
_  -> Just \$ both val \$ minimumBy (compare `on` dist) ps

-- The equivalent list of PVs starting at position 0.
mkPVs :: [a] -> [PV Int a]
mkPVs = zipWith PV [0..]

-- All pairs of elements from xs, where the first element appears strictly
-- earlier in the argument list than the second.
pairs :: [a] -> [(a, a)]
pairs xs = [(x1, x2) | (x1:xs') <- tails xs, x2 <- xs']

-- True iff the values sum to s.
sumTo :: (Num b, Eq b) => b -> (PV a b, PV a b) -> Bool
sumTo s (x, y) = val x + val y == s

-- The distance, by position, between two PVs.
dist :: Num a => (PV a b, PV a b) -> a
dist (x, y) = abs (pos x - pos y)

-- The result of applying the function to both elements of the tuple.
both :: (a -> b) -> (a, a) -> (b, b)
both f (x, y) = (f x, f y)

main :: IO ()
main = do
print \$ nearestPair 7 [1, 5, 3, 6, 4, 2]
print \$ nearestPair 2 [1, 5, 3, 6, 4, 2]
```
```\$ ./nearpair
Just (3,4)
Nothing
```
6. it can be done in O(N) using hash tables

7. Daniel said

Here’s a solution in Python.

```from collections import defaultdict

# Returns the indices of the nearest pair.
# (returns indices to distinguish duplicated values)
def find_nearest_pair(l, target):
index_lookup = defaultdict(list)
for idx, x in enumerate(l):
index_lookup[x].append(idx)
nearest_pair = None
nearest_distance = None
for idx1, x in enumerate(l):
y = target - x
if y not in index_lookup: continue
for idx2 in index_lookup[y]:
if idx1 >= idx2: continue
distance = idx2 - idx1
if (nearest_pair is None) or (distance < nearest_distance):
nearest_pair = (idx1, idx2)
nearest_distance = distance
return nearest_pair

l = [1, 5, 3, 6, 4, 2]
print 'list: {}'.format(l)
print
for target in range(13):
print 'target: {}'.format(target)
nearest_pair = find_nearest_pair(l, target)
if not nearest_pair: continue
print "  indices: {}".format(nearest_pair)
print "  values:  {}".format(tuple(l[idx] for idx in nearest_pair))
```

Output:

```list: [1, 5, 3, 6, 4, 2]

target: 0
target: 1
target: 2
target: 3
indices: (0, 5)
values:  (1, 2)
target: 4
indices: (0, 2)
values:  (1, 3)
target: 5
indices: (2, 5)
values:  (3, 2)
target: 6
indices: (0, 1)
values:  (1, 5)
target: 7
indices: (2, 4)
values:  (3, 4)
target: 8
indices: (1, 2)
values:  (5, 3)
target: 9
indices: (2, 3)
values:  (3, 6)
target: 10
indices: (3, 4)
values:  (6, 4)
target: 11
indices: (1, 3)
values:  (5, 6)
target: 12
```
8. Daniel said

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

9. Mike said

O(n) solution:

```def nearest_pair(iterable, target):
best_pair = None
best_span = None

seen = {}

for index, right_no in enumerate(iterable):
left_no = target - right_no

if left_no in seen:
span = abs(index - seen[left_no])

if best_span is None or span < best_span:
best_span = span
best_pair = (left_no, right_no)

seen[right_no] = index

return best_pair
```