CareerCup

Sort the array in O(nlogn), then go over sorted array and find the necessary numbers in O(n). Overall O(nlogn) + O(n) ~ O(nlogn).

Can this be done without sorting the array?

int FindLeastDiff(int a[], int N, int & i, int & j)
{
   i = j = -1;
   int ii = 0, least_diff = -1;

   for (int jj = 1; jj < N; ++jj)
   {
      int diff = abs(a[ii] - a[jj]);

      if (diff < least_diff || least_diff < 0)
      {
         least_diff = diff;
         i = ii;
         j = jj;
      } else
         ii = jj;
   }

   return least_diff;
}

Yes.
There're some O(nlogn) algorithms which can solve the 2D closest points problem. Reducing the problem to 1D gives the answer.

Note that if this problem can be solved under O(nlogn) time, the classical element uniqueness problem can also be solved under O(nlogn) time, which contradicts the known lower bound of that problem.

But, when randomized algorithms and something like hashtable are allowed, it is also possible to solve this in O(n) expected time. google helps if you want to know more.

Also we can use modified version of quicksort's partition operation.
Select the pivot element, then during the partitioning we can get the following:
[ left side of array < pivot ] [ pivot ] [ right side of array > pivot ]
minL = min(left side of array)
minR = min(right side of array)

So the possible elements should be (minL, pivot) or (pivot, minR).
Then recursively perform this for left and right subarrays and get the necessary result.

Time complexity O(nlong).