sorting - Algorithm: finding closest differences between two elements of array -

you have array, , target. find difference of 2 elements of array. , difference should closest target.

(i.e., find i, j such (array[i]- array[j]) should closest target)

attempt: use order_map (c++ hash-table) store each element of array. o(n). then, output ordered element new array (which sorted increasing number).

next, use 2 pointers.

int mini = int_max, a, b; (int i=0, j = ordered_array.size() -1 ; <j;) {     int tmp = ordered_array[i] - ordered_array[j];     if (abs(tmp - target) < mini) {              mini = abs(tmp - target);               = i;              b = j;        }     if (tmp == target) return {i,j};      else if (tmp > target) j --;      else ++;  } return {a,b}; 

question:

is algorithm still runs @ o(n)?

if array sorted, there o(n) algorithm: let 2 pointers swipe through array, whenever difference between pointed @ elements smaller target increase upper one, whenever larger target increase lower one. while doing so, keep track of best result found far.

when reach end of array overall best result has been found.

it easy see o(n). both pointers move upwards, in each step move 1 pointer , array has n elements. after @ 2n steps halt.

as mentioned in comments, if need sort array first, need o(n log n) effort sorting (unless can use radix sort or counting sort).