Fancy Stack

In this chapter, we discuss the complexity of various operations of a stack which supports a multipop operation.

We are all aware of the push and pop operations offered by a stack data structure. Both push and pop are trivial and take O(1) or constant time. Now imagine the stack also offers a multipop operation, which allows us to pop k elements at once, assuming the stack holds atleast k elements. If we conduct n operations on the stack, what is the average time complexity of each of the n operations?

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.