What would be the datastructure in following scenario? (Stack with maximum)

Question

Please note that there is no limitation of memory. I need to insert int from 1 to 1000.

I can do the each of the following operations in constant order of time:

1. push():adds to the top
2. pop():removes the top element
3. getMax(): returns the max element

Please suggest me appropriate datastructure.

Answer 1

Hi,

Use normal stack structure and additional array for counters int c[1..1000] and variable int maxVal=0.

In code add actions after stack operations:

On push(x) -> c[x]++ ; maxVal = max(x,maxVal)
On pop():x -> c[x]-- ; if (c[x] == 0) { j=x; while(c[--j] == 0); maxVal = j; }

maxVal should have always maximum value.

Maybe I am wrong, this should have amortized computational complexity O(1). It has been a long time since I have been analysing algortihms.

cheers, Piotr

Answer 2

This problem is impossible to solve. Either push has to order its new element or pop has to determine the new biggest element. The worst case for one of these operations will always depend on the number of elements in any datastructure, so these operations cannot be both constant. I believe this would be the only correct answer.

Funny interview question!

Answer 3

Since there is no limitation of memory, I will use 2 vectors - one for the actual data on the stack, and the other to keep track of the max at every state of the stack.
For simplicity sake I'm assuming this stack holds only +ve ints.
I know this doesn't have any error checking. But I am just providing the data structure idea here, not the full-fledged solution.

class StackWithMax
{
 public:
  StackWithMax() : top(-1), currentMax(0) { }
  void push(int x);
  int pop();
  int getMax() { return m[top]; }
 private:
  vector<int> v; // to store the actual elements
  vector<int> m; // to store the max element at each state
  int top;
  int currentMax;
};

void StackWithMax::push(int x)
{
  v[++top] = x;
  m[top] = max(x, currentMax);
}

int StackWithMax::pop()
{
  int x = v[top--];
  currentMax = m[top];
  return x;
}