SEBI CODING PAPER

1. Sorting :-
1. BubbleSort -
void bubbleSort(int arr[])
{
int n = [Link];
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}

2. SelectionSort -
void sort(int arr[])
{
int n = [Link];
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++){
if (arr[j] < arr[min_idx]) {
min_idx = j;
} }
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

3. InserationSort -
void sort(int arr[])
{
int n = [Link];
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
 of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

4. QuickSort -
static int partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}

static void quickSort(int[] arr, int low, int high)

{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

[Link] -
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];

/*Copy data to temp arrays*/

for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
 for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays */

int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void sort(int arr[], int l, int r)

{
if (l < r) {
int m =l+ (r-l)/2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

6. HeapSort -

public void sort(int arr[])

{
int N = [Link];

// Build heap (rearrange array)

for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
 for (int i = N - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

void heapify(int arr[], int N, int i)

{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < N && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < N && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, N, largest);
}
}

2. Searching -

1. BinarySearch -
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1; }
Kth Smallest Element in the Array : Best time complexity -

static void swap(int[] arr, int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int l, int r) {
int pivot = r;
int j = l;
//swap(arr, pivot, r);
for(int i = l ; i < r; i++) {
if(arr[i] < arr[r]) {
swap(arr, i, j);
j++;
}
}
swap(arr, j, r);
return j;
}
static int quickselect(int[] arr, int l, int r, int k) {
int m = partition(arr, l, r);
if (m == k - 1)
return arr[m];
else if (m < k - 1)
return quickselect(arr, m + 1, r, k);
 else
return quickselect(arr, l, m - 1, k);
}

Reverse LinkedList -
reverse singly linked list -
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = [Link];
[Link] = prev;
prev = current;
current = next;
}
node = prev;
return node;
}

reverse doubly linked list -

void reverse()
{
Node temp = null;
Node current = head;

while (current != null) {

temp = [Link];
[Link] = [Link];
[Link] = temp;
current = [Link];
}
if (temp != null) {
head = [Link];
}
}
The Stock Span Problem
The stock span problem is a financial problem where we have a series of n daily price quotes for a
stock and we need to calculate the span of the stock’s price for all n days. The span Si of the stock’s
price on a given day i is defined as the maximum number of consecutive days just before the given
day, for which the price of the stock on the current day is less than its price on the given day.

static void calculateSpan(int price[], int n, int S[])

{
// Span value of first day is always 1
S[0] = 1;
//Calculate span value of remaining days by linearly checking
previous days
for (int i = 1; i < n; i++) {
S[i] = 1; // Initialize span value
for (int j = i - 1; (j >= 0) && (price[i] >= price[j]);j--)
S[i]++;
}
}

PostFix Expression Evolution -

static int evaluatePostfix(String exp)

{
Stack<Integer> stack=new Stack<>();
for(int i=0;i<[Link]();i++)
{
char c=[Link](i);

// If the scanned character is an operand (number

here),
// push it to the stack.
if([Link](c))
[Link](c - '0');

// If the scanned character is an operator, pop two

// elements from stack apply the operator
else
{
int val1 = [Link]();
int val2 = [Link]();

switch(c)
{
case '+':
[Link](val2+val1);
break;
 case '-':
[Link](val2- val1);
break;

case '/':
[Link](val2/val1);
break;

case '*':
[Link](val2*val1);
break;
}
}
}
return [Link]();
}

Parathensis are Balanced or Not :

static boolean ispar(String x)
{
Stack<Character> sc = new Stack<>();
for(int i=0;i<[Link]();i++)
{
char ch = [Link](i);
if(ch == '{' || ch == '(' || ch == '[' )
{
[Link](ch);
continue;
}
if([Link]())
return false;
char check;
switch(ch)
{
case ')':
check = [Link]();
 if(check == '[' || check == '{' )
return false;
break;
case ']':
check = [Link]();
if(check == '(' || check == '{' )
return false;
break;
case '}':
check = [Link]();
if(check == '[' || check == '(' )
return false;
break;

}
}
if([Link]())
return true;
else return false;
}

Tower of Hanoi Problem ::

static void towerOfHanoi(int n, char from_rod,
char to_rod, char aux_rod)
{
if (n == 0) {
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
[Link]("Move disk " + n + " from rod "
+ from_rod + " to rod "
+ to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

// Driver code
public static void main(String args[])
 {
int N = 3;

// A, B and C are names of rods

towerOfHanoi(N, 'A', 'C', 'B');
}

Merge to Sorted Linked List :

public Node SortedMerge(Node A, Node B)

{

if(A == null) return B;

if(B == null) return A;

if([Link] < [Link])

{
[Link] = SortedMerge([Link], B);
return A;
}
else
{
[Link] = SortedMerge(A, [Link]);
return B;
}

or using a dummy node --

Node sortedMerge(Node headA, Node headB)
{

/* a dummy first node to

hang the result on */
Node dummyNode = new Node(0);

/* tail points to the

last result node */
Node tail = dummyNode;
while(true)
{

/* if either list runs out,

use the other list */
if(headA == null)
 {
[Link] = headB;
break;
}
if(headB == null)
{
[Link] = headA;
break;
}

if([Link] <= [Link])

{
[Link] = headA;
headA = [Link];
}
else
{
[Link] = headB;
headB = [Link];
}

/* Advance the tail */

tail = [Link];
}
return [Link];
}

Rotate the Matrix in clockwise direction ::

static void rotatematrix(int m,int n, int mat[][])

{
int row = 0, col = 0;
int prev, curr;

/*
row - Starting row index
m - ending row index
col - starting column index
n - ending column index
i - iterator
*/
while (row < m && col < n)
{

if (row + 1 == m || col + 1 == n)
break;

// Store the first element of next

// row, this element will replace
// first element of current row
 prev = mat[row + 1][col];

// Move elements of first row

// from the remaining rows
for (int i = col; i < n; i++)
{
curr = mat[row][i];
mat[row][i] = prev;
prev = curr;
}
row++;

// Move elements of last column

// from the remaining columns
for (int i = row; i < m; i++)
{
curr = mat[i][n-1];
mat[i][n-1] = prev;
prev = curr;
}
n--;

// Move elements of last row

// from the remaining rows
if (row < m)
{
for (int i = n-1; i >= col; i--)
{
curr = mat[m-1][i];
mat[m-1][i] = prev;
prev = curr;
}
}
m--;

// Move elements of first column

// from the remaining rows
if (col < n)
{
for (int i = m-1; i >= row; i--)
{
curr = mat[i][col];
mat[i][col] = prev;
prev = curr;
}
}
col++;
}

// Print rotated matrix

for (int i = 0; i < R; i++)
{
 for (int j = 0; j < C; j++)
[Link]( mat[i][j] + " ");
[Link]("\n");
}
}

Binary Tree :

Insertion :
static void insert(Node temp, int key)
{

if (temp == null) {
root = new Node(key);
return;
}
Queue<Node> q = new LinkedList<Node>();
[Link](temp);

// Do level order traversal until we find

// an empty place.
while (![Link]()) {
temp = [Link]();
[Link]();

if ([Link] == null) {
[Link] = new Node(key);
break;
}
else
[Link]([Link]);

if ([Link] == null) {
[Link] = new Node(key);
break;
}
else
[Link]([Link]);
}
}

Delete Node in Binary Tree – Replace the node to be

deleted with the deepest node in the tree and delete
the deepest node the tree.
// Function to delete deepest
// element in binary tree
static void deleteDeepest(Node root,
Node delNode)
{
Queue<Node> q = new LinkedList<Node>();
[Link](root);

Node temp = null;

// Do level order traversal until last node

while (![Link]())
{
temp = [Link]();
[Link]();

if (temp == delNode)
{
temp = null;
return;

}
if ([Link]!=null)
{
if ([Link] == delNode)
{
[Link] = null;
return;
}
else
[Link]([Link]);
}

if ([Link] != null)
{
if ([Link] == delNode)
{
[Link] = null;
return;
}
else
[Link]([Link]);
}
}
}

// Function to delete given element

// in binary tree
static void delete(Node root, int key)
{
if (root == null)
 return;
if ([Link] == null && [Link] == null)
{
if ([Link] == key)
{
root=null;
return;
}
else
return;
}
Queue<Node> q = new LinkedList<Node>();
[Link](root);
Node temp = null, keyNode = null;

// Do level order traversal until

// we find key and last node.
while (![Link]())
{
temp = [Link]();
[Link]();
if ([Link] == key)
keyNode = temp;
if ([Link] != null)
[Link]([Link]);
if ([Link] != null)
[Link]([Link]);
}

if (keyNode != null)
{
int x = [Link];
deleteDeepest(root, temp);
[Link] = x;
}
}

Level Order Traversal Sprial Form – Using Two

Stacks

void printSpiral(Node node)

{
if (node == null)
return; // NULL check

// Create two stacks to store alternate levels

// For levels to be printed from right to left
Stack<Node> s1 = new Stack<Node>();
// For levels to be printed from left to right
Stack<Node> s2 = new Stack<Node>();
 // Push first level to first stack 's1'
[Link](node);

// Keep printing while any of the stacks has some nodes

while (![Link]() || ![Link]()) {
// Print nodes of current level from s1 and push nodes
of
// next level to s2
while (![Link]()) {
Node temp = [Link]();
[Link]();
[Link]([Link] + " ");

// Note that is right is pushed before left

if ([Link] != null)
[Link]([Link]);

if ([Link] != null)
[Link]([Link]);
}

// Print nodes of current level from s2 and push nodes

of
// next level to s1
while (![Link]()) {
Node temp = [Link]();
[Link]();
[Link]([Link] + " ");

// Note that is left is pushed before right

if ([Link] != null)
[Link]([Link]);
if ([Link] != null)
[Link]([Link]);
}
}
}

Binary Tree Boundary Traversal -

1. print root first and then
2. print left boundary
3. print leaves from left to right
4. print right boundary in bottom up
passion
void printLeaves(Node node)
{
if (node == null)
return;

printLeaves([Link]);
// Print it if it is a leaf node
if ([Link] == null && [Link] == null)
[Link]([Link] + " ");
printLeaves([Link]);
}

// A function to print all left boundary nodes, except a leaf

node.
// Print the nodes in TOP DOWN manner
void printBoundaryLeft(Node node)
{
if (node == null)
return;

if ([Link] != null) {
// to ensure top down order, print the node
// before calling itself for left subtree
[Link]([Link] + " ");
printBoundaryLeft([Link]);
}
else if ([Link] != null) {
[Link]([Link] + " ");
printBoundaryLeft([Link]);
}

// do nothing if it is a leaf node, this way we avoid

// duplicates in output
}

// A function to print all right boundary nodes, except a leaf

node
// Print the nodes in BOTTOM UP manner
void printBoundaryRight(Node node)
{
if (node == null)
return;

if ([Link] != null) {
// to ensure bottom up order, first call for right
// subtree, then print this node
printBoundaryRight([Link]);
[Link]([Link] + " ");
}
else if ([Link] != null) {
printBoundaryRight([Link]);
[Link]([Link] + " ");
 }
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}

// A function to do boundary traversal of a given binary tree

void printBoundary(Node node)
{
if (node == null)
return;

[Link]([Link] + " ");

// Print the left boundary in top-down manner.

printBoundaryLeft([Link]);

// Print all leaf nodes

printLeaves([Link]);
printLeaves([Link]);

// Print the right boundary in bottom-up manner

printBoundaryRight([Link]);
}

Greedy Algorithms: Kruskal’s Minimum Spanning Tree Algorithm,

Huffman Coding,Prim’s Minimum Spanning Tree Algorithm,Dijkstra’s
Shortest Path Algorithm, Job Sequencing Problem, Greedy Algorithm
to find Minimum number of Coins, K Centers Problem, Minimum Number of
Platforms Required for a Railway/Bus Station

Dynamic Programming: Longest Increasing Subsequence, Longest Common Subsequence, Edit

Distance, Min Cost Path, Coin Change , Matrix Chain Multiplication, Binomial
Coefficient, 0-1 Knapsack Problem, Egg Dropping Puzzle, Longest Palindromic
Subsequence, Maximum Sum Increasing Subsequence, Cutting a Rod, Maximum size square sub-
matrix with all 1s, Longest Palindromic Substring, Largest Sum Contiguous Subarray, Count ways
to reach the n’th stair

Divide and Conquer: Write your own pow(x, n) to calculate x*n,Median of two sorted arrays,
Count Inversions, Closest Pair of Points, Strassen’s Matrix Multiplication

Pattern Searching:
Naive Pattern Searching,KMP Algorithm, Rabin-Karp Algorithm,
Finite Automata, Boyer Moore Algorithm – Bad Character Heuristic,
Suffix Array, Anagram Substring Search (Or Search for all
permutations), Pattern Searching using a Trie of all Suffixes,
Aho-Corasick Algorithm for Pattern Searching, kasai’s Algorithm
for Construction of LCP array from Suffix Array
Backtracking: Print all permutations of a given string, The
Knight’s tour problem, Rat in a Maze, N Queen Problem, Subset Sum,
m Coloring Problem, Hamiltonian Cycle, Sudoku, Tug of War

------------------------------------------------------------------
------------------------------------------------------------------

Binary Search Tree :

Search ::
public Node search(Node root, int key)
{
// Base Cases: root is null or key is present at root
if (root==null || [Link]==key)
return root;

// Key is greater than root's key

if ([Link] < key)
return search([Link], key);

// Key is smaller than root's key

return search([Link], key);
}

Insertion :
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to
insert a new key in BST */
Node insertRec(Node root, int key)
{

/* If the tree is empty,

return a new node */
if (root == null) {
root = new Node(key);
return root;
}

/* Otherwise, recur down the tree */

 else if (key < [Link])
[Link] = insertRec([Link], key);
else if (key > [Link])
[Link] = insertRec([Link], key);

/* return the (unchanged) node pointer */

return root;
}

Deletion ::
void deleteKey(int key)
{ root = deleteRec(root, key); }

/* A recursive function to
delete an existing key in BST
*/
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null)
return root;

/* Otherwise, recur down the tree */

if (key < [Link])
[Link] = deleteRec([Link], key);
else if (key > [Link])
[Link] = deleteRec([Link], key);

// if key is same as root's

// key, then This is the
// node to be deleted
else {
// node with only one child or no child
if ([Link] == null)
return [Link];
else if ([Link] == null)
return [Link];

// node with two children: Get the inorder

// successor (smallest in the right subtree)
[Link] = minValue([Link]);

// Delete the inorder successor

[Link] = deleteRec([Link], [Link]);
}

return root;
}
 int minValue(Node root)
{
int minv = [Link];
while ([Link] != null)
{
minv = [Link];
root = [Link];
}
return minv;
}

------------------------------------------------------------------
------------------------------------------------------------------

BackTracking :

1 . SNAKE and LADDER :

import [Link];
import [Link];
import [Link];
import [Link];
public static void main(String[] args) {
SnakeNLadder s = new SnakeNLadder();
[Link]();
}
}
class SnakeNLadder
{
final static int WINPOINT = 100;

static Map<Integer,Integer> snake = new HashMap<Integer,Integer>();

static Map<Integer,Integer> ladder = new HashMap<Integer,Integer>();
{
[Link](99,54);
[Link](70,55);
[Link](52,42);
[Link](25,2);
[Link](95,72);
[Link](6,25);
[Link](11,40);
[Link](60,85);
[Link](46,90);
[Link](17,69);
}

public int rollDice()

{
int n = 0;
Random r = new Random();
n=[Link](7);
return (n==0?1:n);
}
public void startGame()
{
int player1 =0, player2=0;
int currentPlayer=-1;
Scanner s = new Scanner([Link]);
String str;
int diceValue =0;
do
{
[Link](currentPlayer==-1?"\n\nFIRST PLAYER TURN":"\n\nSECOND PLAYER
TURN");
[Link]("Press r to roll Dice");
str = [Link]();
diceValue = rollDice();

if(currentPlayer == -1)
{
player1 = calculatePlayerValue(player1,diceValue);
[Link]("First Player :: " + player1);
[Link]("Second Player :: " + player2);
[Link]("------------------");
if(isWin(player1))
{
[Link]("First player wins");
return;
}
}
else
{
player2 = calculatePlayerValue(player2,diceValue);
[Link]("First Player :: " + player1);
[Link]("Second Player :: " + player2);
[Link]("------------------");
if(isWin(player2))
{
[Link]("Second player wins");
return;
}
}
currentPlayer= -currentPlayer;

}while("r".equals(str));
}

public int calculatePlayerValue(int player, int diceValue)

{
player = player + diceValue;
if(player > WINPOINT)
{
player = player - diceValue;
return player;
}
if(null!=[Link](player))
{
[Link]("swallowed by snake");
player= [Link](player);
}
if(null!=[Link](player))
{
[Link]("climb up the ladder");
player= [Link](player);
}
return player;
}
public boolean isWin(int player)
{
return WINPOINT == player;
}
}

------------------------------------------------------------------------------------------------------------------------
SoDoku Problem ::
public class Sudoku {
// N is the size of the 2D matrix N*N
static int N = 9;

/* Takes a partially filled-in grid and attempts

to assign values to all unassigned locations in
such a way to meet the requirements for
Sudoku solution (non-duplication across rows,
columns, and boxes) */
static boolean solveSudoku(int grid[][], int row,
int col)
{

/*if we have reached the 8th

row and 9th column (0
indexed matrix) ,
we are returning true to avoid further
backtracking */
if (row == N - 1 && col == N)
return true;

// Check if column value becomes 9 ,

// we move to next row
// and column start from 0
if (col == N) {
row++;
col = 0;
}

// Check if the current position

// of the grid already
// contains value >0, we iterate
// for next column
 if (grid[row][col] != 0)
return solveSudoku(grid, row, col + 1);

for (int num = 1; num < 10; num++) {

// Check if it is safe to place

// the num (1-9) in the
// given row ,col ->we move to next column
if (isSafe(grid, row, col, num)) {

/* assigning the num in the current

(row,col) position of the grid and
assuming our assigned num in the position
is correct */
grid[row][col] = num;

// Checking for next

// possibility with next column
if (solveSudoku(grid, row, col + 1))
return true;
}
/* removing the assigned num , since our
assumption was wrong , and we go for next
assumption with diff num value */
grid[row][col] = 0;
}
return false;
}

/* A utility function to print grid */

static void print(int[][] grid)
{
 for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
[Link](grid[i][j] + " ");
[Link]();
}
}

// Check whether it will be legal

// to assign num to the
// given row, col
static boolean isSafe(int[][] grid, int row, int col,
int num)
{

// Check if we find the same num

// in the similar row , we
// return false
for (int x = 0; x <= 8; x++)
if (grid[row][x] == num)
return false;

// Check if we find the same num

// in the similar column ,
// we return false
for (int x = 0; x <= 8; x++)
if (grid[x][col] == num)
return false;

// Check if we find the same num

// in the particular 3*3
// matrix, we return false
int startRow = row - row % 3, startCol = col - col % 3;
 for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow][j + startCol] == num)
return false;

return true;
}

