One algorithm a day: Keeping track of the largest element in a stack

in programming •  6 years ago  (edited)

Imagine that you want to be able to access the largest element in a stack. I know you were dying to do it !
You already have implementation of the stack class:

class Stack<Item> {
    
    // initialize an empty array
    private var items: [Item] = []
    
    // push a new item to the last index
    func push(_ item: Item) {
        items.append(item)
    }
    
    // remove the last item
    func pop() -> Item? {
        
        // if the stack is empty, return nil
        // (it would also be reasonable to throw an exception)
        if items.count == 0 {
            return nil
        }
        return items.removeLast()
    }
    
    // see what the last item is
    func peek() -> Item? {
        return items.last
    }
}

Use your Stack class to implement a new class MaxStack with a method getMax() that returns the largest element in the stack. getMax() should not remove the item.
The easiest way to tackle a problem is to have a private stack that will keep track of all of the previous max elements of the stack. When you want to push new element on the stack, compare it with the current largest item. If it's bigger than existing one add it to the stack.

Same thing with the removing items. Check if the removed item is the biggest. If it is remove it from the private stack keeping track of the max elements.

Here is example of how it could be implemented:

class MaxStack<Item:Comparable>:Stack<Item>{
   private  var maxes:Stack<Item> = Stack<Item>()
    
    override func push(_ item:Item){
        super.push(item)
        //check if the last element is bigger than this one
        
        //if not add it to the stack
        if let max = maxes.peek()
        {
            if max <= item{
                maxes.push(item)
            }

        }
        else{
             maxes.push(item)
        }
        
    }

    override func pop() -> Item? {
        if let max = maxes.peek(), let pop = super.pop(){
            if max == pop {
                maxes.pop()
            }
        }

        return super.pop()
    }
    
   func getMax()->Item?{
        return maxes.peek()
    }
}

And don't forget about the test cases:

var maxStack = MaxStack<Int>()
maxStack.push(10)
maxStack.getMax()//10
maxStack.push(5)
maxStack.push(20)
maxStack.getMax()//20
maxStack.pop()
maxStack.getMax()//10

Time and space complexity

This solution uses 0(n) space, O(1) complexity

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!