-3

How to find the minimum value in a stack with O(1) complexity.To find minimum value of a stack I found two ways : 1) min = top value of the stack Traverse the stack and update the min value to get the minimum value of the stack. This requires O(N) complexity where N is the number of elements in the stack

2) Put the stack elements in a minheap The root value that will be extracted will be the minimum value in the stack This requires O(N log(N))

But how do I implement O(1) algorithm , an Algorithm that is Independent of the Input size.

Here the assumption is that the stack is already loaded with elements

user2903496
  • 1
  • 1

1 Answers1

3

You can't. An O(1) algorithm to find the minimum element of an arbitrary stack could also be used to find the minimum element of a doubly linked list, which you could then use to create an O(n) sorting algorithm.

Now, it's possible to implement a stack which keeps track of its minimum element as it's built up. Such a stack could then return its stored minimum value, and only have to do an O(n) search if you happened to pop the minimum element. But that's not really the same thing.

Jose Torres
  • 347
  • 1
  • 3