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.
I'm not sure if it exists O(n) solution.
Anything better,than O(N^2) solution ?
I can tell you a treap solution if you want.
Yes Tell ?
Okay. So you represent the numbers as a pair (number, index). Now for each number you want to find the second maximum index from the pairs with number < current number. This can be done with treap. Just split with current number or perform a standard search for the second maximum index in the part with keys < current number.
"standard search for the second maximum index in the part with keys" — wouldn't it lead to O(n^2)?
I doubt about it's complexity ?
I meant keep the first and second max in the subtree for every node and then split and take the second max.
Build a sparse table of the given array for range minimum queries. Then for each index the answer could be found using two binary searches. This gives you O(n log n) time and space complexity.
I have no idea, how two Binary search is going to work here ? Please take care, I need previous second element by Order from current index.
Implementation
Are you familiar with Sorted Trees?
Yes ?
Then you can make it in O(n*logn)
How ?
You put element into it. Then try to get two steps(as you need second lesser element): downleft+right/left, if there less then 2 elements — go up-and-left or up-and-up in the tree (this is logn operation). If you succeeded — found some element there — this is your answer. Else return zero for this element.
The answer seems interesting, can you explain me it in Detail.
Nice point. Pardon me, I misunderstood the problem. I thought 2nd lesser element must be by value, but examples suggest you need 2nd lesser element by order. No trees needed — take a look at comments lower — I'd guess it would be of more use to stick to a stack.
Though you can solve it using sorted tree this way: you can iterate through element in reversed order (from last to first) and:
Add current element to tree
Paint every element bigger then current
Take elements bigger then current out of tree — current element is the answer for them
Take next element in backward order.
If no elements left (you iterated to the first) — every vertex left in tree has no 2nd min and answer for them is 0.
Hi AZ01, I've got an O(n log n) algorithm which is very easy in implementation because it doesn't require any trees. It uses the trick with a stack about which you've mentioned. I've just developed it a bit. My idea is to go through the array once and remember previous smaller element with maximum index. Simultaneously, you save queries about previous 2nd element. Then, in the second loop, you just answer these queries. My implementation is below. I'm not sure if it's clear so tell me if you don't catch it.
Hi mindrolin
The Approach work's fine. But I think when the Array in strictly decreasing, the solution will work in O(n^2) as the function update_stack can take upto max O(n).
Not really, as in update_stack at each step you pop an element and you cannot pop more than n elements (as every element you have pushed in the stack will be removed exactly once).
One update_stack can have O(n) complexity but the overall complexity will remain O(n).
Yes, Sorry for misunderstanding.
But what about last_lower() function, The worst case of using lower_bound on Array is O(n). I still doubt about it's complexity. I think it's greater than O(nlogn) and less than O(n*n);
Lower_bound for array is O(logn) — it's O(n) for std::set. The complexity of the above solution is O(nlogn).
Consider pi to be the maximum index that pi < i and api < ai. This can be done in O(n) using a stack.
Consider Si to be the set of indices like j that pj = i. Add all elements of Si behind i and color them red. So like for array [2, 1, 4, 3, 5], p = [0, 0, 2, 2, 4], the new array becomes like this: [2, 4r, 3r, 1, 4, 5r, 3, 5]. (by 4r I mean a red 4).
Construct p for the new array in O(n). The answer is p of red elements! It's easy to prove that so I'll leave it up to you.
Could you elaborate this approach a little more, please. I can't make it together.
How can you produce p in O(n) using stack? (Or where to look if its standard problem)
Looks like p = [0, 0, 2, 2, 4] is prev-min-by-value, and for array [2, 1, 4, 3, 5 ] that leads answer ans = [0, 0, 1, 1, 3]. At first I thought this is what TS asked for, but then realized problem is asking for a prev-min-by-order, and right answer should be [0, 0, 2, 2, 4]. Am I getting it right? If so, can you solution be tweaked to do this kind of min-search lineary?
It's really hard to understand, How you have created p and new Array(O(n)). Can you elaborate the steps by taking an Example?
Bashca has coded the same approach below.
you can use solution to previous, two times.
I don't know ,How that is going to work ?
this is my implementation, in the second time, give priority to those who had their minimum in the current element. O(n).
About the push back on line 32.
Don't know why you would push back something that essentially is a query onto the stack. If I understand the algorithm correctly then I think you could/should just remove that line. But maybe you see it in a different way.
oh, yeah. The code is correct but, that line is unnecessary. thanks you.
Bashca can you please explain how does this code has a time complexity of O(n). I am especially confused with the 2nd for loop that you have used after clearing the vector s. It has a nested for loop that runs from 1 to g[i]. If I am not wrong, g does store the index of the 1st minimum of each element in the array.
MotaSanyal the nested for loop doesn’t run from 1 to g[i], it runs for all element in g[i], they are O(n) for all i. for auto
Can you please explain your idea ? I am not getting it
Ok, in the first part we calculate previous minimum for all element, in the second part we calculate the previous element for all element with index < to current minimum. This is easy, only process the answer for element before his minimum previous element.
Actually I am not much accustomed to the syntax of c++ as I code in Python. If u could kindly explain what does g[i] stores, it will be helpful for me. Is g[i] a vector?
Yes, g[i] is a vector.
I appreciate that you ask, and that you do not give me votes against if you did not understand. :)
Just for Knowledge Purpose,
Why you have implemented stack using Array (why not Stack STL itself). Do implementing Stack using Array create any Difference ?
It’s not difference. I prefer vector because it has []
down votes? really?
Yep. Very "constructive" discussion. And "pedagogic" reaction.
Could you please define 2nd previous minimum? I don't understand why in your first example, the 2nd previous minimum for 7 is 3 or for 10 or 8 is 1. How can 1 ever be a 2nd minimum if there is only one 1 in the array?
Example : A = [1,10,15,8,12] res= [0,0,1,0,10];
for value 12, the 2nd previous minimum is 10 not 1, as After 8, 10 is smaller than 12. Actually you have to traverse in backward direction from current index and return 2nd minimum(not global(0 to i-1)).
In that case, a balanced binary tree seems like a good approach. Just adding a function to find the 2nd minimum each time.
Can't see how this can be done using a stack in O(n). Even if minimums are mapped in constant time, they would keep changing.
I hope you find the O(n) implementation someday and share it with us.
I think, I have to close the Blog Post. I found the O(n) solution coded in above comment by Fischer.
One more way to solve this problem is using square root decomposition:
Divide the array into sqrt(n) blocks of size sqrt(n) each.
For each block you maintain the minimum element encountered
You can skip a block if the minimum is greater the current element
Total time complexity would be O(n*sqrt(n))