// Driver Code
public static void main(String[] args)
{
int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
{ 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 },
{ 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 },
{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };

if (solveSudoku(grid, 0, 0))
print(grid);
else
[Link]("No Solution exists");
}
// This is code is contributed by Pradeep Mondal P
}
------------------------------------------------------------------------------------------------------------------------

Integer to Roman -
public class IntegerToRoman
{
public static void intToRoman(int num)
{
[Link]("Integer: " + num);
int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] romanLetters = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

StringBuilder roman = new StringBuilder();

for(int i=0;i<[Link];i++)
{
while(num >= values[i])
{
num = num - values[i];
[Link](romanLetters[i]);
}
}
[Link]("Corresponding Roman Numerals is: " + [Link]());
}
public static void main(String args[])
{
intToRoman(125);
intToRoman(252);
intToRoman(1000);
intToRoman(1010);
}
}
---------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------

Roman to Integer ::

1. import [Link].*;
1. import [Link].*;
2. public class RomanToInteger2
3. {
4. public static void convertRomanToInt(String s)
5. {
6. Map<Character, Integer> map=new HashMap<Character, Integer>();
7. //adding elements to the Map
8. [Link]('I',1);
9. [Link]('V',5);
10. [Link]('X',10);
 11. [Link]('L',50);
12. [Link]('C',100);
13. [Link]('D',500);
14. [Link]('M',1000);
15. s = [Link]("IV","IIII");
16. s = [Link]("IX","VIIII");
17. s = [Link]("XL","XXXX");
18. s = [Link]("XC","LXXXX");
19. s = [Link]("CD","CCCC");
20. s = [Link]("CM","DCCCC");
21. int number = 0;
22. //loop iterates over the roman numeral
23. for (int i = 0; i < [Link](); i++)
24. {
25. //getting each character of roman numeral and adding it to the variable number
26. number = number + ([Link]([Link](i)));
27. }
28. //prints the corresponding integer value
29. [Link]("The corresponding Integer value is: "+number);
30.}
31. //driver code
32. public static void main (String args[])
33. {
34. //function calling
35. convertRomanToInt("MCMXV");
36. }
37.}
38.}

-------------------------------------------------------------------------------------------------------
Form Maximum number from given Digit --
class GFG {

// The main function that prints the

// arrangement with the largest value.
// The function accepts a vector of strings
static void printLargest(Vector<String> arr)
{

[Link](arr, new Comparator<String>()

{
// A comparison function which is used by
// sort() in printLargest()
@Override public int compare(String X, String Y)
{

// first append Y at the end of X

 String XY = X + Y;

// then append X at the end of Y

String YX = Y + X;

// Now see which of the two

// formed numbers
// is greater
return [Link](YX) > 0 ? -1 : 1;
}
});

Iterator it = [Link]();

while ([Link]())
[Link]([Link]());
}

// Driver code
public static void main(String[] args)
{

Vector<String> arr;
arr = new Vector<>();

// output should be 6054854654

[Link]("54");
[Link]("546");
[Link]("548");
[Link]("60");
printLargest(arr);
}
}

-------------------------------------------------------------------------------------------------------
For Calendar problem -
Use map -
Start for year count from given year to -1.
Years No. of odd
Ordinary year 1
Leap year 2
100 years 5
200 years 3
300 years 1
400 years 0
month – 31 – 3
30 – 2
28 – 0
29 – 1
Leap year – feb 29 - 1
Ordinary year – feb 28 - 0

Day of week No. of odd

Sunday 0
Monday 1
Tuesday 2
Wednesday 3
Thursday 4
Friday 5
Saturday 6

-------------------------------------------------------------------------------------------------------
Tree Problem :
Binary Tree -
To get any order , we always need -
1. Inorder and preorder 2. Inorder and postorder
1.
public class PrintPost {
static int preIndex = 0;
void printPost(int[] in, int[] pre, int inStrt, int inEnd)
{
if (inStrt > inEnd)
return;

// Find index of next item in preorder traversal in

// inorder.
int inIndex = search(in, inStrt, inEnd, pre[preIndex++]);

// traverse left tree

printPost(in, pre, inStrt, inIndex - 1);
 // traverse right tree
printPost(in, pre, inIndex + 1, inEnd);

// print root node at the end of traversal

[Link](in[inIndex] + " ");
}

int search(int[] in, int startIn, int endIn, int data)

{
int i = 0;
for (i = startIn; i < endIn; i++)
if (in[i] == data)
return i;
return i;
}

// Driver code
public static void main(String ars[])
{
int in[] = { 4, 2, 5, 1, 3, 6 };
int pre[] = { 1, 2, 4, 5, 3, 6 };
int len = [Link];
PrintPost tree = new PrintPost();
[Link](in, pre, 0, len - 1);
}
}

Post Order in BST -

import [Link].*;

class Solution {
static class INT {
int data;
INT(int d) { data = d; }
}

// Function to find postorder traversal from

// preorder traversal.
static void findPostOrderUtil(int pre[], int n,
int minval, int maxval,
INT preIndex)
{

// If entire preorder array is traversed then

// return as no more element is left to be
// added to post order array.
if ([Link] == n)
return;
 // If array element does not lie in range specified,
// then it is not part of current subtree.
if (pre[[Link]] < minval
|| pre[[Link]] > maxval) {
return;
}

// Store current value, to be printed later, after

// printing left and right subtrees. Increment
// preIndex to find left and right subtrees,
// and pass this updated value to recursive calls.
int val = pre[[Link]];
[Link]++;

// All elements with value between minval and val

// lie in left subtree.
findPostOrderUtil(pre, n, minval, val, preIndex);

// All elements with value between val and maxval

// lie in right subtree.
findPostOrderUtil(pre, n, val, maxval, preIndex);

[Link](val + " ");

}

// Function to find postorder traversal.

static void findPostOrder(int pre[], int n)
{

// To store index of element to be

// traversed next in preorder array.
// This is passed by reference to
// utility function.
INT preIndex = new INT(0);

findPostOrderUtil(pre, n, Integer.MIN_VALUE,
Integer.MAX_VALUE, preIndex);
}

// Driver code
public static void main(String args[])
{
int pre[] = { 40, 30, 35, 80, 100 };

int n = [Link];

// Calling function
findPostOrder(pre, n);
}
}
[Link]

2.
/* Java program to construct tree using inorder and
postorder traversals */
import [Link].*;
class GFG
{

/* A binary tree node has data, pointer to left

child and a pointer to right child */
static class Node
{
int data;
Node left, right;
};

// Utility function to create a new node

/* Helper function that allocates a new node */
static Node newNode(int data)
{
Node node = new Node();
[Link] = data;
[Link] = [Link] = null;
return (node);
}

/* Recursive function to construct binary of size n

from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
static Node buildUtil(int in[], int post[],
int inStrt, int inEnd)
{

// Base case
if (inStrt > inEnd)
return null;

/* Pick current node from Postorder traversal

using postIndex and decrement postIndex */
int curr = post[index];
Node node = newNode(curr);
(index)--;

/* If this node has no children then return */

if (inStrt == inEnd)
return node;

/* Else find the index of this node in Inorder

traversal */
int iIndex = [Link](curr);

/* Using index in Inorder traversal, con

 left and right subtrees */
[Link] = buildUtil(in, post, iIndex + 1,
inEnd);
[Link] = buildUtil(in, post, inStrt,
iIndex - 1);
return node;
}
static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
static int index;

// This function mainly creates an unordered_map, then

// calls buildTreeUtil()
static Node buildTree(int in[], int post[], int len)
{

// Store indexes of all items so that we

// we can quickly find later
for (int i = 0; i < len; i++)
[Link](in[i], i);

index = len - 1; // Index in postorder

return buildUtil(in, post, 0, len - 1 );
}

/* This function is here just to test */

static void preOrder(Node node)
{
if (node == null)
 return;
[Link]("%d ", [Link]);
preOrder([Link]);
preOrder([Link]);
}

// Driver code
public static void main(String[] args)
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = [Link];
Node root = buildTree(in, post, n);
[Link]("Preorder of the constructed tree : \n");
preOrder(root);
}
}

-------------------------------------------------------------------------------------------------------
// Java program to construct BST from given preorder traversal

import [Link].*;

// A binary tree node

class Node {

int data;
Node left, right;
 Node(int d) {
data = d;
left = right = null;
}
}

class BinaryTree {

// The main function that constructs BST from pre[]

Node constructTree(int pre[], int size) {

// The first element of pre[] is always root

Node root = new Node(pre[0]);

Stack<Node> s = new Stack<Node>();

// Push root
[Link](root);

// Iterate through rest of the size-1 items of given preorder array

for (int i = 1; i < size; ++i) {
Node temp = null;

/* Keep on popping while the next value is greater than

stack's top value. */
while (![Link]() && pre[i] > [Link]().data) {
temp = [Link]();
 }

// Make this greater value as the right child

// and push it to the stack
if (temp != null) {
[Link] = new Node(pre[i]);
[Link]([Link]);
}

// If the next value is less than the stack's top

// value, make this value as the left child of the
// stack's top node. Push the new node to stack
else {
temp = [Link]();
[Link] = new Node(pre[i]);
[Link]([Link]);
}
}

return root;
}

// A utility function to print inorder traversal of a Binary Tree

void printInorder(Node node) {
if (node == null) {
return;
}
printInorder([Link]);
 [Link]([Link] + " ");
printInorder([Link]);
}

// Driver program to test above functions

public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{10, 5, 1, 7, 40, 50};
int size = [Link];
Node root = [Link](pre, size);
[Link]("Inorder traversal of the constructed tree is ");
[Link](root);
}
}
Inorder traversal of the constructed tree:
1 5 7 10 40 50

[Link]

-------------------------------------------------------------------------------------------------------
to reach up to number K.
* Add one to the operand
• Multiply the operand by 2.

class GFG{

// Function to find minimum operations

static int minOperation(int k)
{

// dp is initialised
// to store the steps
int dp[] = new int[k + 1];
 for(int i = 1; i <= k; i++)
{
dp[i] = dp[i - 1] + 1;

// For all even numbers

if (i % 2 == 0)
{
dp[i] = [Link](dp[i], dp[i / 2] + 1);
}
}
return dp[k];
}

// Driver Code
public static void main (String []args)
{
int K = 12;
[Link]( minOperation(K));
}
}

-------------------------------------------------------------------------------------------------------

Tree Right View --

