Finding N closest numbers

Question

Have a 2-dimensional array, like -

a[0] = [ 0 , 4 , 9 ]
a[1] = [ 2 , 6 , 11 ]
a[2] = [ 3 , 8 , 13 ]
a[3] = [ 7 , 12 ]

Need to select one element from each of the sub-array in a way that the resultant set of numbers are closest, that is the difference between the highest number and lowest number in the set is minimum.

The answer to the above will be = [ 9 , 6 , 8 , 7 ].

Have made an algorithm, but don't feel its a good one. What would be a efficient algorithm to do this in terms of time and space complexity?

EDIT - My Algorithm (in python)-

INPUT - Dictionary : table{}
OUTPUT - Dictionary : low_table{}
#
N = len(table)
for word_key in table:
    for init in table[word_key]:
        temp_table = copy.copy(table)
        del temp_table[word_key]
        per_init = copy.copy(init)
        low_table[init]=[]
        for ite in range(N-1):
            min_val = 9999
            for i in temp_table:
                for nums in temp_table[i]:
                    if min_val > abs(init-nums):
                        min_val = abs(init-nums)
                        del_num = i
                        next_num = nums
            low_table[per_init].append(next_num)
            init = (init+next_num)/2
            del temp_table[del_num]
lowest_val = 99
lowest_set = []
for x in low_table:
    low_table[x].append(x)
    low_table[x].sort()
    mini = low_table[x][-1]-low_table[x][0]
    if mini < lowest_val:
        lowest_val = mini
        lowest_set = low_table[x]
print lowest_set

Answer 1

I've got a variant of whiterook's algorithm that I think is simpler (and apart from an initial sort step, it's more clearly O(N)).

Iterate minval through all the values in order. While doing this, we keep the index of the smallest value in each array which are greater than or equal to minval). We also keep the maximum value of the elements at these index in their corresponding arrays.

When we've done considering a particular minval, we can increment the index for all the arrays that contain minval, and update the maxval if necessary.

Here's an implementation. Note that (except for the initial sort) it's O(N) because the inner loop is executed at most once per value in each array.

def minspan(aa):
    allnums = sorted(set(sum(aa, [])))
    ntoi = dict((x, []) for x in allnums)
    for i in xrange(len(aa)):
        for x in aa[i]:
            ntoi[x].append(i)
    indexes = [0] * len(aa)
    maxval = max(a[0] for a in aa)
    best = None
    for minval in allnums:
        if best is None or best[0] > maxval - minval:
            best = maxval - minval, minval, maxval
        for i in ntoi[minval]:
            indexes[i] += 1
            if indexes[i] >= len(aa[i]):
                return [min(x for x in a if x >= best[1]) for a in aa]
            maxval = max(maxval, aa[i][indexes[i]])

aa = [[0,4,9], [2,6,11], [3,8,13], [7,12]]
print minspan(aa)

Answer 2

A wordy Haskell version of the nice algorithm by whiterook6:

import Data.List (minimumBy,sortBy)
import qualified Data.Map as M (fromList,toList,adjust,lookup)

f arrays = g (zip arrays [1..]) [] h [(100,0),(0,0)] where
  n = length arrays
  h = (M.fromList $ zip [1..n] (repeat 0))
  g arrays sequence indexes best
    | any ((==0) . snd) (M.toList indexes) = 
        g (foldr comb [] arrays) (next:sequence) (M.adjust (+1) ind indexes) best
    | otherwise = 
        if null (drop 1 arrays) 
           then best'
           else g (foldr comb [] arrays) 
                  (next:init trimmedSequence) 
                  (foldr (M.adjust (+1)) h (ind : (map snd $ init trimmedSequence))) 
                  best'
   where 
     best' = minimumBy comp [best,trimmedSequence]
     next@(val,ind) = minimum $ map (\(arr,i) -> (head arr,i)) arrays
     comb a@(seq,i) b = if i == ind 
                           then if null (drop 1 seq) 
                                   then b 
                                   else (drop 1 seq,i) : b 
                           else a : b
     comp a b = compare (fst (head a) - fst (last a)) (fst (head b) - fst (last b))
     trimSequence []     _ = []
     trimSequence (x:xs) h
       | any ((==0) . snd) (M.toList h) = 
           case M.lookup (snd x) h of
             Just 0     -> x : trimSequence xs (M.adjust (+1) (snd x) h)
             otherwise  -> trimSequence xs h
       | otherwise                      = []
     trimmedSequence = trimSequence sequence (M.fromList $ zip [1..n] (repeat 0))

Output:

*Main> f [[0,4,9],[2,6,11],[3,8,13],[7,12]]
[(9,1),(8,3),(7,4),(6,2)]

Answer 3

collect all the values to create a single ordered sequence, with each element tagged with the array it came from: 0(0), 2(1), 3(2), 4(0), 6(1), ... 12(3), 13(2)

then create a window across them, starting with the first (0(0)) and ending it at the first position that makes the window span all the arrays (0(0) -> 7(3))

then roll this window by incrementing the start of the window by one, and increment the end of the window until you again have a window that covers all elements.

then roll it again: (2(1), 3(2), 4(0), ... 7(3)), and so forth.

at each step keep track of the the difference between the largest and the smallest. Eventually you find the one with the smallest window. I have the feeling that in the worst case this is O(n^2) but that's just a guess.