Stack Problem

I recently had a phone interview with a company and was asked a question about stacks that I didn't know how to properly solve. This prompted me to deepen my knowledge of stacks.

I was asked to think about how I would write a max function to find the maximum value in a stack.

Stack Refresher

A stack is a data structure where newer items are added on top and items are also removed from the top. This is called Last In First Out (LIFO). One way to represent a stack is an array. When thinking about the problem on the phone call, I pictured an array where items would be added onto the end and also taken off of the end.

Here is an example:

[2, 3, 3, 1, 1, 100, 200, 100, 400, 30]

30 would be the top of the stack and would also be the first number removed from the stack.

Back to the Problem

During the phone call, I could only come up with a few solutions, which I knew were not what the interviewer was looking for. My first obvious thought was to loop through the array, storing the current maximum number and return that number at the end. This was clearly not what the interviewer was looking for and asked me how I would solve this with a different data structure.

Next I tried to think of a way I could use an object, and linked lists came to mind. My idea was to store the current maximum value in a linked list with a pointer to the previous maximum number, in case the current maximum number was deleted. I didn't fully think through this idea, as I hadn't reviewed how to implement a linked list in a while and I had a hunch that this wasn't what the interviewer was looking for.

We moved on from this question and I was determined to figure out the answer once I got off the phone.

After Some Googling

After some googling, I came across an implementation that seemed like what my interviewer was actually looking for.

With this implementation, you would have an additional stack to store your max values. You would read the top value from this extra stack to see what the current maximum value was.

For example, given this initial stack:

[3]

I would have a max value stack that looks like this:

[3]

Three is the only number in the stack so far, thus it is the maximum. Now if I push 5 onto the stack, my current max should be 5. So we will add that onto our max value stack.

//currentStack
[3, 5]
//maxNumStack
[3, 5]

Now say we add a number that is less than or equal to our current max onto the stack. Now, we would just add the current max again to our maxNumStack to align the lengths of the stacks.

//currentStack
[3, 5, 4]
//maxNumStack
[3, 5, 5]

This way, if 4 is popped off of the stack, we can pop one element off of our maxNumStack as well and still know what the currentMax is (in this case 5).

Implementing the Stack With a Max Method

This is how I might implement this with JavaScript. I roughly followed this blog to implement the basic features of a stack, such as the push and pop methods:

class Stack {
  constructor() {
    this.data = [];
    this.size = 0;
    this.maxValues = [];
  }

  push(element) {
    // if the stack is empty or the element we're pushing is greater than currentMax, add the new element to maxValues
    if (this.size === 0 || element >= this.findMax()) {
      this.maxValues.push(element)
    }
    // otherwise, push the currentMax to maxValues again, to align lengths of arrays and keep currentMax
    else {
      this.maxValues.push(this.findMax())
    }
    // increase the size variable by 1 to keep track of length, and add element to stack
    this.size += 1
    this.data.push(element);
    return this.data
  }

  pop() {
    // if the stack isn't empty, decrease the size count and remove element from the end of the stack and maxValue array to keep lengths aligned
    if (this.size > 0) {
      this.size -= 1;
      this.maxValues.pop()
      return this.data.pop()
    }
  }

  // this returns the top element in the stack (last element in the array)
  peek() {
    return this.data[this.size - 1]
  }

  // this returns the maxValue currently in the stack, by grabbing the last element of the maxValue stack
  findMax() {
    return this.maxValues[this.size - 1]
  }
}

Here is some code I wrote to test that it worked along with the outputs in my terminal:

let stack = new Stack()

stack.push(5)
stack.push(5)
stack.push(7)
stack.push(3)
stack.push(4)

console.log(stack)
// Stack {data: [ 5, 5, 7, 3, 4 ], size: 5, maxValues: [ 5, 5, 7, 7, 7 ]}
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5, 7, 3 ], size: 4, maxValues: [ 5, 5, 7, 7 ] }
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5, 7 ], size: 3, maxValues: [ 5, 5, 7 ] }
console.log("max", stack.findMax())
// max 7

stack.pop()
console.log(stack)
// Stack { data: [ 5, 5 ], size: 2, maxValues: [ 5, 5 ] }
console.log("max", stack.findMax())
// max 5

With this implementation, theoretically all you would be doing to find the max is a quick lookup operation to find the last element in the maxValues array. Looking up an element in an array by index has a time complexity of O(1). Also, the push() and pop() operations to add and remove values from the maxValues stack have a time complexity of O(1). This is significantly more efficient than looping through the array to find the current maximum every time, which would be O(n), where n is the length of the array.

As a side note, there are other ways to implement the push and pop methods, however that wasn't the focus of this blog so I chose to use the built in array methods.

Wrapping It Up

When is a time you have used a stack in your code? Let me know what you think of this solution and if you think it can be improved. Thank you for reading!