O(1) isn't possible

  • 9

    Because if it were, you could use this data structure to sort an array of numbers in O(n) time.

    So, at the very least, either push(x) or popMax() must be O(logn)

  • -2

    @brendon4565 this is different than sorting, you only need to what's the max in the current stack rather than sorting all

  • 1

    @Rachelee If it's O(1) to pop the max in the current stack, then it takes O(n) time to pop all of the numbers in the stack using popMax. Calling popMax until the stack is empty will result in sorted output.

    If it also takes O(1) time to push numbers onto the stack, then pushing a list of numbers also takes O(n) time. This means that given an arbitrary list of numbers, you could push them all into the stack (O(n) time) and then popMax until the stack is empty (O(n) time) resulting an an overall runtime of O(n) to sort the numbers. Obviously this can't hold, so what Brendon was saying was that one of those operations must be at least log n time.

Log in to reply

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