Wednesday, July 14, 2010

Min difference in an array of integers

Given an array of integers A, find the two numbers a, b in A such that a-b is minimal.

1 comment:

  1. 1) Sort the array using something like QuickSort or Divide and Conquer [ O(nlgn) running time ]

    2) Walk thru' the array computing difference between two consecutive integers holding the minimum and the index [ O(n) running time].

    So effective running time is O(n lg n)