Project 1
Project 1
/ Java program to find equilibrium
// index of an array
class EquilibriumIndex {
int equilibrium(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
/* Check for indexes one by one until
an equilibrium index is found */
for (i = 0; i < n; ++i) {
/* get left sum */
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];
/* get right sum */
rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
/* if leftsum and rightsum are same,
then we are done */
if (leftsum == rightsum)
return i;
}
/* return -1 if no equilibrium index is found */
return -1;
}
// Driver code
public static void main(String[] args)
{
EquilibriumIndex equi = new EquilibriumIndex();
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = arr.length;
// Function call
System.out.println(equi.equilibrium(arr, arr_size));
}
}
Output
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
LEADERS IN AN ARRAY
class LeadersInArray
{
/*Java Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i + 1; j < size; j++)
{
if (arr[i] <=arr[j])
break;
}
if (j == size) // the loop didn't break
System.out.print(arr[i] + " ");
}
}
/* Driver program to test above functions */
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
Output
17 5 2
Time Complexity: O(N * N)
Auxiliary Space: O(1)
REVERSE WORDS IN A GIVEN STRING
/ Java program to
// reverse a String
import java.util.*;
class Reverse{
// Reverse the letters
// of the word
static void reverse(char str[],
int start,
int end)
{
// Temporary variable
// to store character
char temp;
while (start <= end)
{
// Swapping the first
// and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Function to reverse words
static char[] reverseWords(char []s)
{
// Reversing individual words as
// explained in the first step
int start = 0;
for (int end = 0; end < s.length; end++)
{
// If we see a space, we
// reverse the previous
// word (word between
// the indexes start and end-1
// i.e., s[start..end-1]
if (s[end] == ' ')
{
reverse(s, start, end);
start = end + 1;
}
}
// Reverse the last word
reverse(s, start, s.length - 1);
// Reverse the entire String
reverse(s, 0, s.length - 1);
return s;
}
// Driver Code
public static void main(String[] args)
{
String s = "i like this program very much ";
char []p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
Output
much very program this like i
Time complexity: O(N)
Auxiliary Space: O(N)
REMOVE DUPLICATES
// Java program to remove duplicate character
// from character array and print in sorted
// order
import java.util.*;
class Duplicate
{
static String removeDuplicate(char str[], int n)
{
// Used as index in the modified string
int index = 0;
// Traverse through all characters
for (int i = 0; i < n; i++)
{
// Check if str[i] is present before it
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}
// If not present, then add it to
// result.
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
// Driver code
public static void main(String[] args)
{
char str[] = "geeksforgeeks".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
Output:
geksfor
Time Complexity: O(n * n)
Auxiliary Space: O(1)
FINDING MIDDLE ELEMENT IN A LINKED LIST
/ Java Program for the above approach
class Middle_Element {
Node head;
/*Creating a new Node*/
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
/*Function to add a new Node*/
public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
/*Displaying the elements in the list*/
public void printNode()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.print("Null"+"\n");
}
/*Finding the length of the list.*/
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
/*Printing the middle element of the list.*/
public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print("The middle element is ["
+ temp.data + "]");
System.out.println();
}
}
public static void main(String[] args)
{
GFG list = new GFG();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
list.printNode();
list.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) where n is no of nodes in linked list
PAIRWISE SWAP ELEMENTS OF A LINKED LIST
// Java program to pairwise swap elements of a linked list
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
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[])
{
LinkedList llist = new LinkedList();
/* 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)
As we traverse the linked list only once.
Auxiliary Space: O(1)
As constant extra space is used.
ADD TWO NUMBERS REPRESENTED BY LINKED LISTS
// Java program to add two numbers
// represented by linked list
class LinkedList {
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) {
LinkedList list = new LinkedList();
// 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), where m and n are numbers of nodes in first and second lists respectively. The lists need to be traversed only once.
Auxiliary Space: O(m + n), A temporary linked list is needed to store the output number
BINARY TREE TO DLL
// A Java program for in-place conversion of Binary Tree to DLL
// A binary tree node has data, left pointers and right pointers
class Node
{
int data;
Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
class BinaryTree
{
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
BinaryTree tree = new BinaryTree();
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
Note: The use of static variables like above is not a recommended practice, here static is used for simplicity. Imagine if the same function is called for two or more trees. The old value of prev would be used in the next call for a different tree. To avoid such problems, we can use a double-pointer or a reference to a pointer.
Time Complexity: O(N), The above program does a simple inorder traversal, so time complexity is O(N) where N is the number of nodes in a given Binary tree.
Auxiliary Space: O(N), For recursion call stack.
BELLMAN FORD ALGORITHM
// A Java program for Bellman-Ford's single source shortest
// path algorithm.
import java.io.*;
import java.lang.*;
import java.util.*;
// A class to represent a connected, directed and weighted
// graph
class Graph {
// 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
Graph(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(Graph 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's code
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(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 B-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;
// Function call
graph.BellmanFord(graph, 0);
}
}
Output
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1
Time Complexity: O(V * E), where V is the number of vertices in the graph and E is the number of edges in the graph
Auxiliary Space: O(E)
MINIMUM SWAPS TO SORT
// Java program to find
// minimum number of swaps
// required to sort an array
import javafx.util.Pair;
import java.util.ArrayList;
import java.util.*;
class Swaps
{
// Function returns the
// minimum number of swaps
// required to sort the array
public static int minSwaps(int[] arr)
{
int n = arr.length;
// Create two arrays and
// use as pairs where first
// array is element and second array
// is position of first element
ArrayList
new ArrayList
Integer> > ();
for (int i = 0; i < n; i++)
arrpos.add(new Pair
Integer> (arr[i], i));
// Sort the array by array element values to
// get right position of every element as the
// elements of second array.
arrpos.sort(new Comparator
Integer>>()
{
@Override
public int compare(Pair
Pair
{
if (o1.getKey() > o2.getKey())
return -1;
// We can change this to make
// it then look at the
// words alphabetical order
else if (o1.getKey().equals(o2.getKey()))
return 0;
else
return 1;
}
});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
Boolean[] vis = new Boolean[n];
Arrays.fill(vis, false);
// Initialize result
int ans = 0;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrpos.get(i).getValue() == i)
continue;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = true;
// move to next node
j = arrpos.get(j).getValue();
cycle_size++;
}
// Update answer by adding current cycle.
if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
// Return result
return ans;
}
}
// Driver class
class MinSwaps
{
// Driver program to test the above function
public static void main(String[] args)
{
int []a = {1, 5, 4, 3, 2};
GfG g = new GfG();
System.out.println(g.minSwaps(a));
}
}
Output
2
Time Complexity: O(n Log n)
Auxiliary Space: O(n)
GET MINIMUM ELEMENT FROM STACK
/ Java program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
import java.util.*;
// A user defined stack that supports getMin() in
// addition to push() and pop()
class MyStack {
Stack
Integer minEle;
// Constructor
MyStack() { s = new Stack
// 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);
}
};
// Driver Code
public class Main {
public static void main(String[] args)
{
MyStack s = new MyStack();
// Function calls
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