Monthly Archives: September 2015

Minimum difference between two elements in array

Given an array, how do we find the minimum difference between any two elements in that array?

For example consider the array [56, 18, 89, 24, 10], the minimum difference is 6 (between 18, and 24).

A straight forward method to find the minimum difference between any two pairs is to iterate through each possible pair and find the minimum difference. But this method takes O(n2) time.

This can be solved in O(n log n) time if we sort the array. Since the closest elements are always adjacent to each other in a sorted array, we can find the minimum difference in one iteration. Here is the C++ code for the same.

Up down array

Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]

For example consider the array A =[6, 9, 36, 24, 42]

The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.

We can solve this problem in a simpler way by sorting the array first. Considering the same example as above

Sorted(A) = [6, 9, 24, 36, 42]

Method1: Start from the second element and swap the elements in pairs

6, 9<-> 24, 36<-> 42 ===>  6, 24, 9, 42, 36

Method2: Interleave the elements of the second half into the first half in reverse order

It becomes 6, 42, 9, 36, 24

Linear search

Given an array of numbers, how do we search for a given number?

For example, given an array [6, 50, 24, 36, 42], the number 36 is present at the index 3 starting with 0. The number 17 is not present any where.

The simplest algorithm to solve this problem is to check each element of the array starting from the first element and search till the target element is found or we reach the end of the array. This most fundamental algorithm is called the linear search.

Here is the pseudo code for the same.

ind = 0 
while ind < length(Array)
   if Array[ind] == target     
      print ind
   ind = ind + 1 
print -1