Quick Sort

import [Link].*;

public class Main {

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

if (low < high) {

int p = partition(arr, low, high);

quickSort(arr, low, p - 1);

quickSort(arr, p + 1, high);

static int partition(int[] arr, int low, int high) {

int pivot = arr[high];

int i = low;

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {

int t = arr[i]; arr[i] = arr[j]; arr[j] = t;

i++;

int t = arr[i]; arr[i] = arr[high]; arr[high] = t;

return i;

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int[] arr = new int[n];

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

quickSort(arr, 0, n - 1);

for (int x : arr) [Link](x + " ");

Merge Sort

import [Link].*;

public class Main {

static void mergeSort(int[] arr, int l, int r) {

if (l < r) {

int m = (l + r) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

static void merge(int[] arr, int l, int m, int r) {

int n1 = m - l + 1, n2 = r - m;

int[] L = new int[n1];

int[] R = new int[n2];

L[i] = arr[l + i];

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

R[i] = arr[m + 1 + i];

int i = 0, j = 0, k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k++] = L[i++];

} else {

arr[k++] = R[j++];

while (i < n1) arr[k++] = L[i++];

while (j < n2) arr[k++] = R[j++];

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link]();

int[] arr = new int[n];

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

mergeSort(arr, 0, n - 1);

for (int x : arr)

[Link](x + " ");

Binary Search Tree

import [Link].*;

public class Main {

static int binarySearch(int[] arr, int key) {

int l = 0, r = [Link] - 1;

while (l <= r) {

int mid = (l + r) / 2;

if (arr[mid] == key)

return mid;

if (arr[mid] < key)

l = mid + 1;

else

r = mid - 1;

return -1;
 }

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link]();

int[] arr = new int[n];

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

arr[i] = [Link]();

int key = [Link]();

int res = binarySearch(arr, key);

[Link](res);

Prim’s

import [Link].*;

public class Main {

static int minKey(int[] key, boolean[] mstSet, int n) {

int min = Integer.MAX_VALUE, idx = -1;

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

if (!mstSet[i] && key[i] < min) {

min = key[i];

idx = i;
 }

return idx;

public static void prim(int[][] graph, int n) {

int[] parent = new int[n];

int[] key = new int[n];

boolean[] mstSet = new boolean[n];

[Link](key, Integer.MAX_VALUE);

key[0] = 0;

parent[0] = -1;

for (int c = 0; c < n - 1; c++) {

int u = minKey(key, mstSet, n);

mstSet[u] = true;

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

if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {

parent[v] = u;

key[v] = graph[u][v];

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

[Link](parent[i] + " - " + i + " : " + graph[i][parent[i]]);

}
 public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link]();

int[][] graph = new int[n][n];

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

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

graph[i][j] = [Link]();

prim(graph, n);

Kruskal’s

import [Link].*;

public class Main {

static class Edge {

int u, v, w;

Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }

static int find(int[] parent, int x) {

if (parent[x] == x) return x;

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

static void union(int[] parent, int[] rank, int a, int b) {

int pa = find(parent, a), pb = find(parent, b);

if (rank[pa] < rank[pb]) parent[pa] = pb;

else if (rank[pb] < rank[pa]) parent[pb] = pa;

else { parent[pb] = pa; rank[pa]++; }

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link](), e = [Link]();

List<Edge> edges = new ArrayList<>();

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

[Link](new Edge([Link](), [Link](), [Link]()));

[Link]([Link](x -> x.w));

int[] parent = new int[n], rank = new int[n];

for (int i = 0; i < n; i++) parent[i] = i;

for (Edge ed : edges) {

if (find(parent, ed.u) != find(parent, ed.v)) {

[Link](ed.u + " - " + ed.v + " : " + ed.w);

union(parent, rank, ed.u, ed.v);

}
Dijkstra

import [Link].*;

public class Main {

static int minDist(int[] dist, boolean[] vis, int n) {

int min = Integer.MAX_VALUE, idx = -1;

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

if (!vis[i] && dist[i] < min) { min = dist[i]; idx = i; }

return idx;

static void dijkstra(int[][] graph, int src, int n) {

int[] dist = new int[n];

boolean[] vis = new boolean[n];

[Link](dist, Integer.MAX_VALUE);

dist[src] = 0;

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

int u = minDist(dist, vis, n);

vis[u] = true;

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

if (graph[u][v] != 0 && !vis[v] &&

dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

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

[Link](src + " -> " + i + " = " + dist[i]);

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link]();

int[][] graph = new int[n][n];

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

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

graph[i][j] = [Link]();

int src = [Link]();

dijkstra(graph, src, n);

Matrix Multiplication

import [Link].*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int r1 = [Link](), c1 = [Link]();

int[][] A = new int[r1][c1];

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

for (int j = 0; j < c1; j++)

A[i][j] = [Link]();
 int r2 = [Link](), c2 = [Link]();

int[][] B = new int[r2][c2];

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

for (int j = 0; j < c2; j++)

B[i][j] = [Link]();

if (c1 != r2) {

[Link]("Multiplication not possible");

return;

int[][] C = new int[r1][c2];

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

for (int j = 0; j < c2; j++)

for (int k = 0; k < c1; k++)

C[i][j] += A[i][k] * B[k][j];

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

for (int j = 0; j < c2; j++)

[Link](C[i][j] + " ");

[Link]();

OBST

import [Link].*;
public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link]();

int[] keys = new int[n];

int[] freq = new int[n];

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

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

int[][] dp = new int[n][n];

int[] prefix = new int[n + 1];

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

prefix[i + 1] = prefix[i] + freq[i];

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

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

if (gap == 0) dp[i][j] = freq[i];

else {

dp[i][j] = Integer.MAX_VALUE;

int sum = prefix[j + 1] - prefix[i];

for (int r = i; r <= j; r++) {

int cost = (r > i ? dp[i][r - 1] : 0)

+ (r < j ? dp[r + 1][j] : 0)

+ sum;

dp[i][j] = [Link](dp[i][j], cost);

[Link](dp[0][n - 1]);

LCS

import [Link].*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

String a = [Link]();

String b = [Link]();

int n = [Link](), m = [Link]();

int[][] dp = new int[n + 1][m + 1];

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

for (int j = 1; j <= m; j++)

if ([Link](i - 1) == [Link](j - 1))

dp[i][j] = dp[i - 1][j - 1] + 1;

else

dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);

Digraph

import [Link].*;

public class Main {

static void bfs(List<List<Integer>> g, int s) {

boolean[] vis = new boolean[[Link]()];

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

[Link](s); vis[s] = true;

while (![Link]()) {

int u = [Link]();

[Link](u + " ");

for (int v : [Link](u))

if (!vis[v]) {

vis[v] = true;

[Link](v);

static void dfs(List<List<Integer>> g, int u, boolean[] vis) {

vis[u] = true;

[Link](u + " ");

for (int v : [Link](u))

dfs(g, v, vis);

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int n = [Link](), e = [Link]();

List<List<Integer>> g = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

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

[Link]([Link]()).add([Link]());

int start = [Link]();

bfs(g, start);

[Link]();

dfs(g, start, new boolean[n]);

APSP

import [Link].*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int[][] dist = new int[n][n];

final int INF = 1000000000;

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

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

dist[i][j] = [Link]();

if (dist[i][j] == -1) dist[i][j] = INF;

if (i == j) dist[i][j] = 0;

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

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

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

if (dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];

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

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

[Link]((dist[i][j] >= INF ? -1 : dist[i][j]) + " ");

[Link]();