void rightView(TreeNode node)
{
//add code here.
if(node==null)
return;

Queue<TreeNode> q=new LinkedList<TreeNode>();

[Link](node);
while(true)
{
int nodecount=[Link]();
if(nodecount==0)
 break;
int d=0;
while(nodecount>0)
{
TreeNode x=[Link]();
d=[Link];
[Link]();
if([Link]!=null)
[Link]([Link]);
if([Link]!=null)
[Link]([Link]);
nodecount--;
}
[Link](d+" ");
}

-------------------------------------------------------------------------------------------------------
Lowest Common Ancestor in a BST --

Node lca(Node node, int n1, int n2)

{
// Your code here
return lcabst(node,n1,n2);

}
Node lcabst(Node node,int n1,int n2)
{
if(node==null)
 return null;
if([Link]==n1 || [Link]==n2)
return node;
if([Link]>n1 && [Link]>n2)
return lcabst([Link],n1,n2);
else if( [Link]<n1 && [Link]<n2)
return lcabst([Link],n1,n2);
return node;
}

-------------------------------------------------------------------------------------------------------
LEFT View OF TREE ::
void leftView(Node root)
{
// Your code here
if(root==null)
return;

Queue<Node> q=new LinkedList<Node>();

[Link](root);
while([Link]()>0)
{
int n=[Link]();
if(n==0)
break;
int c=0;
Node x=null;
 while(n>0)
{
Node temp=[Link]();
if(c==0)
{
x=temp;
c=1;}
if([Link]!=null)
[Link]([Link]);
if([Link]!=null)
[Link]([Link]);

n--;
}
[Link]([Link]+" ");
}
}

------------------------------------------------------------------------------------------

Stack Related Problem ::

1. Infix to Postfix
2. Infix to Prefix ( just reverse the string and use same as Infix to Postfix )
Step 1: Reverse the infix expression i.e A+B*C will become C*B+A.
Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.
Just One change - while(![Link]() && ( prec(ch) < prec([Link]()) || ( prec(ch) <=
prec([Link]()) && ch=='^') ) ) { re+=[Link](); }
[Link](ch);
 • Step 2: Obtain the “nearly” postfix expression of the modified expression i.e CB*A+.
• Step 3: Reverse the postfix expression. Hence in our example prefix is +A*BC.

import [Link].*;

public class InToPost

{
public static void main(String arg[])
{
Scanner sc = new Scanner([Link]);

String in = [Link]();

StringBuffer sb = new StringBuffer(in);

sb = [Link]();

String in1 = [Link]();

String pre ="";
for(int i=0;i<[Link]();i++)
{
char ch = [Link](i);
if(ch == '(')
pre+=')';
if(ch == ')')
pre+='(';
else
{
pre+=ch;
}
}

Stack<Character> st= new Stack<>();

 String re = "";
for(int i=0;i<[Link]();i++)
{

char ch = [Link](i);
if([Link](ch))
{
re += ch;
}

else if(ch == '(')

{
[Link](ch);
}
else if(ch == ')')
{
while(![Link]() && [Link]()!='(')
{
re+=[Link]();
}
[Link]();
}
else
{
while(![Link]() && ( prec(ch) < prec([Link]()) || ( prec(ch) <= prec([Link]()) &&
ch=='^') ) )
{
re+=[Link]();

}
[Link](ch);
}
 }
while(![Link]())
{
if([Link]()=='(')
{
[Link]("Invalid");
}

re+=[Link]();
}

StringBuffer sb2= new StringBuffer(re);

[Link]([Link]());

public static int prec(char ch)

{
switch(ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;

}
 return -1;
}
}
1. Infix to Postfix
/* Java implementation to convert
infix expression to postfix*/
// Note that here we use ArrayDeque class for Stack
// operations

import [Link];
import [Link];
import [Link];

class Test {

// A utility function to return

// precedence of a given operator
// Higher returned value means
// higher precedence
static int Prec(char ch)
1. {
2. switch (ch) {
3. case '+':
4. case '-':
5. return 1;
6.
7. case '*':
8. case '/':
9. return 2;
10.
11. case '^':
12. return 3;
13. }
14. return -1;
15. }
static String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");

// initializing empty stack

Deque<Character> stack
= new ArrayDeque<Character>();

for (int i = 0; i < [Link](); ++i) {

char c = [Link](i);

// If the scanned character is an

// operand, add it to output.
if ([Link](c))
result += c;

// If the scanned character is an '(',

// push it to the stack.
else if (c == '(')
[Link](c);

// If the scanned character is an ')',

// pop and output from the stack
// until an '(' is encountered.
else if (c == ')') {
while (![Link]()
&& [Link]() != '(') {
result += [Link]();
[Link]();
}
 [Link]();
}
else // an operator is encountered
{
while (![Link]()
&& Prec(c) <= Prec([Link]())) {

result += [Link]();
[Link]();
}
[Link](c);
}
}

// pop all the operators from the stack

while (![Link]()) {
if ([Link]() == '(')
return "Invalid Expression";
result += [Link]();
[Link]();
}

return result;
}

// Driver's code
public static void main(String[] args)
{
String exp = "a+b*(c^d-e)^(f+g*h)-i";

// Function call
[Link](infixToPostfix(exp));
 }
}

3. Prefix to Infix -
Algorithm for Prefix to Infix:
• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator between them.
string = (operand1 + operator + operand2) -----------> Yhi DIFF HAI
And push the resultant string back to Stack
• Repeat the above steps until the end of Prefix expression.
• At the end stack will have only 1 string i.e resultant string
4. Prefix to PostFix -
Algorithm for Prefix to Postfix:
• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator after them.
string = operand1 + operand2 + operator -----------> Yhi DIFF HAI
And push the resultant string back to Stack
• Repeat the above steps until end of Prefix expression.

5. Postfix to Infix -
Algorithm for Postfix to Infix:
• Read the Postfix expression from left to right
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator before them.
string = operand2 + operator + operand1 -----------> Yhi DIFF HAI
( OP2 > OP1)
And push the resultant string back to Stack
• Repeat the above steps until end of Postfix expression.

6. PostFix to Prefix -
Algorithm for Postfix to Prefix:
• Read the Postfix expression from left to right
• If the symbol is an operand, then push it onto the Stack
 • If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator before them.
string = operator + operand2 + operand1 -----------> Yhi DIFF HAI
( OP2 > OP1)
And push the resultant string back to Stack
• Repeat the above steps until end of Postfix expression.

Matrix Related Problem :

1. Rorate matrix by 90 degree ( clockwise or anticlockwise )
1. Anticlockwise - 1. Find transpose 2. Reverse the column of matrix or 1. Reverse every row
and then 2. Find Transpose
2. Clockwise – Find Transpose . Revese the row of the matrix or 1. Reverse column and then
2. Transpose
For 180 degree – Do same step 2 times or Just Print the matrix from bottom side

------------------------------------------------------------------------------------------------------------------------
Rate in The MAZE - moment allowed – forward and down
/* Java program to solve Rat in
a Maze problem using backtracking */

public class RatMaze {

// Size of the maze

static int N;

/* A utility function to print

solution matrix sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
[Link](
" " + sol[i][j] + " ");
 [Link]();
}
}

/* A utility function to check

if x, y is valid index for N*N maze */
boolean isSafe(
int maze[][], int x, int y)
{
// if (x, y outside maze) return false
return (x >= 0 && x < N && y >= 0
&& y < N && maze[x][y] == 1);
}

/* This function solves the Maze problem using

Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = new int[N][N];

if (solveMazeUtil(maze, 0, 0, sol) == false) {

[Link]("Solution doesn't exist");
return false;
}

printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze

problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x, y is goal) return true
if (x == N - 1 && y == N - 1
&& maze[x][y] == 1) {
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid

if (isSafe(maze, x, y) == true) {
// Check if the current block is already part of solution path.
if (sol[x][y] == 1)
return false;

// mark x, y as part of solution path

sol[x][y] = 1;

/* Move forward in x direction */

if (solveMazeUtil(maze, x + 1, y, sol))
return true;

/* If moving in x direction doesn't give

solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
 /* If none of the above movements works then
BACKTRACK: unmark x, y as part of solution
path */
sol[x][y] = 0;
return false;
}

return false;
}

public static void main(String args[])

{
RatMaze rat = new RatMaze();
int maze[][] = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 } };

N = [Link];
[Link](maze);
}
}
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

------------------------------------------------------------------------------------------------------------------------
String Questions -
[Link](ch)
[Link](ch)
int i = [Link](i) - ‘A’ --- 1
int j = [Link](j) – ‘a’ --- 1
int k = [Link](k) – ‘0’ – 1
To Count only English Alphbhets - Create array of 26
To Count all the char – create array of 256
A – Z – 65- 90
a – z - 97 – 122
0 – 9 - 47 - 58
Category No of letters unmatched
Pangram 0( all 26 char should be there)
Lipogram >1
Pangrammatic Lipogram 1
Anagram (same number of char in both string in any order)
Paliandrome ( same order of char s1 and resverse s1 )

1. Replace all punctuation -

public static void main(String[] args)
{
// input string
String str = "Welcome???@@##$ to#$% Geeks%$^for$%^&Geeks";

// similar to [Link]
str = [Link]("\\p{Punct}","");

[Link](str);
}
Output = Welcome to GeeksforGeeks

2 . Rearrange the String such taht no two adjusent are same char
// Java program to rearrange characters in a string
// so that no two adjacent characters are same.
USE priority Queue -
import [Link].*;
import [Link].*;

class KeyComparator implements Comparator<Key> {

// Overriding compare()method of Comparator
public int compare(Key k1, Key k2)
{
if ([Link] < [Link])
return 1;
else if ([Link] > [Link])
return -1;
 return 0;
}
}
class Key {
int freq; // store frequency of character
char ch;
Key(int val, char c)
{
freq = val;
ch = c;
}
}

class GFG {
static int MAX_CHAR = 26;
// Function to rearrange character of a string
// so that no char repeat twice
static void rearrangeString(String str)
{
int n = [Link]();
// Store frequencies of all characters in string
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[[Link](i) - 'a']++;
// Insert all characters with their
// frequencies into a priority_queue
PriorityQueue<Key> pq
= new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c <= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0)
[Link](new Key(count[val], c));
}
// 'str' that will store resultant value
str = "";
// work as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev = new Key(-1, '#');
// traverse queue
while ([Link]() != 0) {
// pop top element from queue and
// add it to string.
Key k = [Link]();
[Link]();
str = str + [Link];
// If frequency of previous character
// is less than zero that means it is
// useless, we need not to push it
if ([Link] > 0)
[Link](prev);

// make current character as the previous

// 'char' decrease frequency by 'one'
([Link])--;
prev = k;
}
// If length of the resultant string
// and original string is not same then
// string is not valid
if (n != [Link]())
[Link](" Not possible ");
else
[Link](str);
 }

// Driver's code
public static void main(String args[])
{
String str = "bbbaa";

// Function call
rearrangeString(str);
}
}
------------------------------------------------------------------------------------------------------------------------
Area of Histogram ::
//Java program to find maximum rectangular area in linear time

import [Link];
public class RectArea
{
// The main function to find the maximum rectangular area under given
// histogram with n bars
static int getMaxArea(int hist[], int n)
{
// Create an empty stack. The stack holds indexes of hist[] array
// The bars stored in stack are always in increasing order of their
// heights.
Stack<Integer> s = new Stack<>();

int max_area = 0; // Initialize max area

int tp; // To store top of stack
int area_with_top; // To store area with top bar as the smallest bar

// Run through all bars of given histogram

int i = 0;
while (i < n)
{
// If this bar is higher than the bar on top stack, push it to stack
if ([Link]() || hist[[Link]()] <= hist[i])
[Link](i++);

// If this bar is lower than top of stack, then calculate area of rectangle
// with stack top as the smallest (or minimum height) bar. 'i' is
// 'right index' for the top and element before top in stack is 'left index'
else
{
tp = [Link](); // store the top index
[Link](); // pop the top

// Calculate the area with hist[tp] stack as smallest bar

area_with_top = hist[tp] * ([Link]() ? i : i - [Link]() - 1);

// update max area, if needed

if (max_area < area_with_top)
max_area = area_with_top;
}
}

// Now pop the remaining bars from stack and calculate area with every
// popped bar as the smallest bar
while ([Link]() == false)
{
tp = [Link]();
[Link]();
area_with_top = hist[tp] * ([Link]() ? i : i - [Link]() - 1);
 if (max_area < area_with_top)
max_area = area_with_top;
}

return max_area;

// Driver program to test above function

public static void main(String[] args)
{
int hist[] = { 6, 2, 5, 4, 5, 1, 6 };
[Link]("Maximum area is " + getMaxArea(hist, [Link]));
}
}
//12

------------------------------------------------------------------------------------------------------------------------
All possible unique BST – with Value N
// A Java program to construct all unique BSTs for keys from 1 to n
import [Link];
public class Main {
// function for constructing trees
static ArrayList<Node> constructTrees(int start, int end)
{
ArrayList<Node> list=new ArrayList<>();
/* if start > end then subtree will be empty so returning NULL
in the list */
if (start > end)
{
[Link](null);
return list;
 }
/* iterating through all values from start to end for constructing\
left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
ArrayList<Node> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
ArrayList<Node> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting
them to ith root below */
for (int j = 0; j < [Link](); j++)
{
Node left = [Link](j);
for (int k = 0; k < [Link](); k++)
{
Node right = [Link](k);
Node node = new Node(i); // making value i as root
[Link] = left; // connect left subtree
[Link] = right; // connect right subtree
[Link](node); // add this tree to list
}
}
}
return list;
}
// A utility function to do preorder traversal of BST
static void preorder(Node root)
{
if (root != null)
{
[Link]([Link]+" ") ;
 preorder([Link]);
preorder([Link]);
}
}
public static void main(String args[])
{
ArrayList<Node> totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal of all constructed BSTs */
[Link]("Preorder traversals of all constructed BSTs are ");
for (int i = 0; i < [Link](); i++)
{
preorder([Link](i));
[Link]();
}
}
}
// node structure
class Node
{
int key;
Node left, right;
Node(int data)
{
[Link]=data;
left=right=null;
}
};
------------------------------------------------------------------------------------------------------------------------
// Java program to print ancestors of given node
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root;
/* If target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
boolean printAncestors(Node node, int target)
{
/* base cases */
if (node == null)
return false;
if ([Link] == target)
return true;
/* If target is present in either left or right subtree
of this node, then print this node */
if (printAncestors([Link], target) || printAncestors([Link], target))
{
[Link]([Link] + " ");
return true;
}
/* Else return false */
return false;
}
/* Driver program to test above functions */
 public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* Construct the following binary tree
