# Create a Stack class which has a method to return the biggest number in O(1)

## What to achieve?

One of my friends told me that there’s a common interview question like following:

- Write a Stack class which have
`push()`

and`pop()`

method- Add
`get_max()`

method which returns the biggest element in the stack `get_max()`

must return the result in O(1)

- Add

It sounds interesting, doesn’t it?

## An example to fulfill the requirement

There’s no description about memory space. How about using 2 stacks inside the Stack class to implement the trick? Let’s call the stacks as *Stack A* and *Stack B*. *Stack A* works as a normal stack, while *Stack B* is used to track the biggest number. The top of *Stack B* is always the biggest number and peeping the value of a stack is O(1).

Here’s how it works.

### Assume that *3* is the first number to push

As the iamge above shows, *3* is pushed to *Stack B* when it’s empty.

### Assume that *2* is the second number to push

*2* is pushed to *Stack A* since it’s just a normal stack.

However, *Stack B* behaves differently. When it’s not empty, the value is compared with the value of the stack top. In this case, *2* is compared with *3* and *Stack B* won’t accept *2* since it’s smaller than *3*.

### Assume that *4* is the third number to push

*4* is pushed to *Stack A* since it’s just a normal stack.

*4* is pushed to *Stack B* as well because it’s bigger than the stack top of it, which is *3*.

Like this way, the top of *Stack B* is always the biggest value of *Stack A*.

### How to pop()?

`pop()`

is relatively easy. `pop()`

always retrieves the top of *Stack A*. If and only if the value retrieved from *Stack A* is the same as the top of *Stack B*, the top of *Stack B* is discarded.

## Sample Code in Python

Here’s my sample code :)