Find 2nd previous minimum in Array -> Interview Problem

Revision en5, by AZ01, 2019-02-07 13:59:52

Hi, I am looking for O(n)(Better than O(N^2)) solution of this Problem. The problem is to find the 2nd previous minimum element in Array ,If there is no minimum value we can return 0 ;

Example : Array = [2,4,5,3,1,7,10,8]

Result =[0,0,2,0,0,3, 1,1]

Array = [1,2,3,4,2,3,7,8,2,1]

Result= [0,0,1,2,0,2,2,3,0,0]

All I know is, we can find previous minimum element in O(n) using a Stack. But I don't know how to solve for 2nd previous minimum. Any Suggestions?

Update :- I need previous minimum by order, have a close look at examples.

Update 2: : I found a O(n) solution given by Bashca && AghaTizi. You can see the implementation here or in Comment below.

Thanks for your contribution.

Tags stack, #interview

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English AZ01 2019-02-07 13:59:52 228
en4 English AZ01 2019-02-04 16:57:01 76
en3 English AZ01 2019-02-01 23:36:53 20 Tiny change: 'g for O(n) solution' -> 'g for O(n)(Better than O(N^2)) solution'
en2 English AZ01 2019-02-01 20:18:55 4
en1 English AZ01 2019-02-01 20:18:08 514 Initial revision (published)