Project 1
Arrays
EQUILIBRIUM POINT
// 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));
}
}
// This code has been contributed by Mayank Jaiswal
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)-----------------------------------------------------------------------
String
REVERSE WORDS IN A GIVEN STRING
// Java program to
// reverse a String
import java.util.*;
class GFG {
// 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 ";
// Function call
char[] p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
// This code is contributed by gauravrajput1
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 GFG
{
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[] = "skilllync".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
// This code is contributed by Rajput-Ji
Output
skilync
Time Complexity: O(n * n)
Auxiliary Space: O(1), -----------------------------------------------------------------------------------------
LinkedList
FINDING MIDDLE ELEMENT IN A LINKED LIST
public class MiddleNode
{
Node head;
// Node class
class Node{
int key;
Node next;
Node(int data)
{
key = data;
next = null;
}
}
// Method for inserting node to the front
public void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
// Method for inserting a node at the last
public void insertAtLast(int data)
{
Node new_node = new Node(data);
if(head == null){
head = new_node;
return;
}
Node temp = head;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = new_node;
return;
}
// Method to get the count of number of nodes in the List
public int getCount()
{
int count = 0;
Node temp = head;
while(temp!= null)
{
count++;
temp = temp.next;
}
return count;
}
// Method to find the middle node of a linked list
public void findMiddleNode()
{
int count = getCount();
Node temp = head;
// If the number of nodes are even, then there are
// two middle nodes print the first middle node
if(count%2 == 0)
{
int i = (count/2) - 1;
while(i != 0)
{
temp = temp.next;
i--;
}
System.out.println(temp.key);
}
// If the number of nodes are even
else{
int i = (count/2);
while(i != 0)
{
temp = temp.next;
i--;
}
System.out.println(temp.key);
}
}
// A utility method to print the Linked List
public void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.key + " ");
temp = temp.next;
}
}
public static void main(String []args)
{
MiddleNode ll = new MiddleNode();
// Making a linked list of odd number of nodes
// 1->2->3->4->5->NULL
ll.push(1);
ll.insertAtLast(2);
ll.insertAtLast(3);
ll.insertAtLast(4);
ll.insertAtLast(5);
System.out.println("Printing the original Linked List");
ll.printList();
System.out.println("\nThe middle node of a Linked list is");
ll.findMiddleNode();
// Making a linked list of even number of nodes
// 10->20->30->40->50->60->NULL
ll = new MiddleNode();
ll.push(2);
ll.insertAtLast(4);
ll.insertAtLast(6);
ll.insertAtLast(7);
ll.insertAtLast(5);
ll.insertAtLast(1);
System.out.println("Printing the original Linked List");
ll.printList();
System.out.println("\nThe middle node of a Linked list is");
ll.findMiddleNode();
}
}
out put
Printing the original Linked List
1 2 3 4 5
The middle node of a Linked list is
3
Printing the original Linked List
2 4 6 7 5 1
The middle node of a Linked list is
7
----------------------------------------------------------------------------------------
REVERSE A LINKED LIST
// Java program for reversing the linked list
class LinkedList {
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)
{
LinkedList list = new LinkedList();
list.head = new Node(20->);
list.head.next = new Node(40->);
list.head.next.next = new Node(60->);
list.head.next.next.next = new Node(70->);
list.head.next.next.next.next = new Node(50->);
list.head.next.next.next.next.next = new Node(10);
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
20->40->60->70->50->10
reversed linked list
10->50->70->60->40->20
Time Complexity: O(N)
Auxiliary Space: O(1)-----------------------------------------------------------------------------------------
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(8);
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(2);
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();
}
}
/* This code is contributed by Rajat Mishra */
Output
Linked list before calling pairWiseSwap()
1 2 2 4 5 6 7 8
Linked list after calling pairWiseSwap()
2 1 4 2 6 5 8 7
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(4);
list.head1.next = new Node(5);
System.out.print("First list is ");
list.printList(head1);
// creating second list
list.head2 = new Node(3);
list.head2.next = new Node(4);
list.head2.next.next = new Node(5);
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);
}
// this code is contributed by *Saurabh321Gupta*
}
Output
4 5
3 4 5
Resultant list is 3 9 0
Time Complexity: O(m + n),
Auxiliary Space: O(m + n), --------------------------------------------------------------------------------
Trees
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);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Output
25 12 30 10 36 15
Time Complexity: O(N)
Auxiliary Space: O(N)---------------------------------------------------------------------------------------
Graph
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);
}
}
// Contributed by Aakash Hasija
Output
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1
Time Complexity: O(V * E)
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 GfG
{
// 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 > arrpos =
new ArrayList > ();
for (int i = 0; i < n; i++)
arrpos.add(new Pair <Integer,
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<Pair<Integer,
Integer>>()
{
@Override
public int compare(Pair<Integer, Integer> o1,
Pair<Integer, Integer> o2)
{
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));
}
}
// This code is contributed by Saksham Seth
Output
2
Time Complexity: O(n Log n)
Auxiliary Space: O(n)
--------------------------------------------------------------------------------------------
Stacks Queues
GET MINIMUM ELEMENT FROM STACK
import java.io.*;
import java.util.*;
public class MinStack {
Stack<Node> s;
class Node {
int val;
int min;
public Node(int val, int min)
{
this.val = val;
this.min = min;
}
}
/** initialize your data structure here. */
public MinStack() { this.s = new Stack<Node>(); }
public void push(int x)
{
if (s.isEmpty()) {
this.s.push(new Node(x, x));
}
else {
int min = Math.min(this.s.peek().min, x);
this.s.push(new Node(x, min));
}
}
public int pop() { return this.s.pop().val; }
public int top() { return this.s.peek().val; }
public int getMin() { return this.s.peek().min; }
}
// Driver code
class GFG {
public static void main(String[] args)
{
MinStack s = new MinStack();
// Function calls
s.push(2);
s.push(3);
s.push(1);
System.out.println(s.getMin());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.getMin());
}
}
Output:
321
Time Complexity: O(n)
Auxiliary Space: O(n)--------------------------------------------------------------------------------------------------------------