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

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

    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. 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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: