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]

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).