5 ms·

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)

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

d--b 5y ago
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.
- ahmedtd 5y ago
  You don't pop the min, you pop the top of the stack.
  - arcastroe 5y ago
    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.
masterof0 5y ago
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.
- d--b 5y ago
  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.