1
/\
2 3
/\
45
/
7
*/
[Link] = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);
[Link] = new Node(7);
[Link]([Link], 7);
}
}
4 2 1
------------------------------------------------------------------------------------------------------------------------
// Java program to check if binary tree is subtree of another binary tree
1. Using two way recussion we can do it.
2. Using inorder and preorder in two array( from original tree) and other inorder and
preorder( from subtree ) - in two other array and compare them if it’s subarray if
INORIGINAL to INSUB and PREORIGINAL to PRESUB, it’s subtree.
// A binary tree node
class Node
{
int data;
Node left, right, nextRight;
 Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root1,root2;
/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
boolean areIdentical(Node root1, Node root2)
{

/* base cases */
if (root1 == null && root2 == null)
return true;
if (root1 == null || root2 == null)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return ([Link] == [Link]
&& areIdentical([Link], [Link])
&& areIdentical([Link], [Link]));
}

/* This function returns true if S is a subtree of T, otherwise false */

boolean isSubtree(Node T, Node S)
{
/* base cases */
if (S == null)
return true;
 if (T == null)
return false;
/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree([Link], S)
|| isSubtree([Link], S);
}

public static void main(String args[])

{
BinaryTree tree = new BinaryTree();

// TREE 1
/* Construct the following tree
26
/\
10 3
/ \ \
4 6 3
\
30 */
tree.root1 = new Node(26);
[Link] = new Node(3);
[Link] = new Node(3);
[Link] = new Node(10);
[Link] = new Node(4);
[Link] = new Node(30);
[Link] = new Node(6);
// TREE 2
 /* Construct the following tree
10
/\
4 6
\
30 */

tree.root2 = new Node(10);

[Link] = new Node(6);
[Link] = new Node(4);
[Link] = new Node(30);
if ([Link](tree.root1, tree.root2))
[Link]("Tree 2 is subtree of Tree 1 ");
else
[Link]("Tree 2 is not a subtree of Tree 1");
}
}
------------------------------------------------------------------------------------------------------------------------
// Java program to construct a tree using inorder and preorder traversal
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
char data;
Node left, right;
Node(char item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
static int preIndex = 0;
Node buildTree(char in[], char pre[], int inStrt, int inEnd)
{
if (inStrt > inEnd)
return null;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
Node tNode = new Node(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, [Link]);
[Link] = buildTree(in, pre, inStrt, inIndex - 1);
[Link] = buildTree(in, pre, inIndex + 1, inEnd);
return tNode;
}
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
return i;
}
/* This function is here just to test buildTree() */
void printInorder(Node node)
{
 if (node == null)
return;
/* first recur on left child */
printInorder([Link]);
/* then print the data of node */
[Link]([Link] + " ");
/* now recur on right child */
printInorder([Link]);
}

// driver program to test above functions

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
char in[] = new char[] { 'D', 'B', 'E', 'A', 'F', 'C' };
char pre[] = new char[] { 'A', 'B', 'D', 'E', 'C', 'F' };
int len = [Link];
Node root = [Link](in, pre, 0, len - 1);

// building the tree by printing inorder traversal

[Link]("Inorder traversal of constructed tree is : ");
[Link](root);
}
}
------------------------------------------------------------------------------------------------------------------------
// Java program to find predecessor
// and successor in a BST
class GFG{

// BST Node
static class Node
{
 int key;
Node left, right;

public Node()
{}

public Node(int key)

{
[Link] = key;
[Link] = [Link] = null;
}
};

static Node pre = new Node(), suc = new Node();

// This function finds predecessor and

// successor of key in BST. It sets pre
// and suc as predecessor and successor
// respectively
static void findPreSuc(Node root, int key)
{

// Base case
if (root == null)
return;

// If key is present at root

if ([Link] == key)
{

// The maximum value in left

// subtree is predecessor
 if ([Link] != null)
{
Node tmp = [Link];
while ([Link] != null)
tmp = [Link];

pre = tmp;
}

// The minimum value in

// right subtree is successor
if ([Link] != null)
{
Node tmp = [Link];

while ([Link] != null)

tmp = [Link];

suc = tmp;
}
return;
}

// If key is smaller than

// root's key, go to left subtree
if ([Link] > key)
{
suc = root;
findPreSuc([Link], key);
}

// Go to right subtree
 else
{
pre = root;
findPreSuc([Link], key);
}
}

// A utility function to insert a

// new node with given key in BST
static Node insert(Node node, int key)
{
if (node == null)
return new Node(key);
if (key < [Link])
[Link] = insert([Link], key);
else
[Link] = insert([Link], key);

return node;
}

// Driver code
public static void main(String[] args)
{

// Key to be searched in BST

int key = 65;

/*
* Let us create following BST
* 50
* /\
 * 30 70
* /\/\
* 20 40 60 80
*/

Node root = new Node();

root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

findPreSuc(root, key);
if (pre != null)
[Link]("Predecessor is " + [Link]);
else
[Link]("No Predecessor");

if (suc != null)
[Link]("Successor is " + [Link]);
else
[Link]("No Successor");
}
}
Predecessor is 60
Successor is 70

------------------------------------------------------------------------------------------------------------------------
// An iterative java program to solve tree isomorphism problem
/* A binary tree node has data, pointer to left and right children */
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right;
}
}
class BinaryTree
{
Node root1, root2;
/* Given a binary tree, print its nodes in reverse level order */
boolean isIsomorphic(Node n1, Node n2)
{
// Both roots are NULL, trees isomorphic by definition
if (n1 == null && n2 == null)
return true;
// Exactly one of the n1 and n2 is NULL, trees not isomorphic
if (n1 == null || n2 == null)
return false;
if ([Link] != [Link])
return false;
// There are two possible cases for n1 and n2 to be isomorphic
// Case 1: The subtrees rooted at these nodes have NOT been
// "Flipped".
// Both of these subtrees have to be isomorphic.
// Case 2: The subtrees rooted at these nodes have been "Flipped"
return (isIsomorphic([Link], [Link]) && isIsomorphic([Link],[Link])) ||
(isIsomorphic([Link], [Link]) && isIsomorphic([Link], [Link]));
}
// Driver program to test above functions
 public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// Let us create trees shown in above diagram
tree.root1 = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);
[Link] = new Node(6);
[Link] = new Node(7);
[Link] = new Node(8);

tree.root2 = new Node(1);

[Link] = new Node(3);
[Link] = new Node(2);
[Link] = new Node(4);
[Link] = new Node(5);
[Link] = new Node(6);
[Link] = new Node(8);
[Link] = new Node(7);

if ([Link](tree.root1, tree.root2) == true)

[Link]("Yes");
else
[Link]("No");
}
}
Yes
------------------------------------------------------------------------------------------------------------------------
Best Way to Find Kth Smallest and Kth Largest Element -
// Java code for k largest/ smallest elements in an array
import [Link].*;
class GFG {
// Function to find k largest array element
static void kLargest(int a[], int n, int k)
{
// Implementation using
// a Priority Queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

for (int i = 0; i < n; ++i) {

// Insert elements into
// the priority queue
[Link](a[i]);
// if size of the priority
// queue exceeds k
if ([Link]() > k) {
[Link]();
}
}
// Print the k largest element
while (![Link]()) {
[Link]([Link]() + " ");
[Link]();
}
[Link]();
}

// Function to find k smallest array element

static void kSmallest(int a[], int n, int k)
{
// Implementation using
// a Priority Queue
 PriorityQueue<Integer> pq = new
PriorityQueue<Integer>( [Link]());

for (int i = 0; i < n; ++i) {

// Insert elements into
// the priority queue
[Link](a[i]);
// If size of the priority
// queue exceeds k
if ([Link]() > k) {
[Link]();
}
}
// Print the k largest element
while (![Link]()) {
[Link]([Link]() + " ");
[Link]();
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
int n = [Link];
int k = 3;
[Link](k + " largest elements are : ");
// Function Call
kLargest(a, n, k);
[Link](k + " smallest elements are : ");
// Function Call
kSmallest(a, n, k);
}
}

------------------------------------------------------------------------------------------------------------------------
For Time and Date and Day Calculator --
import [Link].*;
import [Link].*;
import [Link].*;
public class dateTime
{
public static void main(String arg[])
{
Scanner sc = new Scanner([Link]);
String in = [Link]();
LocalDate dd = [Link](2022,9,13);
Month m = [Link](dd);
DayOfWeek dd1 = [Link](dd);
[Link]([Link]()); [Link]([Link]()); }
---------------------------------------------------------------------------------------------------------------

Length of the longest valid substring

// Java program to find length of the longest valid
// substring

import [Link];

class Test
{
// method to get length of the longest valid
static int findMaxLen(String str)
{
int n = [Link]();
 Stack<Integer> stk = new Stack<>();
[Link](-1);
// Initialize result
int result = 0;
for (int i = 0; i < n; i++)
{
if ([Link](i) == '(')
[Link](i);
else
{
if(![Link]())
[Link]();
if (![Link]())
result= [Link](result,i - [Link]());
else
[Link](i);
}
}
return result;
}
// Driver code
public static void main(String[] args)
{
String str = "((()()";
// Function call
[Link](findMaxLen(str));
str = "()(()))))";
// Function call
[Link](findMaxLen(str));
}
}

---------------------------------------------------------------------------------------------------------------

Rain Tapping Water -

class GFG
{
public static void main (String[] args)
{
//code
Scanner sc=new Scanner([Link]);
int t=[Link]();
while(t-- >0)
{
int n=[Link]();
int a[]=new int[n];
int i;
for(i=0;i<n;i++)
a[i]=[Link]();

int l[]=new int[n];

int r[]=new int[n];

l[0]=a[0];
for(i=1;i<n;i++)
l[i]=[Link](l[i-1],a[i]);

r[n-1]=a[n-1];
for(i=n-2;i>=0;i--)
r[i]=[Link](r[i+1],a[i]);

int water=0;

for(i=0;i<n;i++)
{
water+=[Link](l[i],r[i])-a[i];
}
[Link](water);
}
}
}

3 0 0 2 0 4 ->>> 10

------------------------------------------------------------------------------------------------

/*package whatever //do not write package name here */

import [Link].*;

class GFG
{
// Java program to find Maximum Product Subarray

// Returns the product

// of max product subarray.
static int maxSubarrayProduct(int arr[],int n){
int max_ending_here = arr[0];
int min_ending_here = arr[0];
int max_so_far = arr[0];
for(int i=1;i<n;i++){
int temp = [Link]([Link](arr[i], arr[i] * max_ending_here),
arr[i] * min_ending_here);
min_ending_here = [Link]([Link](arr[i], arr[i] *
max_ending_here), arr[i] * min_ending_here);
max_ending_here = temp;
max_so_far = [Link](max_so_far, max_ending_here);
}
return max_so_far;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
int n = [Link];
[Link]("Maximum Sub array product is
%d",maxSubarrayProduct(arr, n));
}
}
//Maximum Sub array product is 112
-----------------------------------------------------

Dynamic Programming :

1. Longest Increasing Subsequence :

the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80}
is 6
static int max_ref = 1;
static int _lis(int arr[], int n)
{
// base case
if (n == 1)
return 1;
int res, max_ending_here = 1;
for (int i = 1; i < n; i++) {
res = _lis(arr, i);
if (arr[i - 1] < arr[n – 1] && max_ending_here < res + 1 )
max_ending_here = res + 1;
}
if (max_ref < max_ending_here)
max_ref = max_ending_here;
 return max_ending_here;
}

2. Longest Common Subsequence :

LCS for input Sequences “ABCDGH” and “AEDFHR” is
“ADH” of length 3.
int lcs( char[] X, char[] Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

3. Edit Distance :
Find minimum number of edits (operations) required to convert
‘str1’ into ‘str2’.
[Link] (m,n-1) 2. Remove(m-1,n) 3. Replace(m-1.n-1)
static int editDist(String str1, String str2, int m,
int n)
{

if (m == 0)
return n;
if (n == 0)
return m;
if ([Link](m - 1) == [Link](n - 1))
return editDist(str1, str2, m - 1, n - 1);
return 1 + min(editDist(str1, str2, m, n - 1), // Insert
editDist(str1, str2, m - 1, n), // Remove
editDist(str1, str2, m – 1, n - 1) // Replace
);
}

4. Min Cost Path – Moving in Matrix from (0,0) to (m,n) -

right, diagonal, down – are allowed-

static int minCost(int cost[][], int m, int n)

{
if (n < 0 || m < 0)
return Integer.MAX_VALUE;
else if (m == 0 && n == 0)
return cost[m][n];
else
return cost[m][n] + min( minCost(cost, m-1, n-1),
minCost(cost, m-1, n),minCost(cost, m, n-1) );
 }

int cost[][] = { {1, 2, 3},

{4, 8, 2},
{1, 5, 3} };

[Link](minCost(cost, 2, 2));

//output 8

5. Coin Change --
coins[] = { coins1, coins2, .. , coinsn}
sum =
all possible denomination we have to find -

static int count(int coins[], int n, int sum)

{
if (sum == 0)
return 1;
if (sum < 0)
return 0;
if (n <= 0)
return 0;
return count(coins,n-1,sum) + count(coins,n,sum-coins[n - 1]);
}
int coins[] = { 1, 2, 3 };
int n = [Link];
[Link](count(coins, n, 4));
//output 4

[Link] Chain Multiplication ; minimum number of multipication

required -
Input: arr[] = {1, 2, 3, 4, 3}
Output: 30 //1*2*3 + 1*3*4 + 1*4*3 = 30

static int MatrixChainOrder(int p[], int i, int j)

{
if (i == j)
return 0;
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++)
{
int count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
 return min;
}

MatrixChainOrder(arr, 1, N - 1));

[Link] Coefficient --

C(n, k) = C(n-1, k-1) + C(n-1, k)

C(n, 0) = C(n, n) = 1

We can find it using recusrsion -

static int binomialCoeff(int n, int k)

{
if (k > n)
return 0;
if (k == 0 || k == n)
return 1;
return binomialCoeff(n - 1, k – 1) + binomialCoeff(n - 1, k);
}

8. 0-1 Knapsack Problem :

we have to find out – maximum values we can put in total

capacity -

static int knapSack(int W, int wt[], int val[], int n)

{
// Base Case
if (n == 0 || W == 0)
return 0;
if (wt[n-1] > W)
return knapSack(W,wt,val,n-1);
else
return max(val[n-1]+ knapSack(W-wt[n-1],wt,val,n-1),
knapSack(W,wt,val,n-1));
}
9. Egg Dropping Puzzle :
k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trials needed to
find the critical
floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n – 1, x – 1),
eggDrop(n, k – x)), where x is in {1, 2, …, k}}

static int eggDrop(int n, int k)

{
if (k == 1 || k == 0)
return k;
if (n == 1)
return k;

int min = Integer.MAX_VALUE;

int x, res;
for (x = 1; x <= k; x++)
{
res = [Link](eggDrop(n - 1, x - 1),
eggDrop(n, k - x));
if (res < min)
min = res;
}
return min+1;
}

10. Longest Palindromic Subsequence :

static int lps(char seq[], int i, int j) {

// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
 }

// If the first and last characters match

if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}

// If the first and last characters do not match

return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}

11. Longest Palindromic Substring :

Input: Given string :"forgeeksskeegfor",
Output: "geeksskeeg"

static int longestPalSubstr(String str)

