What is the time complexity to get the minimum element from the Stack?

Java MCQ: What is the time complexity to get the minimum element from the Stack?

Answer:

Explanation:

If a stack does not maintain a separate data structure to track the minimum element, the time complexity to get the minimum element is O(n). This is because, in a typical stack, there is no direct access to the minimum element, and finding it requires traversing the entire stack to compare each element.

For example, consider a scenario where you need to find the minimum element in a stack:

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(5);
        stack.push(30);

        int min = stack.peek();
        for (int i : stack) {
            if (i < min) {
                min = i;
            }
        }
        System.out.println("Minimum element is: " + min); // Outputs: 5
    }
}

In this example, the stack does not have a special mechanism to track the minimum element, so we need to iterate through the entire stack to find it, resulting in O(n) time complexity.

However, if a stack is implemented with a supporting structure that tracks the minimum element (such as an auxiliary stack), the time complexity for retrieving the minimum element can be reduced to O(1), as the minimum is directly accessible. This optimization is useful in applications where frequent access to the minimum element is required without traversing the entire stack.

Reference links:

https://www.javaguides.net/p/java-stack-tutorial.html