Hacker News Reader

This pretty standard interview question. You should keep track of the current minimum when you do a push: push 1: [(v=1,m=1)] push -1: [(v=1, m=1), (v=-1, m=-1)] push 3: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] get_min: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] returns m=-1 pop: [(v=1, m=1), (v=-1, m=-1)] returns v=3 get_min: returns -1

View on HN

Came here to say this, as far as LC questions go, this one is pretty straight forward. OP, the way you come up with a solution like this is practice and more practice, the same way you can solve an equation you never seen before, because you have a set of tools (patterns, "tricks", knowledge, ...) that allows you to come up with a solution. Keep practicing and you will see the progress.

OP meant O(1) in time and space (forgot the space but it’s in the linked article). That solution is O(N) in space.

problem is when you pop the min, you can't know which was the second to min unless you do the trick that's in the website quoted.

You don't pop the min, you pop the top of the stack.

Yes. Of course. But what do you do when the top of the stack IS the min? Your new min should change, but you won't have the information to update to the second min unless you do the trick in the article.

Reply on news.ycombinator.com