What if we also want to implement the popMin() function. What is the average complexity?

  • 0

    A straightforward way on top of the existing two-stack solution is to scan the data stack and pop the min item. However the complexity is O(n).

    Another possible solution is to use list to store the data stack and keep a min pointer. So we can remove min from list in O(1) time. Any comment is appreciated.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.