{
int n = [Link]();
int maxLength = 1, start = 0;
// Nested loop to mark start and end index
for (int i = 0; i < [Link](); i++) {
for (int j = i; j < [Link](); j++) {
int flag = 1;

// Check palindrome
for (int k = 0; k < (j - i + 1) / 2; k++)
{
if ([Link](i + k) != [Link](j - k))
flag = 0;
}
// Palindrome
if (flag!=0 && (j - i + 1) > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
[Link]("Longest palindrome subString is: ");
printSubStr(str, start, start + maxLength - 1);
return maxLength;
}
static void printSubStr(String str, int low, int high)
{
for (int i = low; i <= high; ++i)
[Link]([Link](i));
}

12. Cutting a Rod ;

if the length of the rod is 8 and the values
of different pieces are given as the
following, then the maximum obtainable value
is 22 (by cutting in two pieces of lengths 2
and 6)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20

static int cutRod(int price[], int index, int n)

{
// base case
if (index == 0) {
return n * price[0];
}
// At any index we have 2 options either
// cut the rod of this length or not cut
// it
int notCut = cutRod(price, index - 1, n);
int cut = Integer.MIN_VALUE;
int rod_length = index + 1;

if (rod_length <= n)
cut = price[index]
+ cutRod(price, index, n - rod_length);

return [Link](notCut, cut);

}

/* Driver program to test above functions */

public static void main(String args[])
{
int arr[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
int size = [Link];
[Link]("Maximum Obtainable Value is "
+ cutRod(arr, size - 1, size));
}

----------------------------------------------------------------
BackTracking
Problems ::
[Link] and Ladder –
Using one Hashmap we
can do it.

2. Solve the Sudoku ::

class Solution
{
//Function to find a solved Sudoku.
static boolean SolveSudoku(int grid[][])
{
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(grid[i][j] == 0)
{

for(int k=1; k<=9; k++)

{
if(isValid(grid, i, j, k))
{
grid[i][j] = k;
 if(SolveSudoku(grid) == true)
{
return true;
}
grid[i][j] = 0;
}
}
return false;
}
}
}
return true;
}

static boolean isValid(int[][] grid, int row, int col, int c){
for(int i=0; i<9; i++){
if(grid[i][col] == c) return false;
if(grid[row][i] == c) return false;
if (grid[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
}
return true;
}

//Function to print grids of the Sudoku.

static void printGrid (int grid[][])
{
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
[Link](grid[i][j] + " ");
}
}
}
}

--------------------------------------------
Find all possible paths from top to bottom
Input: 1 2 3
4 5 6
Output: 1 4 5 6
1 2 5 6
1 2 3 6
Explanation: We can see that there are 3
paths from the cell (0,0) to (1,2).

Given a N x M grid. Find All possible paths from top left

to bottom [Link] each cell you can either move only to
right or down.

class Solution {
public static void find(int i, int j, int n, int m, int [][]
grid,ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths){
if(i > n-1 || j > m-1){
 return;
}
if(i == n-1 && j == m-1){
[Link](grid[i][j]);
[Link](new ArrayList<>(path));
return;
}

[Link](grid[i][j]);
find(i+1, j, n, m, grid, new ArrayList<Integer>(path), paths);
find(i, j+1, n, m, grid, new ArrayList<Integer>(path), paths);
}

public static ArrayList<ArrayList<Integer>> findAllPossiblePaths(int n,int m,

int[][] grid) {
// code here
ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
find(0,0,n,m,grid,path,paths);

return paths;
}
}

--------------------------------------------
LRU Cache Implementation
// Java program to implement LRU cache
// using LinkedHashSet
import [Link].*;

class LRUCache {

Set<Integer> cache;
int capacity;

public LRUCache(int capacity)

{
[Link] = new LinkedHashSet<Integer>(capacity);
[Link] = capacity;
}

// This function returns false if key is not

// present in cache. Else it moves the key to
// front by first removing it and then adding
// it, and returns true.
public boolean get(int key)
{
if ()
return false;
[Link](key);
[Link](key);
return true;
}
 /* Refers key x with in the LRU cache */
public void refer(int key)
{
if (get(key) == false)
put(key);
}

// displays contents of cache in Reverse Order

public void display()
{
LinkedList<Integer> list = new LinkedList<>(cache);

// The descendingIterator() method of [Link]

// class is used to return an iterator over the elements
// in this LinkedList in reverse sequential order
Iterator<Integer> itr = [Link]();

while ([Link]())
[Link]([Link]() + " ");
}

public void put(int key)

{

if ([Link]() == capacity) {
int firstKey = [Link]().next();
[Link](firstKey);
}

[Link](key);
}

public static void main(String[] args)

{
LRUCache ca = new LRUCache(4);
[Link](1);
[Link](2);
[Link](3);
[Link](1);
[Link](4);
[Link](5);
[Link]();
}
}

5 4 1 3

------------------------------------------------------------------------------------------------------------------------
Greedy Problems ::
1. Activity Selection Problem ;
1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do the following for the remaining activities in the sorted array.
…….a) If the start time of this activity is greater than or equal to the finish time of the previously
selected activity then select this activity and print it.

// Java program for activity selection problem

// when input activities may not be sorted.
import [Link].*;
import [Link].*;
// A job has a start time, finish time and profit.
class Activity
{
int start, finish;
public Activity(int start, int finish)
{
[Link] = start;
[Link] = finish;
}
}
// Driver class
class GFG {
static void printMaxActivities(Activity arr[], int n)
{
// Sort jobs according to finish time
[Link](arr, new Comparator<Activity>()
{
@Override
public int compare(Activity s1, Activity s2)
{
 return [Link] - [Link];
}
});
[Link]("Following activities are selected :");
int i = 0;
[Link]("(" + arr[i].start + ", "+ arr[i].finish + "), ");
for (int j = 1; j < n; j++)
{
if (arr[j].start >= arr[i].finish)
{
[Link]("(" + arr[j].start + ", " + arr[j].finish + "), ");
i = j;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 6;
Activity arr[] = new Activity[n];
arr[0] = new Activity(5, 9);
arr[1] = new Activity(1, 2);
arr[2] = new Activity(3, 4);
arr[3] = new Activity(0, 6);
arr[4] = new Activity(5, 7);
arr[5] = new Activity(8, 9);
printMaxActivities(arr, n);
}
}
Following activities are selected
(1, 2), (3, 4), (5, 7), (8, 9)

---------------------------------------------------------------------------------------------------------------
2. Job Sequencing Problem
1. Maximize the total profit if only one job can be scheduled at a time.
Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output: Following is maximum profit sequence of jobs: c, a, e
Greedily choose the jobs with maximum profit first, by sorting the jobs in decreasing order of
their profit. This would help to maximize the total profit as choosing the job with maximum profit
for every time slot will eventually maximize the total profit
// Java code for the above approach
import [Link].*;
class Job {
// Each job has a unique-id,profit and deadline
char id;
int deadline, profit;
// Constructors
public Job() {}
public Job(char id, int deadline, int profit)
{
[Link] = id;
[Link] = deadline;
[Link] = profit;
}
// Function to schedule the jobs take 2 arguments
// arraylist and no of jobs to schedule
void printJobScheduling(ArrayList<Job> arr, int t)
{
// Length of array
int n = [Link]();
 // Sort all jobs according to decreasing order of
// profit
[Link](arr, (a, b) -> [Link] - [Link]);
// To keep track of free time slots
boolean result[] = new boolean[t];
// To store result (Sequence of jobs)
char job[] = new char[t];
// Iterate through all given jobs
for (int i = 0; i < n; i++) {
for (int j = [Link](t - 1, [Link](i).deadline – 1); j >= 0; j--)
{
// Free slot found
if (result[j] == false) {
result[j] = true;
job[j] = [Link](i).id;
break;
}
}
}
// Print the sequence
for (char jb : job)
[Link](jb + " ");
[Link]();
}
// Driver's code
public static void main(String args[])
{
ArrayList<Job> arr = new ArrayList<Job>();
[Link](new Job('a', 2, 100));
[Link](new Job('b', 1, 19));
[Link](new Job('c', 2, 27));
[Link](new Job('d', 1, 25));
 [Link](new Job('e', 3, 15));
[Link]("Following is maximum profit sequence of jobs");
Job job = new Job();
//maximum time we need to pass
[Link](arr, 3);
}
}
Following is maximum profit sequence of jobs
c a e

--------------------------------------------------------------------------------

3. Huffman Coding :
1. Build a Huffman Tree from input characters.

2. Traverse the Huffman Tree and assign codes to characters.

import [Link];

import [Link];

import [Link];

class HuffmanNode {

int data;

char c;

HuffmanNode left;

HuffmanNode right;

class MyComparator implements Comparator<HuffmanNode> {

public int compare(HuffmanNode x, HuffmanNode y)

return [Link] - [Link];

}
}

class Huffman {

public static void printCode(HuffmanNode root, String s)

if ([Link] == null && [Link] == null && [Link](root.c)) {

[Link](root.c + ":" + s);

return;

printCode([Link], s + "0");

printCode([Link], s + "1");

// main function

public static void main(String[] args)

Scanner s = new Scanner([Link]);

// number of characters.

int n = 6;

char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq = { 5, 9, 12, 13, 16, 45 };

PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new MyComparator());

for (int i = 0; i < n; i++) {

HuffmanNode hn = new HuffmanNode();

hn.c = charArray[i];

[Link] = charfreq[i];
 [Link] = null;

[Link] = null;

[Link](hn);

// create a root node

HuffmanNode root = null;

while ([Link]() > 1) {

HuffmanNode x = [Link]();

[Link]();

HuffmanNode y = [Link]();

[Link]();

HuffmanNode f = new HuffmanNode();

[Link] = [Link] + [Link];

f.c = '-';

[Link] = x;

[Link] = y;

root = f;

[Link](f);

// print the codes by traversing the tree

printCode(root, "");

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

---------------------------------------------------------

Prims Algorithm ::
// A Java program for Prim's Minimum Spanning Tree (MST)
// algorithm. The program is for adjacency matrix
// representation of the graph
import [Link].*;
import [Link].*;
import [Link].*;
class MST {
private static final int V = 5;
int minKey(int key[], Boolean mstSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}

return min_index;
}
// A utility function to print the constructed MST
// stored in parent[]
void printMST(int parent[], int graph[][])
{
[Link]("Edge \tWeight");
 for (int i = 1; i < V; i++)
[Link](parent[i] + " - " + i + "\t"+ graph[i][parent[i]]);
}
void primMST(int graph[][])
{
// Array to store constructed MST
int parent[] = new int[V];
int key[] = new int[V];
// To represent set of vertices included in MST
Boolean mstSet[] = new Boolean[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is
// picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
{ if (graph[u][v] != 0 && mstSet[v] == false
&& graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// print the constructed MST
 printMST(parent, graph);
}
public static void main(String[] args)
{
MST t = new MST();
int graph[][] = new int[][] { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Print the solution
[Link](graph);
}
}
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5

-------------------------------------------------------------------------------------------------------

Diskastra For shortest Path - similar concept like prim algo

import [Link].*;
import [Link].*;
import [Link].*;

class ShortestPath {
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min) {
 min = dist[v];
min_index = v;
}
return min_index;
}
// A utility function to print the constructed distance
// array
void printSolution(int dist[])
{
[Link]("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++)
[Link](i + " \t\t " + dist[i]);
}
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V]; // The output array.
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
{
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v]
< dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
 // print the constructed distance array
printSolution(dist);
}
// Driver's code
public static void main(String[] args)
{
int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
ShortestPath t = new ShortestPath();
// Function call
[Link](graph, 0);
}
}
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

------------------------------------------------------------------------
// Java program for Kruskal's algorithm to

// find Minimum Spanning Tree of a given

// connected, undirected and weighted graph

import [Link].*;

import [Link].*;

import [Link].*;

class Graph {

// A class to represent a graph edge

class Edge implements Comparable<Edge> {

int src, dest, weight;

public int compareTo(Edge compareEdge)

return [Link] - [Link];

};

// A class to represent a subset for

// union-find

class subset {

int parent, rank;

};

int V, E; // V-> no. of vertices & E->[Link] edges

Edge edge[]; // collection of all edges

// 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();

// A utility function to find set of an

// element i (uses path compression technique)

int find(subset subsets[], int i)

if (subsets[i].parent != i)

subsets[i].parent= find(subsets, subsets[i].parent);

return subsets[i].parent;

// A function that does union of two sets

// of x and y (uses union by rank)

void Union(subset subsets[], int x, int y)

int xroot = find(subsets, x);

int yroot = find(subsets, y);

// Attach smaller rank tree under root

// of high rank tree (Union by Rank)

 if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

else {

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

void KruskalMST()

// This will store the resultant MST

Edge result[] = new Edge[V];

// An index variable, used for result[]

int e = 0;

// An index variable, used for sorted edges

int i = 0;

for (i = 0; i < V; ++i)

result[i] = new Edge();

[Link](edge);

// Allocate memory for creating V subsets

subset subsets[] = new subset[V];

for (i = 0; i < V; ++i)

 subsets[i] = new subset();

// Create V subsets with single elements

for (int v = 0; v < V; ++v) {

subsets[v].parent = v;

subsets[v].rank = 0;

i = 0; // Index used to pick next edge

// Number of edges to be taken is equal to V-1

while (e < V - 1) {

Edge next_edge = edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

if (x != y) {

result[e++] = next_edge;

Union(subsets, x, y);

// Else discard the next_edge

[Link]("Following are the edges in " + "the constructed MST");

int minimumCost = 0;

for (i = 0; i < e; ++i) {

[Link](result[i].src + " -- " + result[i].dest + " == " + result[i].weight);

minimumCost += result[i].weight;
 }

[Link]("Minimum Cost Spanning Tree "+ minimumCost);

// Driver's Code

public static void main(String[] args)

int V = 4; // Number of vertices in graph

int E = 5; // Number of edges in graph

Graph graph = new Graph(V, E);

// add edge 0-1

[Link][0].src = 0;

[Link][0].dest = 1;

[Link][0].weight = 10;

// add edge 0-2

[Link][1].src = 0;

[Link][1].dest = 2;

[Link][1].weight = 6;

// add edge 0-3

[Link][2].src = 0;

[Link][2].dest = 3;

[Link][2].weight = 5;

// add edge 1-3

 [Link][3].src = 1;

[Link][3].dest = 3;

[Link][3].weight = 15;

// add edge 2-3

[Link][4].src = 2;

[Link][4].dest = 3;

[Link][4].weight = 4;

// Function call

[Link]();

Following are the edges in the constructed MST

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

---------------------------------------------------------------------------------------------------------------

Cycle Ditecttion in The Graph Using Union-Find Algo – Like Disjoint Set

// Java Program for union-find algorithm to detect cycle in

// a graph

import [Link].*;

import [Link].*;

import [Link].*;

class Graph {

int V, E; // V-> no. of vertices & E->[Link] edges

Edge edge[]; // /collection of all edges

class Edge {

int src, dest;

};

// 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();

// A utility function to find the subset of an element i

int find(int parent[], int i)

if (parent[i] == i)

return i;

return find(parent, parent[i]);

// A utility function to do union of two subsets

void Union(int parent[], int x, int y)

{
 parent[x] = y;

// The main function to check whether a given graph

// contains cycle or not

int isCycle(Graph graph)

// Allocate memory for creating V subsets

int parent[] = new int[graph.V];

// Initialize all subsets as single element sets

for (int i = 0; i < graph.V; ++i)

parent[i] = i;

for (int i = 0; i < graph.E; ++i) {

int x = [Link](parent, [Link][i].src);

int y = [Link](parent, [Link][i].dest);

if (x == y)

return 1;

[Link](parent, x, y);

return 0;

// Driver Method

public static void main(String[] args)

{
 int V = 3, E = 3;

Graph graph = new Graph(V, E);

// add edge 0-1

[Link][0].src = 0;

[Link][0].dest = 1;

// add edge 1-2

[Link][1].src = 1;

[Link][1].dest = 2;

// add edge 0-2

[Link][2].src = 0;

[Link][2].dest = 2;

if ([Link](graph) == 1)

[Link]("Graph contains cycle");

else

[Link]("Graph doesn't contain cycle");

Graph contains cycle

---------------------------------------------------------------------------------------------------------------

Graph Problem ::

BFS:
import [Link].*;
1. import [Link].*;
2. public class BFSTraversal
3. {
4. private int vertex; /* total number number of vertices in the graph */
5. private LinkedList<Integer> adj[]; /* adjacency list */
6. private Queue<Integer> que; /* maintaining a queue */
7. BFSTraversal(int v)
8. {
9. vertex = v;
10. adj = new LinkedList[vertex];
11. for (int i=0; i<v; i++)
12. {
13. adj[i] = new LinkedList<>();
14. }
15. que = new LinkedList<Integer>();
16. }
17. void insertEdge(int v,int w)
18. {
19. adj[v].add(w); /* adding an edge to the adjacency list (edges are bidirectional in this
example) */
20. }
21. void BFS(int n)
22. {
23. boolean nodes[] = new boolean[vertex]; /* initialize boolean array for holding the d
ata */
24. int a = 0;
25. nodes[n]=true;
26. [Link](n); /* root node is added to the top of the queue */
27. while ([Link]() != 0)
28. {
29. n = [Link](); /* remove the top element of the queue */
30. [Link](n+" "); /* print the top element of the queue */
31. for (int i = 0; i < adj[n].size(); i++) /* iterate through the linked list and push all neig
hbors into queue */
32. {
33. a = adj[n].get(i);
34. if (!nodes[a]) /* only insert nodes into queue if they have not been explored alr
eady */
35. {
36. nodes[a] = true;
37. [Link](a);
38. }
39. }
40. }
41. }
42. public static void main(String args[])
43. {
 44. BFSTraversal graph = new BFSTraversal(10);
45. [Link](0, 1);
46. [Link](0, 2);
47. [Link](0, 3);
48. [Link](1, 3);
49. [Link](2, 4);
50. [Link](3, 5);
51. [Link](3, 6);
52. [Link](4, 7);
53. [Link](4, 5);
54. [Link](5, 2);
55. [Link](6, 5);
56. [Link](7, 5);
57. [Link](7, 8);
58. [Link]("Breadth First Traversal for the graph is:");
59. [Link](2);
60. }
61.}

output : 2 4 7 5 8

DFS ::
import [Link].*;
•
• class DFSTraversal {
• private LinkedList<Integer> adj[]; /*adjacency list representation*/
• private boolean visited[];
•
• /* Creation of the graph */
• DFSTraversal(int V) /*'V' is the number of vertices in the graph*/
• {
• adj = new LinkedList[V];
• visited = new boolean[V];
•
• for (int i = 0; i < V; i++)
• adj[i] = new LinkedList<Integer>();
• }
•
• /* Adding an edge to the graph */
• void insertEdge(int src, int dest) {
• adj[src].add(dest);
• }
•
 • void DFS(int vertex) {
• visited[vertex] = true; /*Mark the current node as visited*/
• [Link](vertex + " ");
•
• Iterator<Integer> it = adj[vertex].listIterator();
• while ([Link]()) {
• int n = [Link]();
• if (!visited[n])
• DFS(n);
• }
• }
•
• public static void main(String args[]) {
• DFSTraversal graph = new DFSTraversal(8);
•
• [Link](0, 1);
• [Link](0, 2);
• [Link](0, 3);
• [Link](1, 3);
• [Link](2, 4);
• [Link](3, 5);
• [Link](3, 6);
• [Link](4, 7);
• [Link](4, 5);
• [Link](5, 2);
•
• [Link]("Depth First Traversal for the graph is:");
• [Link](0);
• }
• }
OUTPUT :: 0 1 3 5 2 4 7 6

---------------------------------------------------------------------------------------------------------------

Topological Sorting -
// A Java program to print topological
// sorting of a DAG
import [Link].*;
import [Link].*;

// This class represents a directed graph

// using adjacency list representation
class Graph {
// No. of vertices
private int V;

// Adjacency List as ArrayList of ArrayList's

private ArrayList<ArrayList<Integer> > adj;

// Constructor
Graph(int v)
{
V = v;
adj = new ArrayList<ArrayList<Integer> >(v);
for (int i = 0; i < v; ++i)
[Link](new ArrayList<Integer>());
}

// Function to add an edge into the graph

void addEdge(int v, int w) { [Link](v).add(w); }

// A recursive function used by topologicalSort

void topologicalSortUtil(int v, boolean visited[],
Stack<Integer> stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent

// to thisvertex
Iterator<Integer> it = [Link](v).iterator();
while ([Link]()) {
 i = [Link]();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack

// which stores result
[Link](new Integer(v));
}

// The function to do Topological Sort.

// It uses recursive topologicalSortUtil()
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();

// Mark all the vertices as not visited

boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper

// function to store
// Topological Sort starting
// from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack

while ([Link]() == false)
[Link]([Link]() + " ");
 }

// Driver code
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);
[Link](5, 2);
[Link](5, 0);
[Link](4, 0);
[Link](4, 1);
[Link](2, 3);
[Link](3, 1);

[Link]("Following is a Topological "

+ "sort of the given graph");
// Function Call
[Link]();
}
}
// 5 4 2 3 1 0

---------------------------------------------------------------------------------------------------------------

Tree Problems :

1. Tree Construction - Inorder and LevelOrder

// Java program to construct a tree from level order and

// and inorder traversal

// A binary tree node

class Node {
 int data;

Node left, right;

Node(int item)

data = item;

left = right = null;

public void setLeft(Node left) { [Link] = left; }

public void setRight(Node right) { [Link] = right; }

class Tree {

Node root;

Node buildTree(int in[], int level[])

Node startnode = null;

return constructTree(startnode, level, in, 0,[Link] - 1);

Node constructTree(Node startNode, int[] levelOrder,int[] inOrder, int inStart,int inEnd)

// if start index is more than end index

if (inStart > inEnd)

return null;

if (inStart == inEnd)
 return new Node(inOrder[inStart]);

boolean found = false;

int index = 0;

for (int i = 0; i < [Link] - 1; i++) {

int data = levelOrder[i];

for (int j = inStart; j < inEnd; j++) {

if (data == inOrder[j]) {

startNode = new Node(data);

index = j;

found = true;

break;

if (found == true)

break;

[Link](constructTree(startNode, levelOrder, inOrder,inStart, index - 1));

[Link](constructTree(startNode, levelOrder, inOrder,index + 1, inEnd));

return startNode;

/* Utility function to print inorder traversal of binary

* tree */
 void printInorder(Node node)

if (node == null)

return;

printInorder([Link]);

[Link]([Link] + " ");

printInorder([Link]);

// Driver program to test the above functions

public static void main(String args[])

Tree tree = new Tree();

int in[] = new int[] { 4, 8, 10, 12, 14, 20, 22 };

int level[] = new int[] { 20, 8, 22, 4, 12, 10, 14 };

int n = [Link];

Node node = [Link](in, level);

[Link]("Inorder traversal of the constructed tree is ");

[Link](node);

Inorder traversal of the constructed tree is

4 8 10 12 14 20 20
2. PreOrder and PostOrder : Full Binary Tree

// Java program for construction

// of full binary tree

public class fullbinarytreepostpre

static int preindex;

static class node

int data;

node left, right;

public node(int data)

[Link] = data;

static node constructTreeUtil(int pre[], int post[], int l, int h, int size)

// Base case

if (preindex >= size || l > h)

return null;

node root = new node(pre[preindex]);

preindex++;

if (l == h || preindex >= size)

 return root;

int i;

// Search the next element of pre[] in post[]

for (i = l; i <= h; i++)

if (post[i] == pre[preindex])

break;

if (i <= h)

[Link] = constructTreeUtil(pre, post, l, i, size);

[Link] = constructTreeUtil(pre, post, i + 1, h-1, size);

return root;

static node constructTree(int pre[], int post[], int size)

preindex = 0;

return constructTreeUtil(pre, post, 0, size - 1, size);

static void printInorder(node root)

if (root == null)
 return;

printInorder([Link]);

[Link]([Link] + " ");

printInorder([Link]);

public static void main(String[] args)

int pre[] = { 1, 2, 4, 8, 9, 5, 3, 6, 7 };

int post[] = { 8, 9, 4, 5, 2, 6, 7, 3, 1 };

int size = [Link];

node root = constructTree(pre, post, size);

[Link]("Inorder traversal of the constructed tree:");

printInorder(root);

Inorder traversal of the constructed tree:

8 4 9 2 5 1 6 3 7

3. InOrder and PostOrder :

/* Java program to construct tree using inorder and postorder traversals */

import [Link].*;

class GFG

static class Node

{
 int data;

Node left, right;

};

static Node newNode(int data)

Node node = new Node();

[Link] = data;

[Link] = [Link] = null;

return (node);

static Node buildUtil(int in[], int post[],int inStrt, int inEnd)

// Base case

if (inStrt > inEnd)

return null;

int curr = post[index];

Node node = newNode(curr);

(index)--;

if (inStrt == inEnd)

return node;

int iIndex = [Link](curr);

[Link] = buildUtil(in, post, iIndex + 1,inEnd);

[Link] = buildUtil(in, post, inStrt,iIndex - 1);

 return node;

static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();

static int index;

static Node buildTree(int in[], int post[], int len)

for (int i = 0; i < len; i++)

[Link](in[i], i);

index = len - 1; // Index in postorder

return buildUtil(in, post, 0, len - 1 );

static void preOrder(Node node)

if (node == null)

return;

[Link]("%d ", [Link]);

preOrder([Link]);

preOrder([Link]);

// Driver code

public static void main(String[] args)

int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
 int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };

int n = [Link];

Node root = buildTree(in, post, n);

[Link]("Preorder of the constructed tree : \n");

preOrder(root);

Preorder of the constructed tree :

1 2 4 8 5 3 6 7

---------------------------------------------------------------------------------------------------------------

4. Special Tree Using inOrder Traversal -

Given Inorder Traversal of a Special Binary Tree in which the key of every node is
greater than keys in left and right children, construct the Binary Tree and return root.

Input: inorder[] = {5, 10, 40, 30, 28}

Output: root of following tree

40
/ \
10 30
/ \
5 28

// Java program to construct tree from inorder traversal

class Node

int data;

Node left, right;

Node(int item)

{
 data = item;

left = right = null;

class BinaryTree

Node root;

Node buildTree(int inorder[], int start, int end, Node node)

if (start > end)

return null;

int i = max(inorder, start, end);

node = new Node(inorder[i]);

if (start == end)

return node;

[Link] = buildTree(inorder, start, i - 1, [Link]);

[Link] = buildTree(inorder, i + 1, end, [Link]);

return node;

/* Function to find index of the maximum value in arr[start...end] */

int max(int arr[], int strt, int end)

int i, max = arr[strt], maxind = strt;

 for (i = strt + 1; i <= end; i++)

if (arr[i] > max)

max = arr[i];

maxind = i;

return maxind;

void printInorder(Node node)

if (node == null)

return;

printInorder([Link]);

[Link]([Link] + " ");

printInorder([Link]);

public static void main(String args[])

BinaryTree tree = new BinaryTree();

int inorder[] = new int[]{5, 10, 40, 30, 28};

int len = [Link];

 Node mynode = [Link](inorder, 0, len - 1, [Link]);

[Link]("Inorder traversal of the constructed tree is ");

[Link](mynode);

Inorder traversal of the constructed tree is

5 10 40 30 28

---------------------------------------------------------------------------------------------------------------

1. Convert to Sum of it’s sub tree and leaf node to 0

10
/ \
-2 6
/ \ / \
8 -4 7 5

To 20(4-2+12+6)
/ \
4(8-4) 12(7+5)
/ \ / \
0 0 0 0

int toSumTree(Node node)

{
if (node == null)
return 0;
// Store the old value
int old_val = [Link];
[Link] = toSumTree([Link]) + toSumTree([Link]);
return [Link] + old_val;
}

---------------------------------------------------------------------------------------------------------------

Given a Binary Tree, change the value in each node to sum of

all the values in the nodes in the left subtree including its
own.
Input

1
/ \
2 3
/ \ \
4 5 6
Output:
12
/ \
6 3
/ \ \
4 5 6

static int updatetree(node root)

{
if (root == null)
return 0;
if ([Link] == null && [Link] == null)
return [Link];
int leftsum = updatetree([Link]);
int rightsum = updatetree([Link]);
[Link] += leftsum;
return [Link] + rightsum;
}

---------------------------------------------------------------------------------------------------------------

Flip the Tree - In the flip operation, the leftmost node becomes the root of the flipped tree and its
parent becomes its right child and the right sibling becomes its left child and the same should be
done for all left most nodes recursively.

// method to flip the binary tree

public static Node flipBinaryTree(Node root)

{
if (root == null)
 return root;
if ([Link] == null && [Link] ==null)
return root;

// recursively call the same method

Node flippedRoot=flipBinaryTree([Link]);

[Link]=[Link];
[Link]=root;
[Link]=[Link]=null;
return flippedRoot;
}
---------------------------------------------------------------------------------------------------------------

Given a binary tree, print all root-to-leaf paths

For the below example tree, all root-to-leaf paths are:

10 –> 8 –> 3
10 –> 8 –> 5
10 –> 2 –> 2

void printPaths(Node node)

{
int path[] = new int[1000];
printPathsRecur(node, path, 0);
}
void printPathsRecur(Node node, int path[], int pathLen)
{
if (node == null)
return;
path[pathLen] = [Link];
pathLen++;
if ([Link] == null && [Link] == null)
printArray(path, pathLen);
else
{
printPathsRecur([Link], path, pathLen);
printPathsRecur([Link], path, pathLen);
}
}
---------------------------------------------------------------------------------------------------------------

Reverse tree path : Given a tree and node data, the task to reverse the
path to that particular Node.

We can use same concept as above , just need to check when root data is equal
to given particular node.
Input:
7
/ \
6 5
/ \ / \
4 3 2 1
Data = 4
Output: Inorder of tree
7 6 3 4 2 5 1

static void reverseTreePathUtil(Node root, ArrayList<Node> path,int

pathLen, int key)

{
if (root == null)
return;
[Link](pathLen, root);
pathLen++;
// reversed
if ([Link] == key) {

int i = 0, j = pathLen - 1;

// Swap the data of two nodes

while (i < j)
{
int temp = [Link](i).data;
[Link](i).data = [Link](j).data;
[Link](j).data = temp;
i++;
j--;
}
}
if ([Link] == null && [Link] == null)
return;

reverseTreePathUtil([Link], path,
pathLen, key);
reverseTreePathUtil([Link], path,
pathLen, key);
}
static void reverseTreePath(Node root, int key)
{
if (root == null)
return;
ArrayList<Node> path = new ArrayList<Node>();
for(int i = 0; i < 50; i++)
{
[Link](null);
}
reverseTreePathUtil(root, path, 0, key);
}
-----------------------------------------------------------------------------------------------

Find all possible binary trees with given Inorder Traversal :

Input: in[] = {4, 5, 7};
Output: Preorder traversals of different possible Binary Trees are:
4 5 7
4 7 5
5 4 7
7 4 5
7 5 4
Below are different possible binary trees
4 4 5 7 7
\ \ / \ / /
5 7 4 7 4 5
\ / \ /
7 5 5 4

class BinaryTree {
Node root;

void preOrder(Node node) {

if (node != null) {
[Link]([Link] + " " );
preOrder([Link]);
preOrder([Link]);
}
}
Vector<Node> getTrees(int arr[], int start, int end) {
Vector<Node> trees= new Vector<Node>();
if (start > end) {
[Link](null);
return trees;
}
for (int i = start; i <= end; i++) {
/* Constructing left subtree */
Vector<Node> ltrees = getTrees(arr, start, i - 1);

/* Constructing right subtree */

Vector<Node> rtrees = getTrees(arr, i + 1, end);

/* Now looping through all left and right subtrees

and connecting them to ith root below */
for (int j = 0; j < [Link](); j++) {
for (int k = 0; k < [Link](); k++) {

// Making arr[i] as root

Node node = new Node(arr[i]);

// Connecting left subtree

 [Link] = [Link](j);

// Connecting right subtree

[Link] = [Link](k);

// Adding this tree to list

[Link](node);
}
}
}
return trees;
}

public static void main(String args[]) {

int in[] = {4, 5, 7};
int n = [Link];
BinaryTree tree = new BinaryTree();
Vector<Node> trees = [Link](in, 0, n - 1);
[Link]("Preorder traversal of different binary
trees are:");
for (int i = 0; i < [Link](); i++) {
[Link]([Link](i));
[Link]("");
}
}
}

------------------------------------------------------------------------------------------------

Replace each node in binary tree with the sum of its inorder predecessor and
successor

- Do simple inorder and store the value in ArrayList the again do inorder and change value
of each node with [Link] = [Link](i-1) + [Link](i+1)

---------------------------------------------------------------------------------------------------------------

Minimum swap required to convert binary tree to binary search tree

Minimum number of swaps required to sort an array

Input: {4, 3, 2, 1}

Output: 2
Explanation: Swap index 0 with 3 and 1 with 2 to form the sorted array {1, 2, 3,
4}.
// Java program to find

// minimum number of swaps

// required to sort an array

import [Link];

import [Link];

import [Link].*;

class GfG

public static int minSwaps(int[] arr)

int n = [Link];

ArrayList <Pair <Integer, Integer> > arrpos =new ArrayList <Pair <Integer,Integer> >
();

for (int i = 0; i < n; i++)

[Link](new Pair <Integer,Integer> (arr[i], i));

[Link](new Comparator<Pair<Integer,Integer>>()

@Override

public int compare(Pair<Integer, Integer> o1,Pair<Integer, Integer> o2)

if ([Link]() > [Link]())

return -1;

else if ([Link]().equals([Link]()))

return 0;

else
 return 1;

});

Boolean[] vis = new Boolean[n];

[Link](vis, false);

int ans = 0;

for (int i = 0; i < n; i++)

if (vis[i] || [Link](i).getValue() == i)

continue;

int cycle_size = 0;

int j = i;

while (!vis[j])

vis[j] = true;

j = [Link](j).getValue();

cycle_size++;

if(cycle_size > 0)

ans += (cycle_size - 1);

}
 return ans;

class MinSwaps

public static void main(String[] args)

int []a = {1, 5, 4, 3, 2};

GfG g = new GfG();

[Link]([Link](a));

---------------------------------------------------------------------------------------------------------------

Check if two nodes are cousins in a Binary Tree

Given the binary Tree and the two nodes say ‘a’ and ‘b’, determine whether the two nodes
are cousins of each other or not.
Two nodes are cousins of each other if they are at same level and have different parents.

/ \
3 5
/ \ / \
7 8 1 3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.

boolean isSibling(Node node, Node a, Node b)

{
// Base case
if (node == null)
return false;
 return (([Link] == a && [Link] == b) ||
([Link] == b && [Link] == a) ||
isSibling([Link], a, b) ||
isSibling([Link], a, b));
}

int level(Node node, Node ptr, int lev)

{
// base cases
if (node == null)
return 0;
if (node == ptr)
return lev;
int l = level([Link], ptr, lev + 1);
if (l != 0)
return l;
return level([Link], ptr, lev + 1);
}

// Returns 1 if a and b are cousins, otherwise 0

boolean isCousin(Node node, Node a, Node b)
{
return ((level(node, a, 1) == level(node, b, 1)) &&
(!isSibling(node, a, b)));
}

------------------------------------------------------------------------------------------------------------------------

// Java program to check if all leaves are at same level

Check if all leaves are at same level

class Node

int data;

Node left, right;

Node(int item)

data = item;

left = right = null;

}
}

class Leaf

int leaflevel=0;

class BinaryTree

Node root;

Leaf mylevel = new Leaf();

boolean checkUtil(Node node, int level, Leaf leafLevel)

if (node == null)

return true;

if ([Link] == null && [Link] == null)

if ([Link] == 0)

[Link] = level;

return true;

return (level == [Link]);

return checkUtil([Link], level + 1, leafLevel)

 && checkUtil([Link], level + 1, leafLevel);

boolean check(Node node)

int level = 0;

return checkUtil(node, level, mylevel);

public static void main(String args[])

BinaryTree tree = new BinaryTree();

[Link] = new Node(12);

[Link] = new Node(5);

[Link] = new Node(3);

[Link] = new Node(9);

[Link] = new Node(1);

[Link] = new Node(1);

if ([Link]([Link]))

[Link]("Leaves are at same level");

else

[Link]("Leaves are not at same level");

Leaves are at same level

---------------------------------------------------------------------------------------------------------------

Check sum of Covered and Uncovered nodes of Binary

Tree
In above binary tree,

Covered node: 6, 5, 7
Uncovered node: 9, 4, 3, 17, 22, 20

class BinaryTree

{
Node root;
int sum(Node t)
{
if (t == null)
return 0;
return [Link] + sum([Link]) + sum([Link]);
}
int uncoveredSumLeft(Node t)
{
if ([Link] == null && [Link] == null)
return [Link];
if ([Link] != null)
return [Link] + uncoveredSumLeft([Link]);
else
return [Link] + uncoveredSumLeft([Link]);
}

int uncoveredSumRight(Node t)
{
if ([Link] == null && [Link] == null)
return [Link];
if ([Link] != null)
return [Link] + uncoveredSumRight([Link]);
else
return [Link] + uncoveredSumRight([Link]);
}

int uncoverSum(Node t)
{
int lb = 0, rb = 0;

if ([Link] != null)
lb = uncoveredSumLeft([Link]);
 if ([Link] != null)
rb = uncoveredSumRight([Link]);

/* returning sum of root node, left boundary

and right boundary*/
return [Link] + lb + rb;
}

// Returns true if sum of covered and uncovered elements

// is same.
boolean isSumSame(Node root)
{
// Sum of uncovered elements
int sumUC = uncoverSum(root);

// Sum of all elements

int sumT = sum(root);

// Check if sum of covered and uncovered is same

return (sumUC == (sumT - sumUC));
}

void inorder(Node root)

{
if (root != null)
{
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
}

// Driver program to test above functions

public static void main(String[] args)
{

BinaryTree tree = new BinaryTree();

// Making above given diagram's binary tree

[Link] = new Node(8);
[Link] = new Node(3);
[Link] = new Node(1);
[Link] = new Node(6);
[Link] = new Node(4);
[Link] = new Node(7);

[Link] = new Node(10);

[Link] = new Node(14);
[Link] = new Node(13);

if ([Link]([Link]))
 [Link]("Sum of covered and uncovered is
same");
else
[Link]("Sum of covered and uncovered is
not same");
}
}
---------------------------------------------------------------------------------------------------------------

Given level order traversal of a Binary Tree, check if the Tree is a

Min-Heap
Input : level = [10, 15, 14, 25, 30]

Output : True

static boolean isMinHeap(int []level)

{
int n = [Link] - 1;
for (int i=(n/2-1) ; i>=0 ; i--)
{
// Left child will be at index 2*i+1
// Right child will be at index 2*i+2
if (level[i] > level[2 * i + 1])
return false;

if (2*i + 2 < n)
{
if (level[i] > level[2 * i + 2])
return false;
}
}
return true;
}
---------------------------------------------------------------------------------------------------------------

Check whether a given binary tree is perfect or not

static int findADepth(Node node)

{
int d = 0;
while (node != null)
{
d++;
node = [Link];
}
return d;
}
/* This function tests if a binary tree is perfect
or not. It basically checks for two things :
1) All leaves are at same level
2) All internal nodes have two children */
static boolean isPerfectRec(Node root, int d, int level)
{
if (root == null)
return true;

if ([Link] == null && [Link] == null)

return (d == level+1);

if ([Link] == null || [Link] == null)

return false;
return isPerfectRec([Link], d, level+1) &&
isPerfectRec([Link], d, level+1);
}

static boolean isPerfect(Node root)

{
int d = findADepth(root);
return isPerfectRec(root, d, 0);
}
---------------------------------------------------------------------------------------------------------------

Check whether a binary tree is a full binary tree or

not

boolean isFullTree(Node node)

{
// if empty tree
if(node == null)
return true;

// if leaf node
if([Link] == null && [Link] == null )
return true;

// if both left and right subtrees are not null

// the are full
if(([Link]!=null) && ([Link]!=null))
return (isFullTree([Link]) &&
isFullTree([Link]));

// if none work
return false;
}
---------------------------------------------------------------------------------------------------------------

Check if two trees are Mirror

boolean areMirror(Node a, Node b)

{
/* Base case : Both empty */
if (a == null && b == null)
return true;

// If only one is empty

if (a == null || b == null)
return false;

/* Both non-empty, compare them recursively

Note that in recursive calls, we pass left
of one tree and right of other tree */
return [Link] == [Link]
&& areMirror([Link], [Link])
&& areMirror([Link], [Link]);
}
---------------------------------------------------------------------------------------------------------------

Print cousins of a given node in Binary Tree

Input : root of below tree

1
/ \
2 3
/ \ / \
4 5 6 7
and pointer to a node say 5.

Output : 6, 7

static void printCousins(Node root, Node node_to_find)

{
if (root == node_to_find)
{
[Link]("Cousin Nodes : None" + "\n");
return;
}

Queue<Node> q = new LinkedList<Node>();

boolean found = false;
int size_ = 0;
Node p = null;
[Link](root);
while ([Link]() == false && found == false)
 {
size_ = [Link]();
while (size_ -- > 0)
{
p = [Link]();
[Link]();
if (([Link] == node_to_find || [Link] == node_to_find))
{
found = true;
}
else
{
if ([Link] != null)
[Link]([Link]);
if ([Link]!= null)
[Link]([Link]);
}

}
}
if (found == true)
{
[Link]("Cousin Nodes : ");
size_ = [Link]();
if (size_ == 0)
[Link]("None");
for (int i = 0; i < size_; i++)
{
p = [Link]();
[Link]();

[Link]([Link] + " ");

}
}
else
{
[Link]("Node not found");
}

[Link]("");
return;
}
------------------------------------------------------------------
Perfect Binary Tree Specific Level Order Traversal
Output should be like - 1 2 3 4 7 5 6 8 15 9 14 10 13 11 12 16 31
17 30 18 29 19 28 20 27 21 26 22 25 23 24

void printSpecificLevelOrder(Node node)

{
if (node == null)
return;

[Link]([Link]);

if ([Link] != null)
[Link](" " + [Link] + " " + [Link]);

if ([Link] == null)
return;

Queue<Node> q = new LinkedList<Node>();

[Link]([Link]);
[Link]([Link]);

Node first = null, second = null;

while (![Link]())
{
first = [Link]();
[Link]();
second = [Link]();
[Link]();

[Link](" " + [Link]+” “ +[Link]);

[Link](" " + [Link] + " "+[Link]);

if ([Link] != null)
{
[Link]([Link]);
[Link]([Link]);
[Link]([Link]);
[Link]([Link]);
}
}
}

------------------------------------------------------------------

Find sum of all left leaves in a given

Binary Tree
boolean isLeaf(Node node)
{
if (node == null)
return false;
 if ([Link] == null && [Link] == null)
return true;
return false;
}

int leftLeavesSum(Node node)

{
// Initialize result
int res = 0;
if (node != null)
{
if (isLeaf([Link]))
res += [Link];
else // Else recur for left child of root
res += leftLeavesSum([Link]);
res += leftLeavesSum([Link]);
}
return res;
}
------------------------------------------------------------------

Find sum of all left leaves in a given

Binary Tree
static void rightLeafSum(Node root)
{
if(root == null)
return;
if([Link] != null)
{
if([Link] == null && [Link] == null)
sum += [Link];
}
rightLeafSum([Link]);
rightLeafSum([Link]);
}
------------------------------------------------------------------

Find the maximum path sum between two leaves

of a binary tree
Node setTree(Node root){

Node temp = new Node(0);

//if tree is left most
if([Link]==null){
[Link]=temp;
}
else{ //if tree is right most
[Link]=temp;
 }

return root;
}
int maxPathSumUtil(Node node, Res res) {

// Base cases
if (node == null)
return 0;
if ([Link] == null && [Link] == null)
return [Link];
int ls = maxPathSumUtil([Link], res);
int rs = maxPathSumUtil([Link], res);
if ([Link] != null && [Link] != null) {
[Link] = [Link]([Link], ls + rs + [Link]);
return [Link](ls, rs) + [Link];
}
return ([Link] == null) ? rs + [Link]:ls + [Link];
}

int maxPathSum(Node node)

{
Res res = new Res();
[Link] = Integer.MIN_VALUE;
if([Link]==null || [Link]==null){
root=setTree(root);
}
maxPathSumUtil(root, res);
return [Link];
}
------------------------------------------------------------------

Find largest subtree sum in a tree

Input : 1
/ \
-2 3
/ \ \ /
4 5 2 -6
Output : 7
Subtree with largest sum is : -2
/ \
4 5
Also, entire tree sum is also 7.

static class INT

{
int v;
INT(int a)
{
v = a;
}
}
static int findLargestSubtreeSumUtil(Node root,INT ans)
{
if (root == null)
return 0;
int currSum = [Link] +
findLargestSubtreeSumUtil([Link], ans) +
findLargestSubtreeSumUtil([Link], ans);
ans.v = [Link](ans.v, currSum);
return currSum;
}
static int findLargestSubtreeSum(Node root)
{
if (root == null)
return 0;
INT ans = new INT(-9999999);
findLargestSubtreeSumUtil(root, ans);

return ans.v;
}
------------------------------------------------------------------

Lowest Common Ancestor in a Binary Tree

Following is a simple O(n) algorithm to find the LCA of n1 and
n2.
1. Find a path from the root to n1 and store it in a vector or array.
2. Find a path from the root to n2 and store it in another vector or array.
3. Traverse both paths till the values in arrays are the same. Return the common element just
before the mismatch.
Hashset we can do it.
------------------------------------------------------------------

Construct BST from its given level order

traversal
tatic Node LevelOrder(Node root , int data)
{
if(root == null)
{
root = getNode(data);
return root;
}
if(data <= [Link])
[Link] = LevelOrder([Link], data);
else
[Link] = LevelOrder([Link], data);
return root;
}
static Node constructBst(int arr[], int n)
{
if(n == 0)return null;
Node root = null;

for(int i = 0; i < n; i++)

root = LevelOrder(root , arr[i]);

return root;
}
------------------------------------------------------------------

Convert BST to Min Heap

private static void bstToArray(Node root,
ArrayList<Integer> arr)
{
// ArrayLIst stores elements in inorder fashion
if (root == null)
return;

bstToArray([Link], arr);

[Link]([Link]);

bstToArray([Link], arr);
}

static int index;

private static void arrToMinHeap(Node root,
ArrayList<Integer> arr)
{
if (root == null)
return;
[Link] = [Link](index++);

arrToMinHeap([Link], arr);
arrToMinHeap([Link], arr);
}
static void convertToMinHeap(Node root)
{
// initialize static index to zero
index = 0;
ArrayList<Integer> arr = new ArrayList<Integer>();
bstToArray(root, arr);

arrToMinHeap(root, arr);
}

------------------------------------------------------------------
Lowest Common Ancestor in a Binary Search Tree.
Node lca(Node node, int n1, int n2)
{
if (node == null)
return null;

// If both n1 and n2 are smaller than root, then LCA lies

in left
if ([Link] > n1 && [Link] > n2)
return lca([Link], n1, n2);

// If both n1 and n2 are greater than root, then LCA lies

in right
if ([Link] < n1 && [Link] < n2)
return lca([Link], n1, n2);

return node;
}
------------------------------------------------------------------

How to determine if a binary tree is height-

balanced?
boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */

int rh; /* for height of right subtree */

if (node == null)
return true;
lh = height([Link]);
rh = height([Link]);

if ([Link](lh - rh) <= 1 && isBalanced([Link])

&& isBalanced([Link]))
return true;
return false;
}

------------------------------------------------------------------
MATRIX -

Sorting rows of matrix in ascending order

followed by columns in descending order
Approach:
• Traverse all rows one by one and sort rows in ascending order using a simple array sort.
• Convert matrix to its transpose
 • Again sort all rows, but this time in descending order.
• Again convert a matrix to its transpose
static void sortByRow(Integer mat[][], int n,
boolean ascending)
{
for (int i = 0; i < n; i++)
{
if (ascending)
[Link](mat[i]);
else
[Link](mat[i],[Link]());
}
}
static void transpose(Integer mat[][], int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
// swapping element at index (i, j)
// by element at index (j, i)
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
static void sortMatRowAndColWise(Integer mat[][],int n)
{
sortByRow(mat, n, true);
transpose(mat, n);
sortByRow(mat, n, false);
transpose(mat, n);
}
------------------------------------------------------------------

Print matrix in zig-zag fashion

Given a matrix of 2D array of n rows and m columns. Print this matrix in ZIG-ZAG fashion as
shown in figure.
Input:
1 2 3
4 5 6
7 8 9
Output:
1 2 4 7 5 3 6 8 9

or

Zigzag (or diagonal)

traversal of Matrix
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

Diagonal printing of the above matrix is

1
5 2
9 6 3
13 10 7 4
17 14 11 8
18 15 12
19 16
20

// JAVA Code for Zigzag (or diagonal)

// traversal of Matrix
class GFG {

public static int R, C;

private static void diagonalOrder(int[][] arr)

{

/* through this for loop we choose each

element of first column as starting point
and print diagonal starting at it. arr[0][0],
arr[1][0]....arr[R-1][0] are all starting points */
for (int k = 0; k < R; k++) {
[Link](arr[k][0] + " ");

// set row index for next

// point in diagonal
int i = k - 1;

// set column index for

// next point in diagonal
int j = 1;

/* Print Diagonally upward */

while (isValid(i, j))
{
[Link](arr[i][j] + " ");

i--;

// move in upright direction

j++;
}

[Link]("");
}
 /* through this for loop we choose each element
of last row as starting point (except the
[0][c-1] it has already been processed in
previous for loop) and print diagonal
starting at it. arr[R-1][0], arr[R-1][1]....
arr[R-1][c-1] are all starting points */

// Note : we start from k = 1 to C-1;

for (int k = 1; k < C; k++) {
[Link](arr[R - 1][k] + " ");

// set row index for next

// point in diagonal
int i = R - 2;

// set column index for

// next point in diagonal
int j = k + 1;

/* Print Diagonally upward */

while (isValid(i, j))
{
[Link](arr[i][j] + " ");

// move in upright direction

i--;
j++;
}

[Link]("");
}
}

public static boolean isValid(int i, int j)

{
if (i < 0 || i >= R
|| j >= C || j < 0)
return false;
return true;
}

// Driver code
public static void main(String[] args)
{
int arr[][] = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 },
{ 17, 18, 19, 20 },
};

R = [Link];
 C = arr[0].length;

// Function call
diagonalOrder(arr);
}
}
------------------------------------------------------------------

Print matrix in diagonal pattern

// Java program to print matrix in

diagonal order
class GFG {
static final int MAX = 100;

static void printMatrixDiagonal(int mat[][], int n)

{
// Initialize indexes of element to be printed next
int i = 0, j = 0;

// Direction is initially from down to up

boolean isUp = true;

// Traverse the matrix till all elements get traversed

for (int k = 0; k < n * n;) {
// If isUp = true then traverse from downward
// to upward
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
[Link](mat[i][j] + " ");
k++;
}

// Set i and j according to direction

if (i < 0 && j <= n - 1)
i = 0;
if (j == n) {
i = i + 2;
j--;
}
}
 // If isUp = 0 then traverse up to down
else {
for (; j >= 0 && i < n; i++, j--) {
[Link](mat[i][j] + " ");
k++;
}

// Set i and j according to direction

if (j < 0 && i <= n - 1)
j = 0;
if (i == n) {
j = j + 2;
i--;
}
}

// Revert the isUp to change the direction

isUp = !isUp;
}
}

// Driver code
public static void main(String[] args)
{
int mat[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };

int n = 3;
printMatrixDiagonal(mat, n);
}
}

------------------------------------------------------------------

String -

Longest Palindromic Substring

String longestPalindrome(String s){
// code here
int n = [Link]();
int maxlen=1;
int start=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int flag=1;

for(int k=0;k<(j-i+1)/2;k++)
{
if([Link](i+k)!=[Link](j-k))
 flag=0;
}

if(flag!=0 && (j-i+1) > maxlen)

{
start = i;
maxlen = j-i+1;
}

}
}
String re = [Link](start,start+maxlen);
return re;

}
------------------------------------------------------------------------------------------------------------------------

Sort elements by frequency :

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then
print the one which came first.
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
Integer arr[] = new Integer[n];

for(int i=0;i<n;i++)
{
arr[i]=[Link]();
}
List<Integer> al = [Link](arr);
HashMap<Integer,Integer> hc = new HashMap<>();
HashMap<Integer,Integer> hi = new HashMap<>();

for(int i=0;i<n;i++)
{
if([Link](arr[i]))
{
[Link](arr[i],[Link](arr[i])+1);
 }
else
{
[Link](arr[i],1);
[Link](arr[i],i);
}
}

[Link](al, new Comparator<Integer>()

{
public int compare(Integer c1,Integer c2)
{
int f1 = [Link](c1);
int f2 = [Link](c2);
if(f1 != f2)
{
return f2-f1;
}
else
{
return c1 - c2;
}
}
});
for(int i=0;i<n;i++)
{
[Link]([Link](i)+" ");
}
[Link]();
------------------------------------------------------------------------------------------------------------------------
Minimum number of swaps required to sort an array
public static int minSwaps(int[] arr)
{
int n = [Link];
ArrayList <Pair <Integer, Integer> > arrpos =
new ArrayList <Pair <Integer,
Integer> > ();
for (int i = 0; i < n; i++)
[Link](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.
[Link](new Comparator<Pair<Integer,
Integer>>()
{
@Override
public int compare(Pair<Integer, Integer> o1,
Pair<Integer, Integer> o2)
{
if ([Link]() > [Link]())
return -1;

// We can change this to make

// it then look at the
// words alphabetical order
else if ([Link]().equals([Link]()))
return 0;

else
return 1;
}
});

Boolean[] vis = new Boolean[n];

[Link](vis, false);

// Initialize result
int ans = 0;

// Traverse array elements

for (int i = 0; i < n; i++)
{
if (vis[i] || [Link](i).getValue() == i)
continue;
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = true;
 // move to next node
j = [Link](j).getValue();
cycle_size++;
}

// Update answer by adding current cycle.

if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}

// Return result
return ans;
}

------------------------------------------------------------------------------------------------------------------------

FIND LCA FOR BT

public static Node LCA(Node root, int n1, int n2)
{
if (root == null)
return root;
if ([Link] == n1 || [Link] == n2)
return root;

Node left = LCA([Link], n1, n2);

Node right = LCA([Link], n1, n2);

if (left != null && right != null)

return root;
if (left == null && right == null)
return null;
if (left != null)
return LCA([Link], n1, n2);
else
return LCA([Link], n1, n2);
}

or
boolean inorder(Node node,ArrayList<Node> al,int x)
{
if(node==null) return false;

[Link]([Link]);
 if([Link]==x) return true;

if([Link]!=null && inorder([Link],al,x))

return true;

if([Link]!=null && inorder([Link],al,x))

return true;

[Link]([Link]()-1);
return false;
}

ArrayList<Node> al1 = new ArrayList<>();

ArrayList<Node> al2 = new ArrayList<>();

if(!inorder(node,al1,a) || !inorder(node,al2,b))
return -1;

int i;
for( i=0;i<[Link]() && i<[Link]();i++)
{
if([Link](i)!=[Link](i)) break;
}
int lca=[Link](i-1);
int d1=findD(lca,a,0);

int d2=findD(lca,b,0);
 return d1+d2;
}

int findD(Node node,int n,int d)

{
if(node==null) return -1;

if([Link]==n) return d;

int left= findD([Link],n,d+1);

if(left==-1) return findD([Link],n,d+1);

return left;
}
------------------------------------------------------------------------------------------------------------------------
-Min distance between two given nodes of a Binary Tree
public static int ans;
//Function that finds distance between two node.
public static int _findDistance(Node root, int n1, int n2)
{
if (root == null) return 0;
int left = _findDistance([Link], n1, n2);
int right = _findDistance([Link], n1, n2);
//if any node(n1 or n2) is found
if ([Link] == n1 || [Link] == n2)
{
if (left != 0 || right != 0)
{
ans = [Link](left, right);
return 0;
}
else
return 1;
}
//if current root is LCA of n1 and n2.
else if (left != 0 && right != 0)
{
ans = left + right;
return 0;
}
//if there is a descendant(n1 or n2).
else if (left != 0 || right != 0)
 //increment its distance
return [Link](left, right) + 1;
//if neither n1 nor n2 exist as descendant.
return 0;
}
// The main function that returns distance between n1
// and n2.
public static int findDistance(Node root, int n1, int n2)
{
ans = 0;
_findDistance(root, n1, n2);
return ans;
}

------------------------------------------------------------------------------------------------------------------------

Is Binary Tree Heap

boolean isMaxHeap(Node node)

{
if(node==null) return false;

Queue<Node> qq = new LinkedList<>();

[Link](node);

boolean nullTrue=false;

while(![Link]())
{
Node temp=[Link]();

//[Link]([Link]);

if([Link]!=null)
{
if(nullTrue || [Link] > [Link])
 return false;
[Link]([Link]);
}
else
nullTrue=true;

if([Link]!=null)
{
if(nullTrue || [Link] > [Link])
return false;
[Link]([Link]);
}
else nullTrue=true;

}
return true;

}
------------------------------------------------------------------------------------------------------------------------

Largest BST
static boolean checkBST(Node node,int min,int max)
{
if(node==null) return true;

if([Link] < min || [Link]> max) return false;

return checkBST([Link],min,[Link]-1) && checkBST([Link],[Link]+1,max);

}

static int count(Node node)

{
if(node==null) return 0;
 return 1+count([Link])+count([Link]);
}
static int ans=0;
static int largestBst(Node node)
{
ans=0;
return larBST(node);

static int larBST(Node node)

{
if(node==null) return 0;

if(checkBST(node,Integer.MIN_VALUE,Integer.MAX_VALUE))
{
int c=count(node);
// [Link](c);
ans= [Link](ans,c);

}
larBST([Link]);

larBST([Link]);

return ans;
}
------------------------------------------------------------------------------------------------------------------------
Connected Component in this Graph -

static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {

 int arr[][]=new int[V][V];
for(int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
{

if(i!=j && [Link](i).get(j)==1)

arr[i][j]=j;
}
}
return check(V,arr);
}

public static int check(int V,int arr[][])

{
boolean b[]=new boolean[V];
int c=0;
for(int i=0;i<V;i++)
{
if(!b[i])
{
DFS(b,arr,i);
c+=1;
}
}
return c;
}
public static void DFS(boolean b[],int arr[][],int v)
{
b[v]=true;
int arr1[]=arr[v];
for(int i=0;i<[Link];i++)
 {
int x = arr1[i];
if(!b[x])
{
DFS(b,arr,x);
}
}
}

------------------------------------------------------------------------------------------------------------------------
000
000
200
[
[1, 0, 1],
[0, 1, 0],
[1, 0, 1]
]

------------------------------------------------------------------------------------------------------------------------