techInterview Discussion

For an unsorted list of numbers of length n give an O(n) algorithm to find the largest gap between the sequential values in the list.  You can use up to 3*n extra storage spaces.

diff=0;
pos=0;

for(i=1;i<n;i++)
{
if(diff < abs(a[i-1] - a[i]))
{
  diff= abs(a[i-1] - a[i]);
  pos=i;
}
}
printf("Largest Gap: %d and its position %d - %d",diff,pos-1,pos);

If by largest gap you mean this.
Is it what you are looking for? if not then please throw some more light on your problem.
Thanks.

I think the question is:

if the numbers are a_1 , a_2, ..., a_n and sorted they are b_1, b_2, ...b_n. return max |b_(i+1) - b_i|

Trouble is, the algorithm needs to be O(n).

1) Use flash sort to sort the elements in O(n) time using O(m) space where m is the small fraction of the no of elements n

2) Then simply find |b(i+1)-b(i)| by sequential iteration in O(n) time

Note: flashsort sorts the elements in O(n) when elements are uniformly distributed over mean

Find the lowest and highest numbers, and the range R=H-L.  O(n) time.

Choose a bin size B = ceiling(R/N).

Divide the range into bins of size B (there will be N or less bins).

Bin sort the input, keeping track of only the highest and lowest number in each bin.  O(N) time, 2*N or less space.

Find the max gap between the highest number in a bin and the lowest number in the next occupied bin.  O(N) time.

This works as long as there is at least one empty bin.  If there is not at least one empty bin you can do a counting sort in 2*N space, so find the max gap that way.

Skorj,
Why would the number of bins (B) be <= N
For example if I have numbers 4,1000,20,100, the number of bins B = (1000 - 4) / 4 = 249.
This makes your solution not in the O(N).

Opps, I did have an error, but that wasn't it (it was a fencepost error).  Bin SIZE = (R/N) + 1.  So in this example there would be 4 bins of size 250.

The bins would be:
Bin 1 [0004-0253] Low: 4, High: 100
Bin 2 [0254-0503] Empty
Bin 3 [0504-0753] Empty
Bin 4 [0754-1003] Low: 1000, High: 1000

How does this above 3*n storage constraint ?

> How does this above 3*n storage constraint ?

You need less than N bins that each hold two nummbers, plus a few registers.