Programming Praxis

9 Responses to “Nearest Pair”

1. Rutger said

   March 13, 2018 at 1:33 PM

   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])[1])
   
2. Azi said

   March 15, 2018 at 5:23 PM

   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

   March 16, 2018 at 7:58 PM

   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

   March 17, 2018 at 3:25 PM

   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[0]===min){
               console.log(item[1]);
           }
   
5. Globules said

   March 18, 2018 at 4:53 AM

   A Haskell version.

   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. Sochima Biereagu, KodeJuice said

   March 18, 2018 at 5:52 AM

   it can be done in O(N) using hash tables
7. Daniel said

   March 19, 2018 at 1:27 AM

   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

   March 19, 2018 at 1:32 AM

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

   March 20, 2018 at 6:38 PM

   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