DSA Series: Find the Max Number in a Stack

Given a Stack, keep track of the maximum value in it. The maximum value may be the top element of the stack, but once a new element is pushed or an element is popped from the stack, the maximum element will be now from the rest of the elements.

Inorder to Find the Max Number in a Stack in an efficient way we will do the following:

1. Create an auxiliary stack, called MaxStack to keep track of the maximum element.
2. Push the first element onto both the main stack and the MaxStack.
3. For every subsequent element, push it onto the main stack. Compare the element to the top element of the MaxStack. If the current element is greater than the top of the MaxStack, then push the current element onto the MaxStack. Otherwise, push the top element of the MaxStack back onto it.
4. Whenever an element is popped from the main stack, pop an element from the MaxStack as well.
5. To find the maximum element of the main stack at any point, simply print the top element of the MaxStack.
6. By using the MaxStack to keep track of the maximum value, it’s possible to find the maximum element in constant time, O(1), even as the size of the main stack grows.

Below given diagram represents how the elements are pushed in the main stack and MaxStack

• Step 1 : Push 4, Current max : 4
• Step 2 : Push 2, Current max : 4
• Step 3 : Push 8, Current max : 8
• Step 4 : Push 10, Current max : 10

Now we will see the code implementation:

class StackWithMax {
    private var stack: [Int]
    private var maxStack: [Int]

    init() {
        stack = []
        maxStack = []
    }

    func push(_ element: Int) {
        stack.append(element)
        if let max = maxStack.last {
            maxStack.append(max > element ? max : element)
        } else {
            maxStack.append(element)
        }
    }

    func pop() {
        stack.popLast()
        maxStack.popLast()
    }

    func max() -> Int? {
        return maxStack.last
    }
}

This implementation uses two separate stacks, one to store the actual elements, and another to store the maximum values so far. Each time a new element is pushed onto the stack, the maximum value is also pushed onto the maxStack. This way, the maximum value can always be easily retrieved in O(1) time.

Tattoo-s-DSA/StackWithMax.swift at main · Nikilicious09/Tattoo-s-DSA