In this article we will implement methods to get the minimum element from all the elements present in our stack. We will first use the naive approach and then use the efficient method to get the constant time complexity.
In both the methods we will use constant space O(1).
In the naive method we call getMin()
. This method will traverse through the stack. Stacks work internally on Last in First Out (LIFO). If any element we want to search is present at the end of the stack, in that case we will have to traverse the whole stack to get our minimum element from the stack (worst case scenario).
Java Implementation
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
51
52
53
54
55
56
import java.util.*;
import java.lang.*;
class UDStack { //user defined stack class
Stack < Integer > stk;
//cons to create object of UIStack class
UDStack() {
stk = new Stack < Integer > ();
}
//to push element into stack
void push(int ele) {
stk.push(ele);
return;
}
//it will remove the topmost element from stack
int pop() {
if (stk.isEmpty()) {
System.out.println("Underflow Error: Stack is Empty");
}
return stk.pop();
}
//to get minimum element from stack O(N)
int getMin() {
if (stk.isEmpty()) {
System.out.println("Underflow Error: Stack is Empty");
}
Iterator < Integer > itr = stk.iterator();
int minElement = stk.peek();
while (itr.hasNext()) {
int x = itr.next();
if (x < minElement)
minElement = x;
}
return minElement;
}
}
public class Solution {
public static void main(String args[]) {
UDStack stk = new UDStack();
stk.push(10);
stk.push(20);
stk.push(30);
stk.push(50);
stk.push(60);
System.out.println("Minimum Element is:" + stk.getMin());
}
}
Code Snippet:
Time Complexity: O(N) - As we are traversing the whole stack.
Space Complexity: O(1) - No extra space is used.
In this method we will get the minimum element from the stack with the best case time complexity O(1). We will create an integer, minCurrentElement, and use it to store the current minimum element. When the getMin()
element is called we will use minCurrentElement to return the minimum element from the stack. Using the minCurrentElement we will push “2*(currentElement) - minCurrentElement” into the stack rather than pushing the currentElement.
Step 1: push(int element)
--> method called
When push() method is called then if currentElement is the first element, push into stack and return.
Otherwise go to step two.
Step 2:
If the current element is less than minElement then push
2*currentElement - minElement and update minElement with currElement.
Otherwisec push the current element.
Step 3:
If the call is made to getMin()
method then
return minElement.
So, without traversing the stack, the minElement is returned.
Java Implementation
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.*;
import java.lang.*;
class UDStack { //user defined stack class
Stack < Integer > stk;
static int minElement;
//cons to create object of UIStack class
UDStack() {
stk = new Stack < Integer > ();
}
//to push element into stack
void push(int currentElement) {
if (stk.isEmpty()) {
minElement = currentElement;
stk.push(currentElement);
return;
}
if (currentElement < minElement) {
stk.push(2 * currentElement - minElement);
minElement = currentElement;
} else
stk.push(currentElement);
}
//it will remove the topmost element from stack
int pop() {
if (stk.isEmpty()) {
System.out.println("Underflow Error: Stack is Empty");
}
return stk.pop();
}
//to get minimum element from stack O(N)
int getMin() {
if (stk.isEmpty()) {
System.out.println("Underflow Error: Stack is Empty");
}
//minElement is already calculated while pushing into stack
return minElement;
}
}
public class Solution {
public static void main(String args[]) {
UDStack stk = new UDStack();
stk.push(10);
stk.push(20);
stk.push(30);
stk.push(50);
stk.push(10);
System.out.println("Minimum Element is:" + stk.getMin());
}
}
Code Snippet
Time Complexity: O(1) - No stack traversed.
Space Complexity: O(1) - No Extra space used.