Growing with the Web

Implement a maximum value aware stack

Published
Tags:

This article looks at the interview question - Implement a stack that can return its maximum value in constant time.

Analysis

First let’s look at the trivial solution; the maximum value can be retrieved from the stack at any time by simply iterating through the backing data structure when the value is requested. This runs in linear time however, so it doesn’t fit the requirements.

A key observation that leads to the solution of this problem is noticing that the maximum of the stack does not change when n items are added and then removed. This means that we could evaluate and record the maximum of the stack at the point the value is pushed, push remains a O(1) operation as we’re only comparing the new value against the previous maximum.

This implementation does indeed accomplish the goal, but can it be improved upon? The illustration above has a lot of repeated numbers so it might be wasting space. The example above shows maximum stack values of 2, 3 and 6, but if 6 was pushed to the stack first there would be n copies of the same value.

Now think about when the maximum value actually changes. It happens when the maximum value itself is removed from the stack, so we could modify our algorithm to take this into account. We’ll now have 2 stacks; one for values and one for maximum values. The top of the maximum value stack is only removed when the same value is removed from the value stack.

An important edge case to consider here is whether duplicate values are supported. Our new optimised algorithm will fail unless it’s explicitly covered. Instead of pushing new maximum values on to the stack when the new value is greater than the maximum value, it needs to be pushed when greater than or equal to. This will allow multiple of the same values to appear on the maximum value stack which will get removed at the correct time.

This answer goes above and beyond what was asked by presenting the optimal solution, which is often what interviewers are looking for.

Complexity

The initial implementation runs in O(1) time and uses Θ(n) additional space.

The optimised implementation runs in O(1) time and uses O(n) additional space.

Code

Initial implementation

public class MaxAwareStack<T extends Comparable<T>> {
    private Stack<MaxAwareEntry> stack = new Stack<MaxAwareEntry>();

    public void push(T obj) {
        MaxAwareEntry entry = new MaxAwareEntry(obj);
        if (stack.size() == 0) {
            entry.max = obj;
        } else {
            T currentMax = stack.peek().max;
            entry.max =  currentMax.compareTo(obj) > 0 ? currentMax : obj;
        }
        stack.push(entry);
    }

    public T pop() {
        if (stack.size() == 0) {
            return null;
        }
        return stack.pop().value;
    }

    public T getMax() {
        if (stack.size() == 0) {
            return null;
        }
        return stack.peek().max;
    }

    private class MaxAwareEntry {
        public T value;
        public T max;

        public MaxAwareEntry(T value) {
            this.value = value;
        }
    }
}
/**
 * Creates a stack that is aware of its maximum value in constant time.
 */
function MaxAwareStack() {
  // Store the value and the maximum at any given point in objects of form:
  // { value: number, max: number }
  this.stack = [];
}

/**
 * Push a value to the stack.
 * @param {*} value The value to push.
 */
MaxAwareStack.prototype.push = function (value) {
  var top = this._top();
  var entry;
  if (!top) {
    entry = {
      value: value,
      max: value
    };
  } else {
    entry = {
      value: value,
      max: value > top.max ? value : top.max
    };
  }
  this.stack.push(entry);
}

/**
 * Pops a value from the stack and returns it.
 * @return {*} The popped value.
 */
MaxAwareStack.prototype.pop = function () {
  if (this.stack.length === 0) {
    return undefined;
  }
  return this.stack.pop().value;
}

/**
 * Gets the maximum value in the stack.
 * @return {*} The maximum value.
 */
MaxAwareStack.prototype.max = function () {
  if (this.stack.length === 0) {
    return undefined;
  }
  return this._top().max;
}

/**
 * A private convenience function for getting the top entry of the stack.
 * @return {Object} The top entry.
 */
MaxAwareStack.prototype._top = function () {
  return this.stack[this.stack.length - 1];
}

module.exports = MaxAwareStack;

Space-optimised implementation

public class MaxAwareStackOptimised<T extends Comparable<T>> {
    private Stack<T> valueStack = new Stack<T>();
    private Stack<T> maxStack = new Stack<T>();

    public void push(T obj) {
        if (maxStack.size() == 0 || obj.compareTo(getMax()) >= 0) {
            maxStack.push(obj);
        }
        valueStack.push(obj);
    }

    public T pop() {
        if (valueStack.size() == 0) {
            return null;
        }
        T result = this.valueStack.pop();
        if (result == getMax()) {
            this.maxStack.pop();
        }
        return result;
    }

    public T getMax() {
        if (maxStack.size() == 0) {
            return null;
        }
        return maxStack.peek();
    }
}
/**
 * Creates a stack that is aware of its maximum value in constant time.
 */
function MaxAwareStackOptimised() {
  this.valueStack = [];
  this.maxStack = [];
}

/**
 * Push a value to the stack.
 * @param {*} value The value to push.
 */
MaxAwareStackOptimised.prototype.push = function (value) {
  if (this.maxStack.length === 0 || this.max() <= value) {
    this.maxStack.push(value);
  }
  this.valueStack.push(value);
}

/**
 * Pops a value from the stack and returns it.
 * @return {*} The popped value.
 */
MaxAwareStackOptimised.prototype.pop = function () {
  if (this.valueStack.length === 0) {
    return undefined;
  }
  var result = this.valueStack.pop();
  if (result === this.max()) {
    this.maxStack.pop();
  }
  return result;
}

/**
 * Gets the maximum value in the stack.
 * @return {*} The maximum value.
 */
MaxAwareStackOptimised.prototype.max = function () {
  if (this.maxStack.length === 0) {
    return undefined;
  }
  return this.maxStack[this.maxStack.length - 1];
}

module.exports = MaxAwareStackOptimised;

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!