Couldn’t come up with an appropriate title ;-)
Got this question from my friend prabhu…
You have an array of numbers a[n]. You will have to construct an array of
numbers b[n], where for every i, b[i] is a[k] such that k is the largest
index < i and a[k] < a[i]. If there is no such element, b[i] is -1.
For example,
A[]={1,4,2,0,9,3,7,3,98}
B[]= {-1,1,1,-1,0,0,3,0,3}
Description:
B[0]=-1, No k exists in this case
B[1]=1, Because k=0 and A[0]=1
B[2]=1, Because k=0 and A[0]=1
B[3]=-1, No A[k] exists which is less than A[3].
B[4]=0,k=4 and A[4]=0
and so on …..
Write an algorithm that does this in O(n) time and O(n) space.
PS: As of now, I too don’t know the answer.. 
March 3, 2008 at 8:27 am
Can we maintain another array of ‘n’ elements in addition to arrays A and B? space used will be 3n which is still O(n).. is this ok?
March 3, 2008 at 10:30 am
If we can maintain another array which stores indexes of elements getting stored in B, we can keep checking B instead of A for finding the largest index such that B[k] < A[i]
min = A[0]; //stores the min element found in the array so far
B[0] = -1;
index[0] = -1; /*for the elements being stored in B, their original indexes in A will be stored in index[n] array */
for ( i = 1; i < n; i++) {
if (A[i] < min) {
B[i] = -1;
index[i] = -1;
min = A[i];
}
else if ( A[i-1] 0; k = index[k] ) {
if (B[k] < A[i] ) {
index[i] = index[k];
B[i] = B[k];
break;
}
}
}
}
March 3, 2008 at 12:28 pm
i didn’t get it.. esp the “else if” part.
can u pls repost ur code?
March 3, 2008 at 2:24 pm
oops! thats a mess.. some of the lines got deleted.. posting again..
min = A[0];
B[0] = -1;
index[0] = -1;
for ( i = 1; i < n; i++) {
if (A[i] < min) {
B[i] = -1;
index[i] = -1;
min = A[i];
}
else if ( A[i-1] 0; k = index[k] ) {
if (B[k] < A[i] ) {
index[i] = index[k];
B[i] = B[k];
break;
}
}
}
}
March 3, 2008 at 2:26 pm
hey there is some problem.. will send the code to naresh to post..
March 3, 2008 at 2:28 pm
trying once more..
min = A[0]; //stores the min element found in the array so far
B[0] = -1;
index[0] = -1; /*for the elements being stored in B, their original indexes in A will be stored in index[n] array */
for ( i = 1; i < n; i++) {
if (A[i] < min) {
B[i] = -1;
index[i] = -1;
min = A[i];
}
else if ( A[i-1] < A[i] ) {
index[i] = i-1;
B[i] = A[i-1];
}
else {
for (k = i-1; k > 0; k = index[k] ) {
if (B[k] < A[i] ) {
index[i] = index[k];
B[i] = B[k];
break;
}
}
}
}
March 20, 2008 at 12:44 pm
I could finally post the code.
the <code> tags are not working..
even after placing the code in <code> tags.. indentation is lost, greater than and lesser than symbols are getting messed up..
finally used , <, > entities to get the code correctly posted. Would like to know if there is a better way..