Finding Max in a Stack

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!

Comments

[Sdu]

Some stack implementations or definitions have a peek() methos that reads the last element without popping it.

You could just have a single variable that holds the maximum value where when an element is pushed to the stack, you check if its greater than the existing, if so replace, and when an element is popped, peek the stack to check if the max value is still higher than the last.

This of course is through a modified stack implementation. I also interpreted the problem to be creating a function that takes in a stack (data set already) and returns a max value.

I'd still try to use the idea I mentioned above of a max value variable, but traversing a stack is the interesting part here, I believe.

My flow would be as follows:

• Create a holding stack
• Create max value, initialise it with min possible value
• loop on given stack size is greater that zero then
  • pop value
  • if higher that current max, set to max
  • push to holding stack
• end loop
• loop on holding stack size is greater tha zero
  • pop value, set it to origional stack
• end loop

[Rachel Williams]

Hi Beautus,

Thank you for reading!

I did implement the peek method in my stack to see the last value in the array.

I'm not sure if I am understanding your implementation right, but I think the way you're thinking about the problem is the way I originally thought of it as well. However say you have this stack [1, 2, 1, 3]. In this case, 3 would be your current stored Max. Now if you pop 3 off and just peek the last element, your code would assume the new max is 1, however it's actually 2.

This is why using another stack is helpful. With my code, the max stack would look like this `[1, 2, 2, 3]'. Now when 3 is popped off the stack, my code will also pop the last value of the max stack. Now we have:


//current stack
[1, 2, 1]
//max stack
[1, 2, 2]


Now all we have to do is peek the last element of the max stack and know that the current max is 2.

Thanks for your input and let me know if I cleared it up a bit.

[Sdu]

No no, I do understand your solution fully. What I didn't make clear though is that my solution assumes that a stack is already hydrated when it gets the max value, and your solution is perfect for getting the max value without traversing the stack each time max is required. I'm not sure if you get me

[Rachel Williams]

Oh I see. I did misunderstand at first, I apologize for that. So your solution is a loop, but with pushing to a holding stack while comparing values? This also assumes that no new values are added to the stack. Am I understanding it correctly?

[Sdu]

Yes that definitely it

[JP Antunes]

I find these type of interview questions to be stress inducing and inefficient in screening for candidates that are worth working with (imho).

FWIW, the answer depends on the underlying data structure used to implement the stack.

• If using linked lists, then the solution would involve iterating from head to tail and returning the max value found

• If using arrays, then both Math.max(...stack) or stack.sort((a, b) => b - a)[0] will work

• If using a tree, then the solution would require either traversing or using a self-balancing tree

In all cases, the implementation can also just keep an invariant with the current maximum value, but then it would need to be checked/ updated with every pop and push.

[Rachel Williams]

Hi Joaquim,

Thank you for reading!

I agree these questions can be stressful. I have been trying to look at them more as practice and a fun exercise to learn something new.

Thank you for your input! From my conversation with the interviewer, it was obvious he didn't want to have to re-check with a loop every time a new value was added or removed. He was hinting at using another data structure. In this blog, I took that to mean another stack. This method of getting the current max is nice in that you only have to look at the end of the maxValue stack to know the current max.

Once again thank you for reading and for your input!

[mrseanpaul81]

Tweet from @j_larrieux: @thepracticaldev I think giving more context around the problem would help. I am assuming the question was about keeping track of current max in the stack as new numbers get popped or pushed in the stack. This is not entirely clear from your description.

I love solving interview questions 😀

[Rachel Williams]

Hi Sean,

I think you're right and I should have clarified the problem more.

I was trying to write about the problem in the way it was asked of me which wasn't super clear. Originally he just asked how I would write a function to find max in the stack. However after mentioning looping through, he then mentioned potentially using another data structure to store the max, so that I wouldn't have to loop multiple times.

This led me to believe, as you have mentioned that he wanted to keep track of the current max. This is when I started to think about linked lists to store the current and previous max. However, I think this solution is a lot more elegant even if it comes with the use of more memory.

Let me know if I cleared it up a bit. Thank you again!

[Order & Chaos Creative]

Good solution, it saves having to look up the max after each push/pop.

This reminded me of Priority Queues: algs4.cs.princeton.edu/24pq/

Not sure if it fits the criteria of your interview question, but you might find it interesting anyway.

"Priority queues are characterized by the remove the maximum and insert operations"

[Rachel Williams]

Thank you for reading!

Priority Queues sound very interesting. I'm definitely going to look those up. Thank you for the input!

[Rachel Williams]

I'm glad you enjoyed it!

I come from a non-traditional CS background and didn't get a chance to practice these problems in a classroom. I really appreciate the input.

That implementation on stack overflow is really nice. It's very useful to be able to find the current min and max all in the same step. Thank you for sharing!

[Rachel Williams]

Hi Pavel,

Thank you for reading the blog!

I wrote about the problem in the way that it was asked by my interviewer, which was a little bit confusing to me. I originally thought I was supposed to find max in a given stack as well, until he explained that if the current max was popped off the stack, he would want to know what the previous max was. After he explained this, it was more obvious that he wanted to keep track of the current max.

While I did mention looping through the stack to find the max, he stated that if he popped or pushed an element he would want to know the new max. The interviewer was leading me to believe that he didn't want loops involved, and wanted me to think of a different data structure to use ( a stack). I should have clarified this more in my blog. Thank you for continuing to read through the confusion, I hope I cleared up my thought process a bit.

[Martín Emanuel]

I have the same feeling. The problem solved here doesn't correspond with what I thought was the problem at the beginning of the article.

[Rachel Williams]

Hi Martin,

Thank you for reading. I responded to Pavel with some clarification. Let me know if I cleared it up or if you have any additional input.

Thank you!

[Martín Emanuel]

Thanks for the clarification. Indeed, the explanation given by the interviewer was confusing, and sadly most interviewers want the answer they expect or know and don't care too much about how you would solve a similar problem.

Have a nice day!

[Rachel Williams]

Of course!

I can imagine it is hard to ask technical questions over the phone without being able to write out exactly what you are looking for. Since I come from a non-traditional CS background and knew very little about stacks during this interview, I needed more guidance to understand the problem.

I definitely will be practicing data structures and algorithms in the coming weeks so I can be better prepared next time. It seems like for a lot of algorithms, it is just memorizing the solution that they are looking for, as you have mentioned.

Have a great rest of your week Martín!

[Rachel Williams]

Thanks for the resources! I'll definitely check those out.

That's great! There is hope for me too, then.

[Rachel Williams]

Thanks for reading Calin!