Get Minimum element from stack Part-1

In the Problem Get Minimum Element From The Stack, we need to get the minimum element in O(1) T.C. Here before we try to discuss on the efficient approach, lets discuss on the Ideas that we usually get. You can have a min variable and each time you push some element you can update this min element. But the issue with is that once we pop the min value we don't have the the information on what is the next min value in the stack. To overcome this we can have an auxiliary array where all the minimums are stored when ever the min is updated. But we need an extra space for this. But our Problems requires to be done in O(1) space complexity too!

So some how we need to trace back the previous min elements without the extra space. I tried but could not come with any solution. And at this time I have seen the hint for this Problem and it uses 2*cur_element - Min to store in the stack when ever a new element is seen. I want to explore further tomorrow on why this equation is used. It should be used to trace the previous elements that is for sure I am guessing. Lets hope that I will get to the solution with this hint.

要查看或添加评论,请登录

Vamshi Krishna Raj S的更多文章

社区洞察

其他会员也浏览了