import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
import java.util.Stack;
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if (stack.isEmpty()) return;
int popped = stack.pop();
if (popped == minStack.peek()) {
minStack.pop();
}
}
public int top() {
if (stack.isEmpty()) return -1; // or throw an exception
return stack.peek();
}
public int getMin() {
if (minStack.isEmpty()) return -1; // or throw an exception
return minStack.peek();
}
}
import java.util.*;
public class celeb{
static int check(int mat[][]){
Stack <Integer> st = new Stack<>();
for (int i=0;i<mat.length; i++){
st.push(i);
}
while(st.size() >1){
int row = st.pop();
int col = st.pop();
if(mat[row][col] == 1)
st.push(col);
else
st.push(row);
}
int x = st.pop();
for(int i= 0;i< mat.length;i++){
if (i == x)
continue;
if (mat[x][i] == 1)
return -1;
}
for (int i=0;i<mat.length;i++){
if (i==x)
continue;
if(mat[i][x] == 0)
return -1;
}
return x;
}
public static void main(String args[]){
Scanner sc = new Scanner (System.in);
int n = sc.nextInt();
int mat [][] = new int [n][n];
for (int i = 0; i<n;i++){
for(int j=0;j<n;j++){
mat[i][j]=sc.nextInt();
}
}
System.out.println(check(mat));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void toh(int n, char s, char d, char a){
if(n==1){
System.out.println("Move disk 1 from "+s+" to "+d);
return;
}
toh(n-1,s,a,d);
System.out.println("Move disk "+n+" from "+s+" to "+d);
toh(n-1,a,d,s);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
toh(n,'A','B','C');
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void check(int arr[], int day[]){
Stack<Integer> st=new Stack<>();
st.push(0);
day[0]=1;
for(int i=1;i<arr.length;i++){
while(!st.isEmpty() && arr[st.peek()]<=arr[i])
st.pop();
day[i]=(st.isEmpty()? i+1 : i-st.peek());
st.push(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int arr [] =new int[n];
for(int i =0;i<n;i++){
arr[i] = sc.nextInt();
}
int day []=new int[n];
check(arr, day);
System.out.print(Arrays.toString(day));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class PD{
int data;
int pri;
PD(int d,int p){
data=d;
pri=p;
}
}
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Comparator<PD> comparator = (e1,e2) -> {
return Integer.compare(e2.pri,e1.pri);
};
PriorityQueue<PD> pq = new PriorityQueue<>(comparator);
for (int i = 0; i < n; i++) {
int data = sc.nextInt();
int priority = sc.nextInt();
pq.add(new PD(data, priority));
}
// Access element and priority separately while peeking/popping
while (!pq.isEmpty()) {
PD topElement = pq.poll();
System.out.println("Element with highest priority: " + topElement.data + " (priority: " + topElement.pri + ")");
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int arr[]=new int [n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
for(int i=0;i<=n-k;i++){
int max=0;
for(int j=0;j<k;j++){
if(arr[i+j]>max)
max=arr[i+j];
}
System.out.print(max + " ");
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static boolean check(int []ip, int []op){
Stack<Integer> st=new Stack<>();
int j=0;
for(int i=0;i<ip.length;i++){
st.push(ip[i]);
while (!st.isEmpty() && st.peek()==op[j]) {
st.pop();
j++;
}
}
return st.isEmpty();
}
public static void main(String[] args) {
Scanner sc = new Scanner (System.in);
int n = sc.nextInt();
int ip[] =new int [n];
int op[] = new int [n];
for (int i=0;i<n;i++)
ip[i] = sc.nextInt();
for (int i=0;i<n;i++)
op[i] = sc.nextInt();
System.out.println(check(ip,op));
}
}
import java.util.*;
class Node {
int val;
Node left;
Node right;
Node() {}
Node(int val) {
this.val = val;
}
Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Main {
public static Node createBinaryTree(int[] arr) {
if (arr == null || arr.length == 0) return null;
Node root = new Node(arr[0]);
Queue<Node> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
Node current = queue.poll();
if (i < arr.length && arr[i] != -1) {
current.left = new Node(arr[i]);
queue.add(current.left);
}
i++;
if (i < arr.length && arr[i] != -1) {
current.right = new Node(arr[i]);
queue.add(current.right);
}
i++;
}
return root;
}
public static Node prev=null,first=null,second=null;
public static void inorder(Node root) {
if(root==null)
return ;
inorder(root.left);
if(prev!=null&&root.val<prev.val){
if(first==null)
first=prev;
second=root;
}
prev=root;
inorder(root.right);
}
static void printInorder(Node node) {
if (node == null)
return;
printInorder(node.left);
System.out.print(node.val+" ");
printInorder(node.right);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s[] = sc.nextLine().split(" ");
int n = s.length;
int arr[] = new int[n];
for(int i=0;i<n;i++){
if(! s[i].equals("N"))
arr[i]=Integer.parseInt(s[i]);
else
arr[i]=-1;
}
Node root=createBinaryTree(arr);
inorder(root);
int temp=first.val;
first.val=second.val;
second.val=temp;
printInorder(root);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Node{
int data;
Node left,right;
Node(int x) {
data=x;
left=right=null;
}
}
class Main {
public static Node createBinaryTree(int[] arr) {
if (arr == null || arr.length == 0) return null;
Node root = new Node(arr[0]);
Queue<Node> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
Node current = queue.poll();
if (i < arr.length && arr[i] != -1) {
current.left = new Node(arr[i]);
queue.add(current.left);
}
i++;
if (i < arr.length && arr[i] != -1) {
current.right = new Node(arr[i]);
queue.add(current.right);
}
i++;
}
return root;
}
public static void leftView(Node root){
Queue<Node> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int n=q.size();
for(int i=1;i<=n;i++){
Node curr=q.poll();
if(i==1)
System.out.print(curr.data+" ");
if(curr.left!=null){
q.add(curr.left);
}
if(curr.right!=null){
q.add(curr.right);
}
}
}
}
public static void rightView(Node root){
Queue<Node> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int n=q.size();
for(int i=1;i<=n;i++){
Node curr=q.poll();
if(i==n)
System.out.print(curr.data+" ");
if(curr.left!=null){
q.add(curr.left);
}
if(curr.right!=null){
q.add(curr.right);
}
}
}
}
public static void topView(Node root){
if (root == null) return ;
class Pair {
Node node;
int hd;
Pair(Node node, int hd) {
this.node = node;
this.hd = hd;
}
}
Map<Integer,Integer> mp = new TreeMap<>();
Queue<Pair> q=new LinkedList<>();
q.add(new Pair(root,0));
while(!q.isEmpty()){
Pair curr=q.poll();
Node node=curr.node;
int hd=curr.hd;
if(!mp.containsKey(hd)){
mp.put(hd,node.data);
}
if(node.left!=null){
q.add(new Pair(node.left,hd-1));
}
if(node.right!=null){
q.add(new Pair(node.right,hd+1));
}
}
for (int data : mp.values()) {
System.out.print(data+" ");
}
}
public static void bottomView(Node root){
if (root == null) return ;
class Pair {
Node node;
int hd;
Pair(Node node, int hd) {
this.node = node;
this.hd = hd;
}
}
Map<Integer,Integer> mp = new TreeMap<>();
Queue<Pair> q=new LinkedList<>();
q.add(new Pair(root,0));
while(!q.isEmpty()){
Pair curr=q.poll();
Node node=curr.node;
int hd=curr.hd;
mp.put(hd,node.data);
if(node.left!=null){
q.add(new Pair(node.left,hd-1));
}
if(node.right!=null){
q.add(new Pair(node.right,hd+1));
}
}
for (int data : mp.values()) {
System.out.print(data+" ");
}
}
public static void verticalOrderView(Node root){
if (root == null) return ;
class Pair {
Node node;
int hd;
Pair(Node node, int hd) {
this.node = node;
this.hd = hd;
}
}
Map<Integer,List<Integer>> mp = new TreeMap<>();
Queue<Pair> q=new LinkedList<>();
q.add(new Pair(root,0));
while(!q.isEmpty()){
Pair curr=q.poll();
Node node=curr.node;
int hd=curr.hd;
if (!mp.containsKey(hd)) {
mp.put(hd, new ArrayList<>());
}
mp.get(hd).add(node.data);
if(node.left!=null){
q.add(new Pair(node.left,hd-1));
}
if(node.right!=null){
q.add(new Pair(node.right,hd+1));
}
}
for (List<Integer> data : mp.values()) {
System.out.print(data+" ");
}
}
public static void printLeftBoundary(Node root, List<Integer> result){
if(root==null || (root.left==null && root.right==null))
return;
result.add(root.data);
if (root.left != null)
printLeftBoundary(root.left, result);
else
printLeftBoundary(root.right, result);
}
public static void printLeaves(Node root, List<Integer> result){
if(root==null)
return;
printLeaves(root.left, result);
if (root.left == null && root.right == null)
result.add(root.data);
printLeaves(root.right, result);
}
public static void printRightBoundary(Node root, List<Integer> result){
if(root==null || (root.left==null && root.right==null))
return;
if (root.right!= null)
printRightBoundary(root.right, result);
else
printRightBoundary(root.left, result);
result.add(root.data);
}
public static void boundaryOrder(Node root){
if(root==null) return;
List<Integer> result=new ArrayList<>();
result.add(root.data);
printLeftBoundary(root.left, result);
printLeaves(root, result);
printRightBoundary(root.right, result);
for(int i:result)
System.out.print(i+" ");
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
Node root=createBinaryTree(arr);
leftView(root);
System.out.println();
rightView(root);
System.out.println();
topView(root);
System.out.println();
bottomView(root);
System.out.println();
verticalOrderView(root);
System.out.println();
boundaryOrder(root);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static class Graph{
int V;
LinkedList<Integer> adj[];
Graph(int v){
V=v;
adj=new LinkedList[v];
for(int i=0;i<V;i++){
adj[i]=new LinkedList();
}
}
void addEdge(int v,int w){
adj[v].add(w);
}
void bfs(int s){
boolean visited[] = new boolean[V];
Queue<Integer> q = new LinkedList<>();
visited[s]=true;
q.add(s);
while(q.size()!=0){
s=q.poll();
System.out.println(s+" ");
Iterator<Integer> i = adj[s].listIterator();
while(i.hasNext()){
int n=i.next();
if(!visited[n]){
visited[n]=true;
q.add(n);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int v=sc.nextInt();
Graph g=new Graph(v);
int n=sc.nextInt();
for(int i=0;i<n;i++){
int a=sc.nextInt();
int b=sc.nextInt();
g.addEdge(a,b);
}
g.bfs(2);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static class Graph{
int V;
LinkedList<Integer> adj[];
Graph(int v){
V=v;
adj=new LinkedList[v];
for(int i=0;i<V;i++){
adj[i]=new LinkedList();
}
}
void addEdge(int v,int w){
adj[v].add(w);
}
void bfs(int s){
boolean visited[] = new boolean[V];
Stack<Integer> st = new Stack<>();
visited[s]=true;
st.push(s);
while(st.size()!=0){
s=st.peek();
st.pop();
System.out.println(s+" ");
Iterator<Integer> i = adj[s].listIterator();
while(i.hasNext()){
int n=i.next();
if(!visited[n]){
visited[n]=true;
st.push(n);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int v=sc.nextInt();
Graph g=new Graph(v);
int n=sc.nextInt();
for(int i=0;i<n;i++){
int a=sc.nextInt();
int b=sc.nextInt();
g.addEdge(a,b);
}
g.bfs(2);
}
}
import java.util.*;
class Graph {
private int V;
private List<List<Node>> adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v, int weight) {
adj.get(u).add(new Node(v, weight));
adj.get(v).add(new Node(u, weight)); // Uncomment for undirected graph
}
public void dijkstra(int source) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;
for (Node neighbor : adj.get(u)) {
int v = neighbor.vertex;
int weight = neighbor.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new Node(v, dist[v]));
}
}
}
// Print the shortest distances
System.out.println("Shortest distances from source vertex " + source + ":");
for (int i = 0; i < V; i++) {
System.out.println("Vertex " + i + ": " + dist[i]);
}
}
static class Node {
int vertex;
int weight;
public Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
}
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int V = scanner.nextInt();
Graph graph = new Graph(V);
int E = scanner.nextInt();
for (int i = 0; i < E; i++) {
int src = scanner.nextInt();
int dest = scanner.nextInt();
int weight = scanner.nextInt();
graph.addEdge(src, dest, weight);
}
int source = scanner.nextInt();
graph.dijkstra(source);
scanner.close();
}
}
import java.util.*;
// Class to represent a weighted directed graph
class Graph {
private int V; // Number of vertices
private List<Edge> adj; // List of adj
// Constructor
public Graph(int V) {
this.V = V;
adj = new ArrayList<>();
}
// Class to represent an edge
class Edge {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
// Add an edge to the graph
public void addEdge(int src, int dest, int weight) {
adj.add(new Edge(src, dest, weight));
}
// Bellman-Ford algorithm to find shortest paths from source vertex
public void bellmanFord(int source) {
// Initialize distances from source to all vertices as INFINITY
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// Relax all adj V-1 times
for (int i = 0; i < V - 1; i++) {
for (Edge edge : adj) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// Check for negative weight cycles
for (Edge edge : adj) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
System.out.println("-1");
return;
}
}
// Print shortest distances
System.out.println("Shortest distances from source vertex " + source + ":");
for(int i = 0; i < V; ++i)
if(dist[i]!=Integer.MAX_VALUE)
System.out.print(dist[i]+" ");
else
System.out.print(-1+" ");
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int V = scanner.nextInt();
Graph graph = new Graph(V);
int E = scanner.nextInt();
for (int i = 0; i < E; i++) {
int src = scanner.nextInt();
int dest = scanner.nextInt();
int weight = scanner.nextInt();
graph.addEdge(src, dest, weight);
}
int source = scanner.nextInt();
graph.bellmanFord(source);
scanner.close();
}
}
import java.util.*;
class BinomialHeapNode {
int key, degree;
BinomialHeapNode parent;
BinomialHeapNode sibling;
BinomialHeapNode child;
public BinomialHeapNode(int k) {
key = k;
degree = 0;
parent = null;
sibling = null;
child = null;
}
public BinomialHeapNode reverse(BinomialHeapNode sibl) {
BinomialHeapNode ret;
if (sibling != null)
ret = sibling.reverse(this);
else
ret = this;
sibling = sibl;
return ret;
}
public BinomialHeapNode findMinNode() {
BinomialHeapNode x = this, y = this;
int min = x.key;
while (x != null) {
if (x.key < min) {
y = x;
min = x.key;
}
x = x.sibling;
}
return y;
}
public BinomialHeapNode findANodeWithKey(int value) {
BinomialHeapNode temp = this, node = null;
while (temp != null) {
if (temp.key == value) {
node = temp;
break;
}
if (temp.child == null)
temp = temp.sibling;
else {
node = temp.child.findANodeWithKey(value);
if (node == null)
temp = temp.sibling;
else
break;
}
}
return node;
}
public int getSize() {
return (1 + ((child == null) ? 0 : child.getSize()) + ((sibling == null) ? 0 : sibling.getSize()));
}
}
class BinomialHeap {
private BinomialHeapNode Nodes;
private int size;
public BinomialHeap() {
Nodes = null;
size = 0;
}
public boolean isEmpty() {
return Nodes == null;
}
public int getSize() {
return size;
}
public void makeEmpty() {
Nodes = null;
size = 0;
}
public void insert(int value) {
if (value > 0) {
BinomialHeapNode temp = new BinomialHeapNode(value);
if (Nodes == null) {
Nodes = temp;
size = 1;
} else {
unionNodes(temp);
size++;
}
}
}
private void merge(BinomialHeapNode binHeap) {
BinomialHeapNode temp1 = Nodes, temp2 = binHeap;
while ((temp1 != null) && (temp2 != null)) {
if (temp1.degree == temp2.degree) {
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
temp1 = tmp.sibling;
} else {
if (temp1.degree < temp2.degree) {
if ((temp1.sibling == null) || (temp1.sibling.degree > temp2.degree)) {
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
temp1 = tmp.sibling;
} else
temp1 = temp1.sibling;
} else {
BinomialHeapNode tmp = temp1;
temp1 = temp2;
temp2 = temp2.sibling;
temp1.sibling = tmp;
if (tmp == Nodes)
Nodes = temp1;
}
}
}
if (temp1 == null) {
temp1 = Nodes;
while (temp1.sibling != null)
temp1 = temp1.sibling;
temp1.sibling = temp2;
}
}
private void unionNodes(BinomialHeapNode binHeap) {
merge(binHeap);
BinomialHeapNode prevTemp = null, temp = Nodes, nextTemp = Nodes.sibling;
while (nextTemp != null) {
if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null) && (nextTemp.sibling.degree == temp.degree))) {
prevTemp = temp;
temp = nextTemp;
} else {
if (temp.key <= nextTemp.key) {
temp.sibling = nextTemp.sibling;
nextTemp.parent = temp;
nextTemp.sibling = temp.child;
temp.child = nextTemp;
temp.degree++;
} else {
if (prevTemp == null)
Nodes = nextTemp;
else
prevTemp.sibling = nextTemp;
temp.parent = nextTemp;
temp.sibling = nextTemp.child;
nextTemp.child = temp;
nextTemp.degree++;
temp = nextTemp;
}
}
nextTemp = temp.sibling;
}
}
public int findMinimum() {
return Nodes.findMinNode().key;
}
public void delete(int value) {
if ((Nodes != null) && (Nodes.findANodeWithKey(value) != null)) {
decreaseKeyValue(value, findMinimum() - 1);
extractMin();
}
}
public void decreaseKeyValue(int old_value, int new_value) {
BinomialHeapNode temp = Nodes.findANodeWithKey(old_value);
if (temp == null)
return;
temp.key = new_value;
BinomialHeapNode tempParent = temp.parent;
while ((tempParent != null) && (temp.key < tempParent.key)) {
int z = temp.key;
temp.key = tempParent.key;
tempParent.key = z;
temp = tempParent;
tempParent = tempParent.parent;
}
}
public int extractMin() {
if (Nodes == null)
return -1;
BinomialHeapNode temp = Nodes, prevTemp = null;
BinomialHeapNode minNode = Nodes.findMinNode();
while (temp.key != minNode.key) {
prevTemp = temp;
temp = temp.sibling;
}
if (prevTemp == null)
Nodes = temp.sibling;
else
prevTemp.sibling = temp.sibling;
temp = temp.child;
BinomialHeapNode fakeNode = temp;
while (temp != null) {
temp.parent = null;
temp = temp.sibling;
}
if ((Nodes == null) && (fakeNode == null))
size = 0;
else {
if ((Nodes == null) && (fakeNode != null)) {
Nodes = fakeNode.reverse(null);
size = Nodes.getSize();
} else {
if ((Nodes != null) && (fakeNode == null))
size = Nodes.getSize();
else {
unionNodes(fakeNode.reverse(null));
size = Nodes.getSize();
}
}
}
return minNode.key;
}
public void displayHeap() {
System.out.print("\nHeap : ");
displayHeap(Nodes);
System.out.println("\n");
}
private void displayHeap(BinomialHeapNode r) {
if (r != null) {
displayHeap(r.child);
System.out.print(r.key + " ");
displayHeap(r.sibling);
}
}
}
public class Main {
public static void main(String[] args) throws Exception{
BinomialHeap binHeap = new BinomialHeap();
Scanner s = new Scanner(System.in);
int n = s.nextInt();
for (int i = 0; i < n; i++)
binHeap.insert(s.nextInt());
System.out.println("Size:" + binHeap.getSize());
binHeap.displayHeap();
binHeap.delete(s.nextInt());
System.out.println("Size:" + binHeap.getSize());
binHeap.displayHeap();
System.out.println(binHeap.isEmpty());
binHeap.makeEmpty();
System.out.println(binHeap.isEmpty());
}
}
public class Main {
public static void main(String[] args) {
final int capacity = 100;
int[] arr = new int[capacity];
arr[0] = 4;
arr[1] = 5;
arr[2] = 6;
arr[3] = 7;
arr[4] = 8;
arr[5] = 9;
arr[6] = 10;
int n = 7;
int k = 3;
buildHeap(arr, n, k);
System.out.println("Built Heap: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
int element = 3;
insert(arr, n, k, element);
n++;
System.out.println("Heap after insertion of " +element + ": ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println("Extracted max is " +extractMax(arr,n,k));
n--;
System.out.println("\n\nHeap after extract max: ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void buildHeap(int[] arr, int n, int k) {
for (int i = (n - 1) / k; i >= 0; i--)
restoreDown(arr, n, i, k);
}
public static void insert(int[] arr, int n, int k, int elem) {
arr[n - 1] = elem;
restoreUp(arr, n - 1, k);
}
public static int extractMax(int[] arr, int n, int k) {
int max = arr[0];arr[0] = arr[n - 1];
restoreDown(arr, n - 1, 0, k);
return max;
}
public static void restoreDown(int[] arr, int len, int index, int k){
int[] child = new int[k + 1];
while (true) {
for (int i = 1; i <= k; i++)
child[i]=(k*index+i) < len ? (k*index+i) : -1;
int maxChild = -1, maxChildIndex = 0;
for (int i = 1; i <= k; i++) {
if (child[i] != -1 && arr[child[i]] > maxChild) {
maxChildIndex = child[i];
maxChild = arr[child[i]];
}
}
if (maxChild == -1)
break;
if (arr[index] < arr[maxChildIndex])
swap(arr, index, maxChildIndex);
index = maxChildIndex;
}
}
public static void restoreUp(int[] arr, int index, int k) {
int parent = (index - 1) / k;
while (parent >= 0) {
if (arr[index] > arr[parent]) {
swap(arr, index, parent);
index = parent;
parent = (index - 1) / k;
} else
break;
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
import java.util.*;
class Node {
int idx;
Node left, right;
}
class Main {
static Node createNode(int idx) {
Node t = new Node();
t.left = t.right = null;
t.idx = idx;
return t;
}
static void traverseHeight(Node root, int[] arr, int[] res) {
if (root == null || (root.left == null && root.right == null))
return;
if (res[0] > arr[root.left.idx] && root.left.idx != root.idx) {
res[0] = arr[root.left.idx];
traverseHeight(root.right, arr, res);
}
else if(res[0]>arr[root.right.idx]&& root.right.idx!=root.idx){
res[0] = arr[root.right.idx];
traverseHeight(root.left, arr, res);
}
}
static void findSecondMin(int[] arr, int n) {
List<Node> li = new LinkedList<>();
Node root = null;
for (int i = 0; i < n; i += 2) {
Node t1 = createNode(i);
Node t2 = null;
if (i + 1 < n) {
t2 = createNode(i + 1);
root = (arr[i] < arr[i + 1]) ? createNode(i) : createNode(i + 1);
root.left = t1;
root.right = t2;
li.add(root);
}
else
li.add(t1);
}
int lsize = li.size();
while (lsize != 1) {
int last = (lsize & 1) == 1 ? lsize - 2 : lsize - 1;
for (int i = 0; i < last; i += 2) {
Node f1 = li.remove(0);
Node f2 = li.remove(0);
root = (arr[f1.idx] < arr[f2.idx]) ? createNode(f1.idx) : createNode(f2.idx);
root.left = f1;
root.right = f2;
li.add(root);
}
if ((lsize & 1) == 1) {
li.add(li.get(0));
li.remove(0);
}
lsize = li.size();
}
int[] res = {Integer.MAX_VALUE};
traverseHeight(root, arr, res);
System.out.println("Minimum: " + arr[root.idx] + ", Second minimum: " + res[0]);
}
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i]=s.nextInt();
findSecondMin(arr, n);
}
}
import java.util.*;
class Main {
private void dfs(List<List<Integer>> adj, int v, boolean[] visited, Stack<Integer> mystack) {
visited[v] = true;
for (int i = 0; i < adj.get(v).size(); ++i)
if (!visited[adj.get(v).get(i)])
dfs(adj, adj.get(v).get(i), visited, mystack);
mystack.push(v);
}
private boolean detectCycle(List<List<Integer>> adj, int numCourses) {
boolean[] visited = new boolean[numCourses];
boolean[] recStack = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (detectCycleUtil(adj, i, visited, recStack))
return true;
}
return false;
}
private boolean detectCycleUtil(List<List<Integer>> adj, int v, boolean[] visited, boolean[] recStack) {
if (!visited[v]) {
visited[v] = true;
recStack[v] = true;
for (int i = 0; i < adj.get(v).size(); i++) {
int adjacent = adj.get(v).get(i);
if (!visited[adjacent] && detectCycleUtil(adj, adjacent, visited, recStack))
return true;
else if (recStack[adjacent])
return true;
}
}
recStack[v] = false; // backtrack
return false;
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++)
adj.add(new ArrayList<>());
for (int i = 0; i < prerequisites.length; ++i)
adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
int[] ans = new int[numCourses];
if (detectCycle(adj, numCourses))
return new int[0];
Stack<Integer> mystack = new Stack<>();
boolean[] visited = new boolean[numCourses];
for (int i = 0; i < numCourses; ++i)
if (!visited[i])
dfs(adj, i, visited, mystack);
int index = 0;
while (!mystack.isEmpty()) {
ans[index++] = mystack.pop();
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int v = sc.nextInt();
int e = sc.nextInt();
int[][] prerequisites = new int[e][2];
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
prerequisites[i][0] = a;
prerequisites[i][1] = b;
}
Main main = new Main();
int[] order = main.findOrder(v, prerequisites);
System.out.println("Topological order:");
for (int course : order) {
System.out.print(course + " ");
}
}
}
import java.util.*;
public class Main {
public void sort(int arr[])
{
int N = arr.length;
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
for (int i = N - 1; i > 0; i--) {
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;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < N && arr[l] > arr[largest])
largest = l;
if (r < N && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, N, largest);
}
}
static void printArray(int arr[])
{
int N = arr.length;
for (int i = 0; i < N; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
Main ob = new Main();
ob.sort(arr);
printArray(arr);
}
}
import java.util.*;
import java.util.stream.*;
class Main {
public static <K, V> Map<K, V> convertToTreeMap(Map<K, V> hashMap)
{
Map<K, V> treeMap = new TreeMap<>();
treeMap.putAll(hashMap);
return treeMap;
}
public static void main(String args[])
{
Map<String, String> hashMap = new HashMap<>();
Scanner s=new Scanner(System.in);
int n=s.nextInt();
for(int i=0; i<n; i++)
hashMap.put(s.next(),s.next());
System.out.println("HashMap: " + hashMap);
Map<String, String> treeMap = convertToTreeMap(hashMap);
System.out.println("TreeMap: " + treeMap);
}
}
import java.util.*;
public class Main {
static boolean checkCount(int []arr, int n, int k){
int count;
for (int i = 0; i < n; i++){
count = 0;
for (int j = 0; j < n; j++){
if (arr[j] == arr[i])count++;
if (count > 2 * k)return false;
}
}return true;
}
static public void main (String[] args){
Scanner s=new Scanner(System.in);
int n=s.nextInt(); int k = s.nextInt();
int []arr =new int[n];
for(int i=0; i<n; i++)
arr[i]=s.nextInt();
if(checkCount(arr, n, k)) System.out.println("Yes");
else System.out.println("No");
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int lcs(String s, String t, int i, int j){
if(i==s.length() || j==t.length())
return 0;
if(s.charAt(i)==t.charAt(j))
return 1+lcs(s,t,i+1,j+1);
else
return Math.max(lcs(s,t,i+1,j),lcs(s,t,i,j+1));
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
String t=sc.nextLine();
System.out.println(lcs(s,t,0,0));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int lcs(String s, String t, int i, int j){
if(i==s.length() || j==t.length())
return 0;
if(s.charAt(i)==t.charAt(j))
return 1+lcs(s,t,i+1,j+1);
else
return Math.max(lcs(s,t,i+1,j),lcs(s,t,i,j+1));
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
String t=new StringBuilder(s).reverse().toString();
System.out.println(lcs(s,t,0,0));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int lis(int []arr){
int n=arr.length;
int dp[]=new int[n];
Arrays.fill(dp,1);
for (int i=1;i<n;i++)
for (int j=0;j<i;j++)
if(arr[i]>arr[j])
dp[i]=Math.max(dp[i],dp[j]+1);
return Arrays.stream(dp).max().orElse(0);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str[]=sc.nextLine().split(",");
int[] arr = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
System.out.println(lis(arr));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static int lbs(int []arr){
int n=arr.length;
int dp1[]=new int[n];
Arrays.fill(dp1,1);
for (int i=1;i<n;i++)
for (int j=0;j<i;j++)
if(arr[i]>arr[j])
dp1[i]=Math.max(dp1[i],dp1[j]+1);
int dp2[]=new int[n];
Arrays.fill(dp2,1);
for (int i=n-2;i>=0;i--)
for (int j=n-1;j>i;j--)
if(arr[i]>arr[j])
dp2[i]=Math.max(dp2[i],dp2[j]+1);
int maxi=dp1[0]+dp2[0]-1;
for(int i=1;i<n;i++)
maxi=Math.max(maxi,dp1[i]+dp2[i]-1);
return maxi;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str[]=sc.nextLine().split(",");
int[] arr = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
System.out.println(lbs(arr));
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static boolean subsetSum(int []arr, int ind, int target){
if(target==0)
return true;
if(ind==0)
return arr[0]==target;
boolean notTake=subsetSum(arr,ind-1,target);
boolean take=false;
if(arr[ind]<=target)
take=subsetSum(arr,ind-1,target-arr[ind]);
return take || notTake;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str[]=sc.nextLine().split(" ");
int[] arr = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
int target=sc.nextInt();
System.out.println(subsetSum(arr, arr.length-1, target));
}
}
class Main {
public static int cutRod(int[] price, int n) {
int[] val = new int[n + 1];
val[0] = 0;
for (int i = 1; i <= n; i++) {
int maxVal = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) {
maxVal = Math.max(maxVal, price[j] + val[i - j - 1]);
}
val[i] = maxVal;
}
return val[n];
}
public static void main(String[] args) {
int[] price = {1, 5, 8, 9, 10, 17, 17, 20};
int n = price.length;
int maxVal = cutRod(price, n);
System.out.println("Maximum obtainable value is" + maxVal);
}
}
public class Main {
public static boolean isMatch(String word, String pattern) {
int n = word.length();
int m = pattern.length();
boolean[][] T = new boolean[n + 1][m + 1];
T[0][0] = true;
for (int j = 1; j <= m; j++) {
if (pattern.charAt(j - 1) == '*') {
T[0][j] = T[0][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (pattern.charAt(j - 1) == '*') {
T[i][j] = T[i - 1][j] || T[i][j - 1];
} else if (pattern.charAt(j - 1) == '?' ||
word.charAt(i - 1) == pattern.charAt(j - 1)) { T[i][j] = T[i - 1][j - 1];
}
}
}
return T[n][m];
}public static void main(String[] args) {
String word = "xyxzzxy";
String pattern = "x***x?";
if (isMatch(word, pattern)) {
System.out.print("Match");
} else {
System.out.print("No Match");
}
}
}
public class Main {
private static int editDistanceHelper(int i, int j, String str1, String str2) {
if (i == 0) {
return j;
}
if (j == 0) {
return i;
}
int ans = 1 + Math.min(Math.min(
editDistanceHelper(i, j - 1, str1, str2), // Insert
editDistanceHelper(i - 1, j, str1, str2)), // Remove
editDistanceHelper(i - 1, j - 1, str1, str2) // Replace
);
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
ans = Math.min(ans, editDistanceHelper(i - 1, j - 1, str1, str2));
}
return ans;
} public static int editDistance(String str1, String str2) {
int n = str1.length(), m = str2.length();
int ans = editDistanceHelper(n, m, str1, str2);
return ans;
}
public static void main(String[] args) {
String str1 = "abade";
String str2 = "abacf";
System.out.println(editDistance(str1,str2));
}
}
public class Main {
public static int findMaxCoins(int[] coin, int i, int j, int[][] lookup) {
if (i == j) return coin[i];
if (i + 1 == j) return Math.max(coin[i], coin[j]);
if (lookup[i][j] == 0) {
int start = coin[i] + Math.min(findMaxCoins(coin, i + 2, j, lookup), findMaxCoins(coin, i + 1, j - 1, lookup));
int end = coin[j] + Math.min(findMaxCoins(coin, i + 1, j - 1, lookup), findMaxCoins(coin, i, j - 2, lookup));
lookup[i][j] = Math.max(start, end);
}
return lookup[i][j];
}
public static void main(String[] args) {
int[] coin = {4, 6, 2, 3};
int[][] lookup = new int[coin.length][coin.length];
System.out.println("Maximum coins collected by player: " + findMaxCoins(coin, 0, coin.length - 1, lookup));
}
}
To embed this program on your website, copy the following code and paste it into your website's HTML: