Given an array A, calculate B st B [i] stores the nearest element to the left of A [i], which is less than A [i]

Question

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

(For i>1 If there are no such smaller elements on 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 about implementing a stack,
put A[1] on B[1] , then push on the stack.
to fill B[i] compare A[i] with the elements of the stack and pop until you get a smaller element.
finally push A[i] onto the stack.

Is the approach right and is there a cheaper solution?

Answer 1

Your stack rule is correct. This works because if you place an element larger than A[i] , this element will never be needed for any elements following A[i] , because instead you can simply use A[i] .

Each item is available only twice, therefore it is O(n) .

Answer 2

Wrong stack approach. just see what happens if you have input 6, 9, 12, 17, 11, 15 . When you work with 15, your stack has been forgotten about 12 and 17. But the closest small left element A [5] is 12.

Said's algorithm is also wrong. Just try to calculate.

The correct answer may 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 O (n) complexity.

Answer 3

 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 said, each element is pushed out and pushed out at most once, time is O (n).

pl correct me if there is any kind of error and I am wondering which alternative solution avoids the stack and is cheaper.