Posts Get minimum element from stack (geeksforgeeks - SDE Sheet)
Post
Cancel

Get minimum element from stack (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

You are given N operations and your task is to Implement a Stack in which you can get a minimum element in O(1) time.

geeksforgeeks

SOLUTION

We can solve this by using a stack where each element is an array containing two values: the actual element and the minimum value at that point in the stack. This allows us to maintain the current minimum element efficiently as we push and pop values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class GfG
{
    Stack<int[]> s;

    GfG()
    {
        s = new Stack<>();
    }

    int getMin()
    {
        // Return -1 if the stack is empty
        if(s.isEmpty())
            return -1;

        // Return the second element of the array (the current minimum)
        return s.peek()[1];
    }

    int pop()
    {
        // Return -1 if the stack is empty
        if(s.isEmpty())
            return -1;

        // Pop the stack and return the first element of the array (the value)
        return s.pop()[0];
    }

    void push(int x)
    {
        // If the stack is empty, push the element along with itself as the minimum.
        if(s.isEmpty())

            s.push(new int[]{x, x});

        else{

            // Push the new element along with the current minimum of the stack.
            // The new minimum is either the current element or the minimum at the top of the stack.
            s.push(
                new int[]{
                    x,
                    Math.min(x, s.peek()[1])
                }
            );
        }

    }
}
This post is licensed under CC BY 4.0 by the author.