Push, Pop, Range in constant time

Question

I was asked this in an interview:

Design a data structure that allows all these operations in constant, O(1), time:

• Push an element
• Pop an element
• Range of elements : Find the smallest range of interval of the current elements.
  Eg. Range of [1, 22, 44, 56, 99, 98, 56] is 98.

I designed this using a customized stack with two variables, max and min, but this doesn't work after Pop'ing a min or max element.

What I tried :

I used a stack with two extra variable max and min:

DS 
{
 top, //Top of the Stack 
 min, //Min till now
 max  //Max till now
}

Push(DS, elem)
  Push_Stack(DS.top, elem)
  if elem < DS.min
    DS.min = elem
  if elem > DS.max
    DS.max = elem

Range(DS)
 return DS.max - DS.min

Pop(DS)
  x = Pop_Stack(DS.top)
  if (x == DS.min)
    DS.min = Find_New_Min(DS.top) //This takes linear time using this approach
  if (x == DS.max)
    DS.max = Find_New_Max(DS.top)

Answer 1

Implement a "Stack" that includes a range function and uses three stacks internally.

---

The First internal stack will represent the 'real' stack of things being pushed and popped.

The second internal stack will only be pushed to if the new element is bigger than or equal to what is on top of it.

The third internal stack will only be pushed to if the new element is smaller than or equal to what is on top of it.

---

Now, whenever you need to calculate the range, just peek at the top of the second and third stacks and do some simple math.

Whenever an element needs to be popped off the 'real' stack, check to see if the element is also at the top of each of the other two stacks, if it is, pop it off those stacks as well.

Since you have to pop items off the main stack in the opposite order they came in, you won't ever miss anything in the two other stacks... meaning the top of the second and third internal stacks will always be the max and min.

Answer 2

This is similar to Bryon Lo answer, but before he posted I commented same

Maintain 3 stacks

• S1 your final stacks
• S2 and S3 temporary stacks

Rest is self explanatory

  push(T value)
  {
    if (value <= min()) 
    {
        s2.push(value);
    }

    if(value >= max())
    {
        s3.push(value);
    }
    s1.push(value);
  }

 T pop() 
 {
    T value = s1.pop();
    if (value == min()) 
    {
        s2.pop();
    }
    return value;
  }

  T min() 
  {
    if (s2.isEmpty()) 
    {
        return MAX_VALUE;
    } 
    else {
        return s2.peek();
    }
  }

   T max() 
  {
    if (s3.isEmpty()) 
    {
        return MIN_VALUE;
    } 
    else 
    {
        return s3.peek();
    }
  }