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.
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])
}
);
}
}
}