Practical File

Of
Advanced Data Structure and Algorithms
E2UC503B (PR)

5th Semester
Section – 19

Submitted By – Submitted to –
Ritik Agarwal Dr. Vipul Narayan
22SCSE1010890
Program 1. Write a program to find the minimum and maximum elements in an array.
Source Code –
import java.util.Arrays;

class ProgramOne {

public static void findMinMax(int arr[], int res_arr[]){

for(int i=1; i<arr.length; i++){

if(res_arr[0]<arr[i]){

res_arr[0] = arr[i];

if(res_arr[1]>arr[i]){

res_arr[1] = arr[i];

public static void main(String[] args) {

int arr[] = {2,5,3,8,10,1,9};

int res_arr[] = new int[2];

res_arr[0] = arr[0];

res_arr[1] = arr[0];

findMinMax(arr, res_arr);

System.out.println("Array is: " + Arrays.toString(arr));

System.out.println("Max and min are: " + res_arr[0] + " " + res_arr[1]);

Output –
Program 2. Write a program to reverse an array.
Source Code –
import java.util.Arrays;

class ProgramTwo {

public static void reverse(int arr[]){

int j = arr.length-1;

int i = 0;

while(i<j){

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++;j--;

public static void main(String[] args) {

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

int right = arr.length-1;

int left = 0;

System.out.println("Original Array: " + Arrays.toString(arr));

reverse(arr);

System.out.println("Reversed Array: " + Arrays.toString(arr));

Output –
Program 3. Find kth Smallest/Largest element in an array.
Source Code –
class Solution {

public int findKthLargest(int[] nums, int k) {

if(nums.length==0){

return 0;

Arrays.sort(nums);

return nums[nums.length-k];

Output –
Program 4. Write a program to sort an array of 0s, 1s, 2s.
Source Code –
class Solution {

public void sortColors(int[] nums) {

int low = 0, mid = 0, high = nums.length-1;

while(mid<=high){

if(nums[mid]==0){

int temp = nums[mid];

nums[mid] = nums[low];

nums[low] = temp;

mid++; low++;

else if(nums[mid]==1){ mid++; }

else{

int temp = nums[mid];

nums[mid] = nums[high];

nums[high] = temp;

high--;

Output –
Program 5. Write a program to move all zeroes to end of array.
Source Code –
class Solution {

public void moveZeroes(int[] nums) {

int count = 0;

for(int i=0; i<nums.length; i++){

if(nums[i]!=0){

int temp = nums[i];

nums[i] = nums[count];

nums[count] = temp;

count++;

Output –
Program 6. Write a program to reverse a linked list.
Source Code –
Definition for singly-linked list.

public class ListNode {

int val;

ListNode next;

ListNode() {}

ListNode(int val) { this.val = val; }

ListNode(int val, ListNode next) { this.val = val; this.next = next; }

class Solution {

public ListNode reverseList(ListNode head) {

ListNode curr = head;

ListNode prev = null;

ListNode next;

while(curr!=null){

next = curr.next; curr.next = prev;

prev = curr; curr = next;

return prev;

Output –
Program 7. Write a program to detect a cycle in linked list.
Source Code –
Definition for singly-linked list.

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

public class Solution {

public boolean hasCycle(ListNode head) {

ListNode first = head;

ListNode second = head;

while(first!=null && first.next!=null){

first = first.next.next; second = second.next;

if(first==second){ return true; }

return false;

Output –
Program 8. Write a program to find the middle of a linked list.
Source Code –
Definition for singly-linked list.

public class ListNode {

int val;

ListNode next;

ListNode() {}

ListNode(int val) { this.val = val; }

ListNode(int val, ListNode next) { this.val = val; this.next = next; }

class Solution {

public ListNode middleNode(ListNode head) {

ListNode fast = head;

ListNode slow = head;

while(fast!=null && fast.next!=null){

fast = fast.next.next;

slow = slow.next;

return slow;

Output –
Program 9. Write a program to merge two sorted linked lists.
Source Code –
class Solution {

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

if(list1!=null && list2!=null){

if(list1.val<list2.val){

list1.next=mergeTwoLists(list1.next,list2);

return list1;

else{

list2.next=mergeTwoLists(list1,list2.next);

return list2;

if(list1==null){

return list2;

return list1;

Output –
Program 10. Write a program to remove nth node from end of list.
Source Code –
class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {

int size=0;

ListNode temp=head;

while(temp!=null){

temp=temp.next;

size++;

if(n==size){

head=head.next; return head;

int i=1; int itofind=size-n;

ListNode prev=head;

while(i<itofind){

prev=prev.next; i++;

prev.next=prev.next.next;

return head;

Output –
Program 11. Write a program to implement stack using array.
Source Code –
class MyStack {

private int[] arr;

private int top;

public MyStack() {

arr = new int[1000];

top = -1;

public void push(int x) {

top++;

arr[top] = x;

public int pop() {

if(top>-1){

int x = arr[top];

top--;

return x;

else{

return -1;

Output –
Program 12. Write a program to implement stack using linked list.
Source Code –
class MyStack {

// class StackNode {

// int data;

// StackNode next;

// StackNode(int a) {

// data = a;

// next = null;

// }

// }

StackNode top;

void push(int a) {

StackNode newNode=new StackNode(a);

newNode.next=top;

top=newNode;

int pop() {

if(top==null) return -1;

int popped=top.data;

top=top.next;

return popped;

Output –
Program 13. Write a program to check for balanced parenthesis.
Source Code –
class Solution {

public boolean isValid(String s) {

int Round = 0;

int Square = 0;

int Curly = 0;

for(int i=0; i<s.length(); i++){

if(s.charAt(i)=='('){

Round++;

if(s.charAt(i)==')'){

Round--;

if(Round<0){

return false;

if(s.charAt(i)=='['){

Square++;

if(s.charAt(i)==']'){

Square--;

if(Square<0){

return false;

if(s.charAt(i)=='{'){

Curly++;

if(s.charAt(i)=='}'){

Curly--;
 if(Curly<0){

return false;

if(Round!=0 || Square!=0 || Curly!=0){

return false;

return true;

Output –
Program 14. Write a program to evaluate postfix expression.
Source Code –
class Solution
{
public static int evaluatePostFix(String expression)
{
Stack<Integer> stack = new Stack<>();
for (char ch : expression.toCharArray()) {
if (Character.isDigit(ch)) {
stack.push(ch - '0');
} else {
int operand2 = stack.pop();
int operand1 = stack.pop();
switch (ch) {
case '+':
stack.push(operand1 + operand2);
break;
case '-':
stack.push(operand1 - operand2);
break;
case '*':
stack.push(operand1 * operand2);
break;
case '/':
stack.push(operand1 / operand2);
break;
}
}
}
return stack.pop();
}
}
Output –
Program 15. Write a program to find next greater element for each element in an array.
Source Code –
class Solution {

public int[] nextGreaterElement(int[] nums1, int[] nums2) {

int i = 0;

int[] result = new int[nums1.length];

boolean found = false;

int j = 0;

while (j < nums2.length) {

if (i >= nums1.length) {

return result;

else {

if (nums1[i] == nums2[j]) {

int k = j + 1;

while (k < nums2.length) {

if (nums2[j] < nums2[k]) {

result[i] = nums2[k];

found = true;

break;

k++;

j = -1;

if (found) {

found = false;

} else {

result[i] = -1;

i = i + 1;

}
 }

j++;

return result;

Output –
Program 16. Write a program to implement a queue using Arrays.
Source Code –
class MyQueue {

int front, rear, Max = 100005;

int arr[] = new int[100005];

MyQueue(){ front=0; rear=0; }

void push(int x)

if(rear>=Max){

System.out.println("Overflow");

else{

arr[rear] = x;

rear++;

int pop()

if(front>rear || front==rear){

return -1;

else{

int x = arr[front];

front++;

return x;

}
Output –
Program 17. Implement a queue using Linked List.
Source Code –
/*The structure of the node of the queue is

class QueueNode

int data;

QueueNode next;

QueueNode(int a)

data = a;

next = null;

}*/

class MyQueue

QueueNode front, rear = null;

//Function to push an element into the queue.

void push(int a)

// Your code here

// initially taking that queue is empty

QueueNode newNode = new QueueNode(a);

if (rear == null) {

front = rear = newNode;

return;

rear.next = newNode;

// newNode.next = null;

rear = newNode;
 }

//Function to pop front element from the queue.

int pop()

// Your code here

if(front==null && rear == null){

return -1;

QueueNode element = front;

front = front.next;

if(front==null){

rear = null;

return element.data;

Output –
Program 18. Write a program to implement a circular queue.
Source Code –
class MyCircularQueue {

private int space;

private ListNode head;

private ListNode tail;

public MyCircularQueue(int k) {

this.space = k;

this.head = new ListNode(0); // Dummy head node

this.tail = new ListNode(0); // Dummy tail node

this.head.next = this.tail;

this.tail.prev = this.head;

public boolean enQueue(int value) {

if (isFull()) {

return false;

ListNode cur = new ListNode(value, tail.prev, tail);

tail.prev.next = cur;

tail.prev = cur;

space--;

return true;

public boolean deQueue() {

if (isEmpty()) {

return false;

head.next = head.next.next;
 head.next.prev = head;

space++;

return true;

public int Front() {

if (isEmpty()) {

return -1;

return head.next.val;

public int Rear() {

if (isEmpty()) {

return -1;

return tail.prev.val;

public boolean isEmpty() {

return head.next == tail;

public boolean isFull() {

return space == 0;

private class ListNode {

int val;

ListNode prev;

ListNode next;
 ListNode(int val) {

this.val = val;

ListNode(int val, ListNode prev, ListNode next) {

this.val = val;

this.prev = prev;

this.next = next;

/**

* Your MyCircularQueue object will be instantiated and called as such:

* MyCircularQueue obj = new MyCircularQueue(k);

* boolean param_1 = obj.enQueue(value);

* boolean param_2 = obj.deQueue();

* int param_3 = obj.Front();

* int param_4 = obj.Rear();

* boolean param_5 = obj.isEmpty();

* boolean param_6 = obj.isFull();

*/

Output –
Program 19. Write a program to generate binary numbers from 1 to N.
Source Code –
import java.util.*;

public class BinaryNumbers {

static class Node {

String data;

Node next;

Node(String data) {

this.data = data;

next = null;

static class Queue {

Node front;

Node rear;

void enqueue(String data) {

Node newNode = new Node(data);

if (front == null && rear == null) {

front = rear = newNode;

} else {

rear.next = newNode;

rear = newNode;

String dequeue() {

if (front == null) {

return "-1";

String data = front.data;

 front = front.next;

if (front == null) {

rear = null;

return data;

static void printBinary(int n) {

Queue q1 = new Queue();

String temp = "1";

q1.enqueue(temp);

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

temp = q1.dequeue();

System.out.print(temp + " ");

q1.enqueue(temp + "0");

q1.enqueue(temp + "1");

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.print("Enter the num: ");

int n = sc.nextInt();

printBinary(n);

Output –
Program 20. Write a program to implement a queue using stack.
Source Code –
class MyStack {

private Queue<Integer> queue = new LinkedList<>();

public void push(int x) {

queue.add(x);

for(int i = 1;i<queue.size();i++) {

queue.add(queue.remove());

public int pop() {

return queue.remove();

public int top() {

return queue.peek();

public boolean empty() {

return queue.isEmpty();

/**

* Your MyStack object will be instantiated and called as such:

* MyStack obj = new MyStack();

* obj.push(x);

* int param_2 = obj.pop();

* int param_3 = obj.top();

* boolean param_4 = obj.empty();

*/
Output –
Program 21. Write a class to implement a basic binary tree with insert, delete, and
traversal operations.
Source Code –
import java.io.*;
import java.util.Scanner;
import java.util.Stack;
class TreeNode {
int info;
TreeNode left;
TreeNode right;
TreeNode(int info) {
this.info = info;
left = null;
right = null;
}
}
class BinaryTree{
public static TreeNode create() {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter data to be inserted or type -1 for no insertion: ");
int data = scanner.nextInt();
if (data == -1)
return null;
TreeNode tree = new TreeNode(data);
System.out.print("Enter left child of " + data + ": ");
tree.left = create();
System.out.print("Enter right child of " + data + ": ");
tree.right = create();
return tree;
}
 public static void preorder(TreeNode root) {
if (root == null)
return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
System.out.print(current.info + " ");
if (current.right != null)
stack.push(current.right);
if (current.left != null)
stack.push(current.left);
}
System.out.println();
}
public static void main(String[] args) {
TreeNode root = null;
root = create();
preorder(root);
}
}

Output –
Program 22. Write a function to perform inorder traversal of a binary tree.
Source Code –
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> answer = new ArrayList<>();
inOrder(root, answer);
return answer;
}
private void inOrder(TreeNode root, List<Integer> answer){
if(root==null){
return;
}
inOrder(root.left, answer);
answer.add(root.val);
inOrder(root.right, answer);
}
}

Output –
Program 23. Write a function to perform preorder traversal of a binary tree.
Source Code –
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> answer = new ArrayList<>();

preOrder(root, answer);
return answer;
}
private void preOrder(TreeNode root, List<Integer> answer){
if(root==null){
return;
}
answer.add(root.val);
preOrder(root.left, answer);
preOrder(root.right, answer);
}
}

Output –
Program 24. Write a function to perform post-order traversal of a binary tree.
Source Code –
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> answer = new ArrayList<>();
preOrder(root, answer);
return answer;
}
private void preOrder(TreeNode root, List<Integer> answer){
if(root==null){
return;
}
preOrder(root.left, answer);
preOrder(root.right, answer);
answer.add(root.val);
}
}

Output –
Program 25. Write a function to perform level order traversal of a binary tree.
Source Code –
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> answer = new ArrayList<>();
dfs(root, 0, answer);
return answer;
}
private void dfs(TreeNode root, int level, List<List<Integer>> answer){
if(root==null){return;}
if(answer.size()==level){
answer.add(new ArrayList<>());
}
answer.get(level).add(root.val);
dfs(root.left, level+1, answer);
dfs(root.right, level+1, answer);
}
}

Output –
Program 26. Write a function to find the height of a binary tree.
Source Code –
class Solution {
public int maxDepth(TreeNode root) {
return root==null?0:1+Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

Output –
Program 27. Write a function to find the diameter of a binary tree.
Source Code –
class Solution {
int length;
public int diameterOfBinaryTree(TreeNode root) {
length = 0;
calLength(root);
return length;
}
private int calLength(TreeNode node){
if(node==null){
return 0;
}
int left = calLength(node.left);
int right = calLength(node.right);
length = Math.max(length, left+right);
return 1+Math.max(left, right);
}
}

Output –
Program 28. Write a function to check if a binary tree is height balanced.
Source Code –
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (Height(root) == -1) return false;
return true;
}
public int Height(TreeNode root) {
if (root == null) return 0;
int leftHeight = Height(root.left);
int rightHight = Height(root.right);
if (leftHeight == -1 || rightHight == -1) return -1;
if (Math.abs(leftHeight - rightHight) > 1) return -1;
return Math.max(leftHeight, rightHight) + 1;
}
}

Output –
Program 29. Write a function to find the lowest common ancestor of two nodes in a
binary tree.
Source Code –
class Solution {
public boolean path(TreeNode root, List<Integer> ans, int x) {
if (root == null) return false;
ans.add(root.val);
if (root.val == x) return true;
if (path(root.left, ans, x) || path(root.right, ans, x)) return true;
ans.remove(ans.size() - 1);
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<Integer> pathp = new ArrayList<>();
List<Integer> pathq = new ArrayList<>();
path(root, pathp, p.val);
path(root, pathq, q.val);
int i;
for (i = 0; i < pathp.size() && i < pathq.size(); i++) {
if (!pathp.get(i).equals(pathq.get(i))) break;
}
return new TreeNode(pathp.get(i - 1));
}
}

Output –
Program 30. Write a class to implement a basic graph using an adjacency list with
methods to add vertices and edges.
Source Code –
class Solution {
public void addVertices(TreeNode root) {
if (root == null) return true;
if (Height(root) == -1) return false;
return true;
}
Public void addEdges(TreeNode root) {
if (root == null) return 0;
int leftHeight = Height(root.left);
int rightHight = Height(root.right);
if (leftHeight == -1 || rightHight == -1) return -1;
if (Math.abs(leftHeight - rightHight) > 1) return -1;
return Math.max(leftHeight, rightHight) + 1;
}
}

Output –
Program 31. Write a function to perform BFS on a graph from a given start vertex.
Source Code –
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> ans = new ArrayList<>();
Queue<List<Integer>> q = new LinkedList<>();
List<Integer> currList = new ArrayList<>();
currList.add(0);
q.add(currList);
while (!q.isEmpty()) {
currList = q.poll();
int v = currList.get(currList.size() - 1);
if (v == graph.length - 1) {
ans.add(currList);
continue;
}
for (int i : graph[v]) {
List<Integer> temp = new ArrayList<>(currList);
temp.add(i);
q.add(temp);
}
}
return ans;
}
}

Output –
Program 32. Write a function to perform DFS on a graph from a given start vertex.
Source Code –
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> answer = new ArrayList<>();
dfs(0, graph, new ArrayList<Integer>(), answer);
return answer;
}
private void dfs(int source, int[][] graph, ArrayList<Integer> list, List<List<Integer>> answer) {
list.add(source);
int[] path = graph[source];
if(source==graph.length-1){
answer.add(new ArrayList<>(list));
list.remove(list.size()-1);
}
for(int i=0; i<path.length; i++){
dfs(path[i], graph, list, answer);
}
list.remove(Integer.valueOf(source));
return;
}
}

Output –
Program 33. Write a function to detect if there is a cycle in an undirected graph.
Source Code –
class Solution {
public boolean isCycle(ArrayList<ArrayList<Integer>> adj) {
boolean[]visited = new boolean[adj.size()];
boolean ans = false;
for(int i = 0;i<visited.length;i++){
if(!visited[i])ans = ans || solve(adj,i,-1,visited);
}
return ans;
}
boolean solve(ArrayList<ArrayList<Integer>> adj,int u,int par,boolean[]visited){
if(visited[u])return true;
visited[u] = true;
boolean ans = false;
for(int v:adj.get(u)){
if(v!=par){
ans = ans || solve(adj,v,u,visited);
}
}
return ans;
}
}

Output –
Program 34. Write a function to find the number of connected components in an
undirected graph.
Source Code –
class Solution {
public int findCircleNum(int[][] isConnected) {
int answer = 0;
boolean[] visited = new boolean[isConnected.length];
for (int i = 0; i < isConnected.length; i++) {
if (!visited[i]) {
answer++;
dfs(isConnected, i, visited);
}
}
return answer;
}
private void dfs(int grid[][], int row, boolean[] visited) {
visited[row]=true;
for(int i=0; i<grid.length; i++){
if(!visited[i] && grid[row][i]==1){
visited[i]=true;
dfs(grid, i, visited);
}
}
return;
}
}
Output –
Program 35. Write a function to find the Minimum Spanning Tree of a graph using
Kruskal’s algorithm.
Source Code –
class Solution {
public static int find(int x,int parent[]){
if(x == parent[x]) return x;

return parent[x] = find(parent[x],parent);

}
public static void Union(int x,int y,int parent[],int rank[]){
int x_parent = find(x,parent);
int y_parent = find(y,parent);

if(x_parent == y_parent) return;

if(rank[x_parent] > rank[y_parent]){

parent[y_parent] = x_parent;
}
else if(rank[y_parent] > rank[x_parent]){
parent[x_parent] = y_parent;
}
else{
parent[x_parent] = y_parent;
rank[y_parent]++;
}
}
static int spanningTree(int V, int E, List<List<int[]>> mat) {
// Code Here.
int parent[] = new int[V];
int rank[] = new int[V];

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

 parent[i] = i;
rank[i] = 1;
}
ArrayList<int[]>adj = new ArrayList<>();
for(int u = 0; u < mat.size(); u++){
for(int arr[] : mat.get(u)){
int v = arr[0];
int w = arr[1];

adj.add(new int[]{u,v,w});
}
}
Collections.sort(adj,(a,b)->a[2]-b[2]);

int sum = 0;
for(int edge[]: adj){
int u = edge[0];
int v = edge[1];
int w = edge[2];

int u_parent = find(u,parent);

int v_parent = find(v,parent);
if(u_parent != v_parent){
sum+=w;
Union(u,v,parent,rank);
}
}

return sum;
}
}
Output –
Program 36. Write a function to find the Minimum Spanning Tree of a graph using
Prim’s algorithm.
Source Code –
class Pair{
int weight;
int node;
Pair(int weight, int node){
this.weight = weight;
this.node = node;
}
}
class Solution {
static int spanningTree(int V, int E, List<List<int[]>> adj) {
PriorityQueue<Pair> pq = new PriorityQueue<>((x,y) -> x.weight - y.weight);
boolean[] visited = new boolean[V];
pq.add(new Pair(0,0));
int sum = 0;
while(!pq.isEmpty()){
int wt = pq.peek().weight;
int nd = pq.peek().node;
pq.remove();
if(visited[nd]) continue;
visited[nd] = true;
sum += wt;
for (int[] edge : adj.get(nd)) {
int edW = edge[1];
int adjNode = edge[0];
if (!visited[adjNode]) {
pq.add(new Pair(edW, adjNode));
}
}
}
 return sum;
}
}

Output –
Program 37. Write a function to compute the nth Fibonacci number using dynamic
programming.
Source Code –
class Solution {
private int fibo(int n, int[] dp){
if(n<=1){
return dp[n]=n;
}
else if(dp[n]!=0){
return dp[n];
}
return dp[n] = fibo(n-1, dp)+fibo(n-2, dp);
}
public int fib(int n) {
int[] dp = new int[n+1];
return fibo(n, dp);
}
}

Output –
Program 38. Write a function to determine how many distinct ways there are to climb a
staircase with n steps if you can climb either 1 or 2 steps at a time.
Source Code –
class Solution {
private int fibo(int n, int[] dp){
if(n<=2){
return dp[n]=n;
}
else if(dp[n]!=0){
return dp[n];
}
return dp[n] = fibo(n-1, dp)+fibo(n-2, dp);
}
public int climbStairs(int n) {
int[] dp = new int[n+1];
return fibo(n, dp);
}
}

Output –
Program 39. Write a function to determine the minimum cost to reach the top of a
staircase given a list of costs associated with each step.
Source Code –
class Solution {
// bottom-up approach
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int dp[] = new int[n + 1];
dp[n] = 0;
dp[n-1] = cost[n-1];
for(int i = n-2; i>=0; i--){
int c = dp[i+1]<dp[i+2]?dp[i+1]:dp[i+2];
dp[i] = cost[i] + c;
}
return dp[0]<dp[1]?dp[0]:dp[1];
}
}

Output –
Program 40. Write a function to determine the maximum amount of money you can rob
from a row of houses without robbing two adjacent houses.
Source Code –
class Solution {
private int calMax(int[] nums, int[] dp, int n){
if(n<0){
return 0;
}
if(dp[n]!=-1){
return dp[n];
}
return dp[n] = Math.max(calMax(nums, dp, n-1), nums[n]+calMax(nums, dp, n-2));
}
public int rob(int[] nums) {
int dp[] = new int[nums.length];
Arrays.fill(dp, -1);
return calMax(nums, dp, nums.length-1);
}
}

Output –
Program 41. Write a function to find the contiguous subarray with the maximum sum.
Source Code –
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int max = Integer.MIN_VALUE, sum = 0;

for(int i=0;i<n;i++){
sum += nums[i];
max = Math.max(sum,max);

if(sum<0) sum = 0;
}

return max;
}
}

Output –
Program 42. Given a set of activities with start and end times, select the maximum
number of activities that do not overlap.
Source Code –
class Solution {
public int activitySelection(List<Integer> start, List<Integer> end) {
int count = 1;
int idx = 0;
for (int i = 0; i < end.size() - 1; i++){
for (int j = 0; j < end.size() - i - 1; j++){
if (end.get(j) > end.get(j + 1)) {
int temp = end.get(j);
end.set(j, end.get(j+1));
end.set(j+1, temp);
temp = start.get(j);
start.set(j, start.get(j+1));
start.set(j+1, temp);
}
}
}
int s = end.get(0);
for(int i=1; i<end.size(); i++){
if(start.get(i)>s){
count++;
s = end.get(i);
}
}
return count;
}
}
Output –
Program 43. Given weights and values of items and the maximum capacity of a
knapsack, determine the maximum value that can be obtained by including fractions of
items.
Source Code –
class Solution {
int[][] dp;
public int coinChange(int[] coins, int amount) {
dp = new int[coins.length+1][amount+1];
for(int i = 0;i<dp.length;i++)
{
for(int j = 0;j<dp[0].length;j++)
{
if(i == 0)
dp[i][j] = Integer.MAX_VALUE - 1;
if(j == 0)
dp[i][j] = 0;
if(i == 1 && j!=0)
{
if(j%coins[0] == 0)
dp[i][j] = j/coins[0];
else
dp[i][j] = Integer.MAX_VALUE - 1;
}
}
}
for(int i = 2;i<dp.length;i++)
{
for(int j = 1;j<dp[0].length;j++)
{
if(coins[i-1]<=j)
dp[i][j] = Math.min(1+dp[i][j-coins[i-1]],dp[i-1][j]);
else
dp[i][j] = dp[i-1][j];
 }
}
if(dp[coins.length][amount] >= Integer.MAX_VALUE - 1)
return -1;
return dp[coins.length][amount];
}
}

Output –
Program 44. Given a set of characters and their frequencies, construct the Huffman
Tree to encode the characters.
Source Code –
class Solution {
static public class Node {
int val;
Node left, right;
public Node(int val, Node left, Node right) {
this.val = val; this.left = left; this.right = right;
}
}
public ArrayList<String> huffmanCodes(String S, int f[], int N)
{
PriorityQueue<Node> pq = new PriorityQueue<Node>((a,b)-> (a.val != b.val) ? a.val - b.val : 1);
for(int v : f) {
pq.add(new Node(v, null, null));
}

while(pq.size()>1) {
Node n1 = pq.poll(), n2 = pq.poll();
pq.add(new Node(n1.val + n2.val, n1, n2));
}

ArrayList<String> res = new ArrayList();

traverse(pq.poll(), "", res);
return res;
}

void traverse(Node node, String code, ArrayList<String> strs) {

if(node.left == null) {
strs.add(code);
} else {
 traverse(node.left, code+'0', strs);
traverse(node.right, code+'1', strs);
}
}
}

Output –
Program 45. Given a set of jobs, each with a deadline and profit, maximize the total
profit by scheduling the jobs to be done before their deadlines.
Source Code –
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n=startTime.length;
int[][] events=new int[n][3];
for(int i=0;i<n;i++){
events[i][0]=startTime[i];
events[i][1]=endTime[i];
events[i][2]=profit[i];
}
Arrays.sort(events,(a,b)->Integer.compare(a[0], b[0]));
Integer[] dp=new Integer[n];
return dfs(events,0,n,dp);
}

public int dfs(int[][] events, int idx, int n,Integer[] dp){

if(idx==n)return 0;
if(dp[idx]!=null)return dp[idx];
int nextIdx=findNext(events, idx,n);
int pick=events[idx][2]+dfs(events, nextIdx, n,dp);
int notPick=dfs(events, idx+1, n,dp);
return dp[idx]= Math.max(pick,notPick);
}
public int findNext(int[][] events, int idx, int n){
int ans=n;
int l=idx+1;
int r=n-1;
while(l<=r){
int mid=(l+r)>>1;
if(events[idx][1]<=events[mid][0]){
 ans=mid;
r=mid-1;
}else {
l=mid+1;
}
}
return ans;
}
}

Output –
Program 46. Given different denominations of coins and an amount, find the minimum
number of coins needed to make up that amount.
Source Code –
class Solution {
int[][] dp;
public int coinChange(int[] coins, int amount) {
dp = new int[coins.length+1][amount+1];
for(int i = 0;i<dp.length;i++)
{
for(int j = 0;j<dp[0].length;j++)
{
if(i == 0)
dp[i][j] = Integer.MAX_VALUE - 1;
if(j == 0)
dp[i][j] = 0;
if(i == 1 && j!=0)
{
if(j%coins[0] == 0)
dp[i][j] = j/coins[0];
else
dp[i][j] = Integer.MAX_VALUE - 1;
}
}
}
for(int i = 2;i<dp.length;i++)
{
for(int j = 1;j<dp[0].length;j++)
{
if(coins[i-1]<=j)
dp[i][j] = Math.min(1+dp[i][j-coins[i-1]],dp[i-1][j]);
else
dp[i][j] = dp[i-1][j];
 }
}
if(dp[coins.length][amount] >= Integer.MAX_VALUE - 1)
return -1;
return dp[coins.length][amount];
}
}

Output –
Program 47. Place N queens on an N×N chessboard so that no two queens threaten each
other.
Source Code –
public class Solution {
private Set<Integer> col = new HashSet<Integer>();
private Set<Integer> diag1 = new HashSet<Integer>();
private Set<Integer> diag2 = new HashSet<Integer>();

public List<List<String>> solveNQueens(int n) {

List<List<String>> res = new ArrayList<List<String>>();
dfs(res,new ArrayList<String>(), 0, n);
return res;
}
private void dfs(List<List<String>> res, List<String> list, int row, int n){
if (row == n){
res.add(new ArrayList<String>(list));
return;
}
for (int i = 0; i < n; i++){
if (col.contains(i) || diag1.contains(row + i) || diag2.contains(row - i)) continue;
char[] charArray = new char[n];
Arrays.fill(charArray, '.');
charArray[i] = 'Q';
String rowString = new String(charArray);
list.add(rowString);
col.add(i);
diag1.add(row + i);
diag2.add(row - i);
dfs(res, list, row + 1, n);
list.remove(list.size() - 1);
col.remove(i);
diag1.remove(row + i);
 diag2.remove(row - i);
}
}
}

Output –
Program 48. Generate all possible permutations of a given list of numbers or characters.
Source Code –
public class Solution {
public void permuteRec(int[] nums, int begin, List<List<Integer>> result) {
if (begin == nums.length) {
List<Integer> temp = new ArrayList<Integer>();
for (int num : nums) temp.add(num);
result.add(temp);
return;
}
for (int i = begin; i < nums.length; i++) {
// Swap
int temp = nums[begin];
nums[begin] = nums[i];
nums[i] = temp;

permuteRec(nums, begin + 1, result);

// Swap back
temp = nums[begin];
nums[begin] = nums[i];
nums[i] = temp;
}
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
permuteRec(nums, 0, result);
return result;
}
}
Output –
Program 49. Generate all possible subsets of a given set of numbers.
Source Code –
class Solution {
public List<List<Integer>> subsets(int[] nums) {
Arrays.sort(nums); // make sure subsets are ordered
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>()); // start with empty set
for (int i = 0; i < nums.length; ++i) {
for (int j = 0, size = result.size(); j < size; ++j) { // remember
List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
subset.add(nums[i]); // expand
result.add(subset); // collect
}
}
return result;
}
}

Output –