algorithm - Given an array A,compute B s.t B[i] stores the nearest element to the left of A[i] which is smaller than A[i] -

given array a[1..n], want compute array b[1..n] such b[i] stores nearest element left of a[i] smaller a[i]. time complexity should o(n).

(for i>1,if there no such smaller elements left, b[i] contains a[i], , b[1]=a[1].)

example :

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

i thinking implementing stack,
put a[1] in b[1], push stack.
filling b[i],compare a[i] elements of stack , pop till smaller element.
push a[i] stack.

is above approach correct, , there cheaper solution?

your stack approach correct. works because if pop element bigger a[i], element never needed elements following a[i], because can use a[i] instead.

each element accessed twice, o(n).