1

Suppose there are 50000+ integer entries in a Stack? How to efficiently find out a maximum or minimum in it? Stack can grow or reduce i.e., pop() and push(), but we need to keep track of max and min value in the stack?

Sharath
  • 407
  • 5
  • 16
  • What is the programming language? How is the stack implemented, with arrays or linked list? – Yu Hao Oct 29 '14 at 09:01
  • Do you nee to implement this kind of stack? do you have a stack and want to find min&max? do you have any O(?) limitations on operations? do you have some code to share? – yossico Oct 29 '14 at 10:53
  • possible duplicate of [Stack with find-min/find-max more efficient than O(n)?](http://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-on) – Jim Mischel Oct 29 '14 at 12:40

2 Answers2

1

As Mischel pointed out, Stack with find-min/find-max more efficient than O(n)?, already answers the question.

However that response suggests that you need to store each and every max and min at each point in the stack. A better solution would be to have a separate stack for the max and the min. For the max stack you will push a new element onto the max stack only if the new element is greater than the current max, and vice-versa for min. You will pop elements of the min and max stacks when the element that you are popping of the main stack is equal to them and not equal to the next element in the main stack.

Note that this requires O(n) extra space while providing O(1) operations.

Community
  • 1
  • 1
navari
  • 287
  • 2
  • 14
0

The only idea I have is to inherit Stack and keep inside max and min. On pop and push do changes to your max and min.

Alexey Shumeyko
  • 117
  • 2