Given an array A,compute B s.t B[i] stores the nea

Question

Given an array A[1..n], we want to compute another array B[1..n] such that B[i] stores the nearest element to the left of A[i] which is smaller than A[i]. Time complexity should be O(n).

(For i>1,If there are no such smaller elements to the left, then B[i] simply contains A[i], and B[1]=A[1].)

Example :

input : 6,9,12,17,11
output:6,6, 9, 12, 9

I was thinking for implementing a stack,
put A[1] in B[1], then push to stack.
for filling B[i],compare A[i] with elements of stack and pop till you get smaller element.
finally push A[i] to stack.

Is above approach correct, and is there a cheaper solution?

Answer 1

Your stack approach is correct. It works because if you pop an element bigger than A[i], that element will never be needed for any elements following A[i], because you can just use A[i] instead.

Each element is only accessed twice, so this is O(n).

Answer 2

B[1]=A[1]
push(B[1])
for i=2 to n do
{
    while(A[i] > stack_top ANS stack_top!=NULL)
       pop()
    if(stack_top=NULL)
        B[i]=A[i]
    else
        B[i]=stack_top
    push(A[i])
}

As IVlad pointed out that each element is pushed and poped atmost once, time is O(n).

pl do correct me if there is some mistake, and I am curious for any alternate solution which avoids stack and is cheaper.

Answer 3

Stack approach isn't correct. just look what happen if you had in input 6, 9, 12, 17, 11, 15. When you will be work with 15 your stack have been forgotten about 12 & 17. But nearest small left element of A[5] is 12.

Algorithm of Saeed isn't right too. Just try to compute.

Right answer could be something like this

b[1] = a[1];
s[1] = 1;
for (i=2; i<=n; i+=1) { 
  j = i - 1;
  while (j>1){
    if (a[j]<a[i]) {
      b[i] = a[j];
      s[i] = j;
      break;
    } else {
      j = s[j];
    }
  }
  if (j = 1) {
    b[i] = a[j];
    s[i] = j;
  }
}

I'm not sure but it has complexity O(n).