Project 1
EQUILIBRIUM POINT
Given an array A of N positive numbers. The task is to find the position where equilibrium first occurs in the array. Equilibrium position in an array is a position such that the sum of elements before it is equal to the sum of elements after it. Complete the function whose argument is the array A and which prints the position at which the elements are at equilibrium if no equilibrium point exists print -1.
Constraints:
1 <= N <= 106
1 <= Ai <= 108
Explaantion: To solve this problem we will follow the following steps:
step 1: Initially assign sum as 0.
step 2: getting total of sum of array and storing it
step 3: Now iterating over each index of the array and calculating sum as: sum = sum -arr[i]
so if leftsum is equal to sum, then return current index so we'll calculate the leftsum as leftsum = leftsum + arr[i]
step 4: so we will return -1 if we don't return then there's no equilibrium found.
Code:
package project1;
public class EquilibriumPoint {
int equilibrium(int arr[], int n)
{
int sum = 0; // initialize sum of whole array
int leftsum = 0; // initialize leftsum
/* Find sum of the whole array */
for (int i = 0; i < n; ++i)
sum += arr[i];
for (int i = 0; i < n; ++i) {
sum -= arr[i]; // sum is now right sum for index i
if (leftsum == sum)
return i;
leftsum += arr[i];
}
/* If no equilibrium index found, then return 0 */
return -1;
}
// Driver code
public static void main(String[] args)
{
EquilibriumPoint equi = new EquilibriumPoint();
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = arr.length;
System.out.println("First equilibrium index is " +
equi.equilibrium(arr, arr_size));
}
}
//output:
//First equilibrium index is 3
//Time complexity: O(n)Video: link
------------------------------------------------------------
LEADERS IN AN ARRAY
Given an array of positive integers. Your task is to find the leaders in the array. An element of array is leader if it is greater than or equal to all the elements to its right side. Also, the rightmost element is always a leader. Complete the function which takes the elements of the array and prints all the leaders.
Constraints:
1 <= N <= 107
0 <=
Explanation: To solve this equation we will scan the array from the right to left and compare and if it's greater then we will print the element.
Code:
package project1;
public class LeaderInArray {
void printLeaders(int arr[], int size)
{
int max_from_right = arr[size-1];
/* Rightmost element is always leader */
System.out.print(max_from_right + " ");
for (int i = size-2; i >= 0; i--)
{
if (max_from_right < arr[i])
{
max_from_right = arr[i];
System.out.print(max_from_right + " ");
}
}
}
/* Driver program to test above functions */
public static void main(String[] args)
{
LeaderInArray lead = new LeaderInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
//output:
//2 5 17
//Time Complexity: O(n)Video: link
-------------------------------------------------------------
REVERSE WORDS IN A GIVEN STRING
Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots. Complete the function which takes a string S containing characters and outputs a single line containing the reversed String.
Constraints:
1 <= T <= 100
1 <= |S| <= 2000
Explanation: We Will split the array after the space and store it array, and using for loop we will reverse the statement
code:
package project1;
public class ReverseString {
public static void main(String[] args)
{
String s[] = "i like this program very much".
split(" ");
String ans = "";
for (int i = s.length - 1; i >= 0; i--)
{
ans += s[i] + " ";
}
System.out.println("Reversed String:");
System.out.println(ans.substring(0,
ans.length() - 1));
}
}
//output:
//Reversed String:
much very program this like i
//Time Complexity: O(n)Video: link
----------------------------------------------------------
REMOVE DUPLICATES
Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same. Complete the function that takes a string and prints the modified string without duplicates and same order of characters.
Constraints:
1 <= |string|<= 1000
Explanation:
To solve this problem we will use the for loop to check for the character, and if it's not present the we will store it in str, and if it's present in the str the new will drop that character.
Code:
package project1;
public class RemoveDuplicates {
// Function to make the string unique
public static String unique(String s)
{
String str = new String();
int len = s.length();
// loop to traverse the string and
// check for repeating chars using
// IndexOf() method in Java
for (int i = 0; i < len; i++)
{
// character at i'th index of s
char c = s.charAt(i);
// if c is present in str, it returns
// the index of c, else it returns -1
if (str.indexOf(c) < 0)
{
// adding c to str if -1 is returned
str += c;
}
}
return str;
}
// Driver code
public static void main(String[] args)
{
// Input string with repeating chars
String s = "geeksforgeeks";
System.out.println(unique(s));
}
}
//Output:
//geksfor
//Time Compelxity:
//O(n)Video: link
-----------------------------------
FINDING MIDDLE ELEMENT IN A LINKED LIST
Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3. If there are even nodes, then there would be two middle nodes, we need to print the
second middle element. For example, if given linked list is 1 ->2->3->4->5->6 then the output should be 4.
The task is to complete the function getMiddle() which takes the list reference and returns data of the middle element of the linked list.
Expected Time Complexity: O(N).
Expected Space Complexity: O(1).
Constraints:
1 <= T <= 500
1 <= N <= 5000
Explanation: To solve this problem we will use two pointer method, where we will use one slow pointer which will move 1 node at a time and the second pointer which will move 2 node, so by the time second (fast pointer) reaches the end the first pointer(slow pointer) will reach the mid.
that's how we get mid and we will print the mid element.
code:
package project1;
public class MidLinkedList {
Node head; // head of linked list
/* Linked list node */
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to print middle of linked list */
void printMiddle()
{
Node slow_ptr = head;
Node fast_ptr = head;
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println("The middle element is [" +
slow_ptr.data + "] \n");
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* This function prints contents of linked list
starting from the given node */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+"->");
tnode = tnode.next;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
MidLinkedList llist = new MidLinkedList();
for (int i=5; i>0; --i)
{
llist.push(i);
llist.printList();
llist.printMiddle();
}
}
}
//output:
//5->NULL
//The middle element is [5]
//4->5->NULL
//The middle element is [5]
//3->4->5->NULL
//The middle element is [4]
//2->3->4->5->NULL
//The middle element is [4]
//1->2->3->4->5->NULL
//The middle element is [3]
Time Complexity: O(n)
Video: link
-----------------------------------------------------------
REVERSE A LINKED LIST
Given a linked list of N nodes. The task is to reverse this list.
Example if linkedlist is Explanation: After reversing the list, elements are.
The task is to complete the function reverseList(givenList) with givenList reference and returns the list after reversing it.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 104
Explanation: To solve this problem we will create prev, next and current. and will assign the prev as null, current as head and next as null.
before changing the next of current store next node as next = current->next, now change the next of current and current.next = prev
and moving the prev and current one node ahead, prev = current and current = next.
Code:
package project1;
public class ReverseLinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to reverse the linked list */
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
// prints content of double linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
ReverseLinkedList list = new ReverseLinkedList();
list.head = new Node(85);
list.head.next = new Node(15);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(20);
System.out.println("Given Linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
//output:
//Given Linked list
//85 15 4 20
//Reversed linked list
//20 4 15 85
Time Complexity: O(n)
Space Complexity: O(1)Video: link
-------------------------------------------------------
PAIRWISE SWAP ELEMENTS OF A LINKED LIST
Given a singly linked list of size N. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.
Complete the function pairWiseSwap() which takes the the linked list and retu rns the modified linked list after swapping pairwise nodes.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 103
Explanation:
If there are two nodes in the given LinkedList then we will swap both the nodes and iteratively follow for the other elements if there are more node present in the LinkedList.
Code:
package project1;
public class PairReverseLinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
static void swap(int data1, int data2) {
int temp = data1;
data1 = data2;
data2 = temp;
}
void pairWiseSwap()
{
Node temp = head;
/* Traverse only till there are atleast 2 nodes left */
while (temp != null && temp.next != null) {
/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
PairReverseLinkedList llist = new PairReverseLinkedList();
/* Created Linked List 1->2->3->4->5 */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();
llist.pairWiseSwap();
System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}
//Output:
//Linked List before calling pairWiseSwap()
//1 2 3 4 5
//Linked List after calling pairWiseSwap()
//2 1 4 3 5
//Time Complexity: O(n)
Video: link
----------------------------------------------------------------
ADD TWO NUMBERS REPRESENTED BY LINKED LISTS
Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers.
Complete the function addTwoLists() which takes both the linked lists and returns the new list.
Expected Time Complexity: O(N) + O(M)
Expected Auxiliary Space: O(N) + O(M)
Constraints:
1 <= N, M <= 5000
Explanation:
Traversing the list and making sure to add zero if one of the linked lists have lesser number.
start from the head of each node recursively calling the rest of the list
creating a node for current addition and returning the carry.
Code:
package project1;
public class AddTwoLinkedList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
/* Adds contents of two linked lists and prints it */
void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}
/* Adds lists and returns the carry */
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}
/* Appends preceding zeros in case a list is having lesser nodes than the other one*/
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
/* Utility function to print a linked list */
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
// Driver Code
public static void main(String[] args) {
AddTwoLinkedList list = new AddTwoLinkedList();
// creating first list
list.head1 = new Node(7);
list.head1.next = new Node(5);
list.head1.next.next = new Node(9);
list.head1.next.next.next = new Node(4);
list.head1.next.next.next.next = new Node(6);
System.out.print("First List is ");
list.printList(head1);
// creating second list
list.head2 = new Node(8);
list.head2.next = new Node(4);
System.out.print("Second List is ");
list.printList(head2);
System.out.print("Resultant List is ");
// add the two lists and see the result
list.addTwoLists(head1, head2);
}
}
//output:
//First List is 7 5 9 4 6
//Second List is 8 4
//Resultant List is 7 6 0 3 0
Time Complexity: O(m + n)Video: link
----------------------------------
BINARY TREE TO DLL
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In -Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.
Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .
Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000
Explanation: To solve this problem we will do in order traversal of the binary tree, and while we do the traversal we will store the pointer of the previously visited node so that we can have two-way pointer and can create doubly linkedlist.
Code:
package project1;
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
public class BinaryToDll {
Node root;
// head --> Pointer to head node of created doubly linked list
Node head;
// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static Node prev = null;
// A simple recursive function to convert a given Binary tree
// to Doubly Linked List
// root --> Root of Binary Tree
void BinaryTree2DoubleLinkedList(Node root) {
// Base case
if (root == null)
return;
// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root.left);
// Now convert this node
if (prev == null)
head = root;
else {
root.left = prev;
prev.right = root;
}
prev = root;
// Finally convert right subtree
BinaryTree2DoubleLinkedList(root.right);
}
/* Function to print nodes in a given doubly linked list */
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.right;
}
}
// Driver program to test above functions
public static void main(String[] args) {
// Let us create the tree as shown in above diagram
BinaryToDll tree = new BinaryToDll();
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);
// convert to DLL
tree.BinaryTree2DoubleLinkedList(tree.root);
// Print the converted List
tree.printList(tree.head);
}
}
//output:
//25 12 30 10 36 15
//Time complexity: O(n)
Video: link
--------------------------------------------------
BELLMAN FORD ALGORITHM
Implement the Bellman Ford Algorithm to find Shortest paths to all vertices from a single source.
Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
If there is a negative weight cycle then print -1
Expected Time Complexity- O(VE)
Explanation: to implement we will take the source vortex and the graph as the input, initially we will assign source vortex as 0 and rest as infinity.
we will create an array with size |v| where all the vertices are assigned as infinity and source as 0.
To find the shortest distance we will run the loop for |V| - 1 times where v is the number of vertices.
and will check the following condition if dist[v] > dis[u] + weight of edge uv then we will update the dist[v] = dist[u] + weight of uv
and if the condition is false then there will be the cycle in the graph.
Code:
package project1;
public class Bellmanford {
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge()
{
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Bellmanford(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Bellmanford graph, int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can
// have at-most |V| - 1 edges
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Bellmanford graph = new Bellmanford(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}
//Output
//Vertex Distance from Source
//0 0
//1 -1
//2 2
//3 -2
//4 1
Time Complexity: (VE)Video: link
----------------------------------------------------------------------------
MINIMUM SWAPS TO SORT
Given an array of integers. Find the minimum number of swaps required to sort the array in non-decreasing order.
complete the function minSwaps() which takes the array arr[] and prints the minimum number of swaps required to sort the array. If the array is already sorted, return 0.
Constraints:
1 <= size of A <= 105
1 <= A[] <= 106
Expected Time Complexity: O(NlogN).
Expected Space Complexity : O(N).
Explanation: To solve this problem we will use the hash map implementation to get the right output in O(nlogn) time complexity,
We will create a new array to store which will be the copy of out input array with sorted values stored inside.
we will create a hash map to store the values of our input array and we will compare it with the temp array and rearrange the value accordingly.
Code:
package project1;
import java.util.Arrays;
import java.util.HashMap;
public class MinimumSwap {
// Return the minimum number
// of swaps required to sort the array
public int minSwaps(int[] arr, int N)
{
int ans = 0;
int[] temp = Arrays.copyOfRange(arr, 0, N);
// Hashmap which stores the
// indexes of the input array
HashMap<Integer, Integer> h
= new HashMap<Integer, Integer>();
Arrays.sort(temp);
for (int i = 0; i < N; i++)
{
h.put(arr[i], i);
}
for (int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
int init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h.get(temp[i]));
// Update the indexes in
// the hashmap accordingly
h.put(init, h.get(temp[i]));
h.put(temp[i], i);
}
}
return ans;
}
public void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Driver class
class Main
{
// Driver program to test the above function
public static void main(String[] args)
throws Exception
{
int[] a
= { 101, 758, 315, 730, 472,
619, 460, 479 };
int n = a.length;
// Output will be 5
System.out.println(new GfG().minSwaps(a, n));
}
}
//output: 5
//time complexity: O(nlogn)
//space complexity: O(n)
Video: link
-------------------------------------------------------
GET MINIMUM ELEMENT FROM STACK
You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.
Complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer popped out from the stack and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)
Expected Time Complexity : O(1) for all the 3 methods.
Expected Space Complexity : O(1) for all the 3 methods.
Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100
Explanation: let us break down the problem into parts and try to understand the logic.
let us first understand the 'push() method.
step 1: we will check if the stack is empty if its empty then we will simply insert x and assign x = minEle.
step 2: if the stack is not empty then we will compare x with minEle and there are two cases:
a. if x is greater than or equal to minEle, insert x
b. If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x.
let us understand the 'pop()' method:
step 1: to remove element there are two cases
a. If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
b. If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y).
code:
package project1;
import java.util.Stack;
public class MinElementStack {
Stack<Integer> s;
Integer minEle;
// Constructor
MinElementStack()
{ s = new Stack<Integer>();
}
// Prints minimum element of MyStack
void getMin()
{
// Get the minimum number in the entire stack
if (s.isEmpty())
System.out.println("Stack is empty");
// variable minEle stores the minimum element
// in the stack.
else
System.out.println("Minimum Element in the " +
" stack is: " + minEle);
}
// prints top element of MyStack
void peek()
{
if (s.isEmpty())
{
System.out.println("Stack is empty ");
return;
}
Integer t = s.peek(); // Top element.
System.out.print("Top Most Element is: ");
// If t < minEle means minEle stores
// value of t.
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}
// Removes the top element from MyStack
void pop()
{
if (s.isEmpty())
{
System.out.println("Stack is empty");
return;
}
System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
System.out.println(minEle);
minEle = 2*minEle - t;
}
else
System.out.println(t);
}
// Insert new number into MyStack
void push(Integer x)
{
if (s.isEmpty())
{
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}
// If new number is less than original minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
System.out.println("Number Inserted: " + x);
}
public static void main(String[] args)
{
MinElementStack s = new MinElementStack();
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
}
};
//output:
//Number Inserted: 3
//Number Inserted: 5
//Minimum Element in the stack is: 3
//Number Inserted: 2
//Number Inserted: 1
//Minimum Element in the stack is: 1
//Top Most Element Removed: 1
//Minimum Element in the stack is: 2
//Top Most Element Removed: 2
//Top Most Element is: 5
//Time complexity: O(1)
Video: link
------------------------------------------------x------------------x------------------x--------------x-------------------------------------