25 Essential Algorithms Every Programmer Should

Know
Curated with by: coding_erorr1

1. Binary Search

2. Bubble Sort

3. Selection Sort

4. Insertion Sort

5. Merge Sort

6. Quick Sort

7. Kadane's Algorithm (Maximum Subarray Sum)

8. Floyd-Warshall Algorithm (All-Pairs Shortest Path)

9. Bellman-Ford Algorithm (Single Source Shortest Path with Negatives)

10. 0/1 Knapsack Problem (Dynamic Programming)

11. Longest Common Subsequence (LCS)

12. Sieve of Eratosthenes (Prime Numbers Generator)

13. Depth-First Search (DFS)

14. Breadth-First Search (BFS)

15. Dijkstra's Algorithm (Shortest Path - Greedy)

16. Prim’s Algorithm (Minimum Spanning Tree - MST)

17. Kruskal’s Algorithm (MST Using Disjoint Set)

18. Topological Sort (Using DFS - DAG)

 19. Cycle Detection in Directed Graph (DFS + Recursion Stack)

20. Union-Find / Disjoint Set (Path Compression + Union by Rank)

21. Matrix Chain Multiplication (MCM - DP)

22. Longest Increasing Subsequence (LIS)

23. Edit Distance (Minimum Operations to Convert Strings)

24. Trie – Insert and Search

25. Sliding Window Maximum (Deque Approach)

1. Binary Search
Description:
Binary Search is an efficient algorithm to find the position of a target element in a sorted
array. It works by repeatedly dividing the search interval in half.

Time Complexity:

• Best: O(1)
• Average & Worst: O(log n)

Java Code:

java
CopyEdit
int binarySearch(int[] arr, int target) {
int left = 0, right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
 2. Bubble Sort
Description:
Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are
in the wrong order.

Time Complexity:

• Best: O(n)
• Average & Worst: O(n²)

Java Code:

java
CopyEdit
void bubbleSort(int[] arr) {
for (int i = 0; i < [Link] - 1; i++) {
for (int j = 0; j < [Link] - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

3. Selection Sort
Description:
Selection Sort divides the array into a sorted and an unsorted part, and repeatedly selects the
smallest element from the unsorted part.

Time Complexity:

• Best, Average & Worst: O(n²)

Java Code:

java
CopyEdit
void selectionSort(int[] arr) {
for (int i = 0; i < [Link] - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < [Link]; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

4. Insertion Sort
Description:
Insertion Sort builds the final sorted array one item at a time by inserting elements into their
correct position.

Time Complexity:

• Best: O(n)
• Average & Worst: O(n²)

Java Code:

java
CopyEdit
void insertionSort(int[] arr) {
for (int i = 1; i < [Link]; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

5. Merge Sort
Description:
Merge Sort is a divide-and-conquer algorithm that splits the array in half, recursively sorts
them, and then merges the sorted halves.

Time Complexity:

• Best, Average & Worst: O(n log n)

Java Code:

java
CopyEdit
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

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

int[] left = [Link](arr, l, m + 1);
int[] right = [Link](arr, m + 1, r + 1);
int i = 0, j = 0, k = l;
while (i < [Link] && j < [Link])
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < [Link]) arr[k++] = left[i++];
while (j < [Link]) arr[k++] = right[j++];
}

6. Quick Sort
Description:
Quick Sort is another divide-and-conquer algorithm that picks a pivot and partitions the array
around the pivot.

Time Complexity:

• Best & Average: O(n log n)

• Worst: O(n²) (when pivot is poorly chosen)

Java Code:

java
CopyEdit
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);
}
}

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

int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1;
}

7. Kadane’s Algorithm
Description:
Kadane’s Algorithm finds the contiguous subarray with the maximum sum in linear time.
 Time Complexity:

• Best, Average, Worst: O(n)

Java Code:

java
CopyEdit
int maxSubArraySum(int[] arr) {
int maxSoFar = arr[0], currMax = arr[0];
for (int i = 1; i < [Link]; i++) {
currMax = [Link](arr[i], currMax + arr[i]);
maxSoFar = [Link](maxSoFar, currMax);
}
return maxSoFar;
}

8. Floyd-Warshall Algorithm
Description:
An all-pairs shortest path algorithm using dynamic programming.

Time Complexity:

• O(n³)

Java Code:

java
CopyEdit
void floydWarshall(int[][] dist, int V) {
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}

9. Bellman-Ford Algorithm
Description:
Finds shortest paths from a single source to all vertices, handles negative weights.

Time Complexity:

• O(VE)

Java Code:
java
CopyEdit
void bellmanFord(int[][] edges, int V, int src) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;

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

for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
}

10. 0/1 Knapsack Problem

Description:
A classic dynamic programming problem where we maximize the value in a knapsack
without exceeding the weight limit.

Time Complexity:

• O(n * W), where W = max capacity

Java Code:

java
CopyEdit
int knapsack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = [Link](val[i - 1] + dp[i - 1][w - wt[i - 1]],
dp[i - 1][w]);
else dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}

11. Longest Common Subsequence (LCS)

Description:
Finds the longest subsequence common to two sequences (not necessarily contiguous).

Time Complexity:

• O(m × n)
 Java Code:

java
CopyEdit
int lcs(String X, String Y) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ([Link](i - 1) == [Link](j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}

12. Sieve of Eratosthenes

Description:
Efficient algorithm to generate all prime numbers up to n.

Time Complexity:

• O(n log log n)

Java Code:

java
CopyEdit
void sieveOfEratosthenes(int n) {
boolean[] prime = new boolean[n + 1];
[Link](prime, true);
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for (int i = 2; i <= n; i++) {
if (prime[i]) [Link](i + " ");
}
}

13. Depth-First Search (DFS)

Description:
Graph traversal method that explores as far as possible before backtracking.

Time Complexity:
 • O(V + E)

Java Code:

java
CopyEdit
void dfs(int v, boolean[] visited, List<List<Integer>> adj) {
visited[v] = true;
[Link](v + " ");
for (int u : [Link](v)) {
if (!visited[u]) dfs(u, visited, adj);
}
}

14. Breadth-First Search (BFS)

Description:
Graph traversal technique that explores all neighbors at the current depth before going
deeper.

Time Complexity:

• O(V + E)

Java Code:

java
CopyEdit
void bfs(int start, List<List<Integer>> adj) {
boolean[] visited = new boolean[[Link]()];
Queue<Integer> queue = new LinkedList<>();
[Link](start);
visited[start] = true;
while (![Link]()) {
int v = [Link]();
[Link](v + " ");
for (int u : [Link](v)) {
if (!visited[u]) {
visited[u] = true;
[Link](u);
}
}
}
}

15. Dijkstra’s Algorithm

Description:
Finds the shortest path from a source to all vertices using a priority queue.
 Time Complexity:

• O((V + E) log V) with min-heap

Java Code:

java
CopyEdit
void dijkstra(int V, List<List<int[]>> adj, int src) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>([Link](a
-> a[1]));
[Link](new int[]{src, 0});

while (![Link]()) {
int[] curr = [Link]();
int u = curr[0], d = curr[1];
if (d > dist[u]) continue;
for (int[] neighbor : [Link](u)) {
int v = neighbor[0], weight = neighbor[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
[Link](new int[]{v, dist[v]});
}
}
}
}

16. Prim’s Algorithm

Description:
Constructs a Minimum Spanning Tree using a greedy approach.

Time Complexity:

• O((V + E) log V)

Java Code:

java
CopyEdit
void primMST(int V, List<List<int[]>> adj) {
boolean[] visited = new boolean[V];
PriorityQueue<int[]> pq = new PriorityQueue<>([Link](a
-> a[1]));
[Link](new int[]{0, 0}); // {node, weight}
int mstWeight = 0;

while (![Link]()) {
int[] curr = [Link]();
int u = curr[0], wt = curr[1];
if (visited[u]) continue;
 visited[u] = true;
mstWeight += wt;

for (int[] edge : [Link](u)) {

int v = edge[0], w = edge[1];
if (!visited[v]) [Link](new int[]{v, w});
}
}
[Link]("MST weight: " + mstWeight);
}

17. Kruskal’s Algorithm

Description:
Builds MST using union-find for edge selection based on weight.

Time Complexity:

• O(E log E)

Java Code:

java
CopyEdit
int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}

void union(int[] parent, int[] rank, int x, int y) {

int px = find(parent, x), py = find(parent, y);
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else {
parent[py] = px;
rank[px]++;
}
}

void kruskalMST(int[][] edges, int V) {

[Link](edges, [Link](e -> e[2]));
int[] parent = new int[V], rank = new int[V];
for (int i = 0; i < V; i++) parent[i] = i;

int mstWeight = 0;
for (int[] edge : edges) {
int u = edge[0], v = edge[1], wt = edge[2];
if (find(parent, u) != find(parent, v)) {
union(parent, rank, u, v);
mstWeight += wt;
}
}
[Link]("MST weight: " + mstWeight);
}
 18. Topological Sort (DFS-based)
Description:
Sorts a Directed Acyclic Graph (DAG) in linear order respecting dependencies.

Time Complexity:

• O(V + E)

Java Code:

java
CopyEdit
void topologicalSort(int V, List<List<Integer>> adj) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();

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

if (!visited[i]) dfsTopo(i, visited, stack, adj);
}

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

}

void dfsTopo(int v, boolean[] visited, Stack<Integer> stack,

List<List<Integer>> adj) {
visited[v] = true;
for (int u : [Link](v)) {
if (!visited[u]) dfsTopo(u, visited, stack, adj);
}
[Link](v);
}

19. Cycle Detection in Directed Graph

Description:
Detects cycles using DFS and recursion stack in directed graphs.

Time Complexity:

• O(V + E)

Java Code:

java
CopyEdit
boolean hasCycle(int V, List<List<Integer>> adj) {
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];

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

if (!visited[i] && dfsCycle(i, visited, recStack, adj))
 return true;
}
return false;
}

boolean dfsCycle(int v, boolean[] visited, boolean[] recStack,

List<List<Integer>> adj) {
visited[v] = true;
recStack[v] = true;

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

if (!visited[u] && dfsCycle(u, visited, recStack, adj)) return
true;
else if (recStack[u]) return true;
}

recStack[v] = false;
return false;
}

20. Union-Find (Disjoint Set)

Description:
Maintains partitioned sets with fast union and find operations.

Time Complexity:

• Nearly O(1) (with path compression & union by rank)

Java Code:

java
CopyEdit
int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}

void union(int[] parent, int[] rank, int x, int y) {

int px = find(parent, x), py = find(parent, y);
if (px == py) return;
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else {
parent[py] = px;
rank[px]++;
}
}

21. Floyd-Warshall Algorithm

Description:
Dynamic programming algorithm to find all pairs shortest paths in a weighted graph.
 Time Complexity:

• O(V³)

Java Code:

java
CopyEdit
void floydWarshall(int[][] dist, int V) {
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

22. Rabin-Karp Algorithm (Pattern Matching)

Description:
Efficient string matching using hashing to find any one of a set of pattern strings in a text.

Time Complexity:

• Average: O(n + m), Worst: O(nm)

Java Code:

java
CopyEdit
void rabinKarp(String text, String pattern, int q) {
int d = 256, m = [Link](), n = [Link]();
int p = 0, t = 0, h = 1;

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

h = (h * d) % q;

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

p = (d * p + [Link](i)) % q;
t = (d * t + [Link](i)) % q;
}

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

if (p == t) {
boolean match = true;
for (int j = 0; j < m; j++) {
if ([Link](i + j) != [Link](j)) {
match = false;
break;
}
}
if (match) [Link]("Pattern found at index " + i);
 }
if (i < n - m) {
t = (d * (t - [Link](i) * h) + [Link](i + m)) % q;
if (t < 0) t = (t + q);
}
}
}

23. KMP Algorithm (Knuth-Morris-Pratt)

Description:
Pattern matching algorithm that avoids redundant comparisons.

Time Complexity:

• O(n + m)

Java Code:

java
CopyEdit
void KMP(String text, String pattern) {
int[] lps = computeLPSArray(pattern);
int i = 0, j = 0;

while (i < [Link]()) {

if ([Link](j) == [Link](i)) {
i++; j++;
}
if (j == [Link]()) {
[Link]("Pattern found at index " + (i - j));
j = lps[j - 1];
} else if (i < [Link]() && [Link](j) !=
[Link](i)) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}

int[] computeLPSArray(String pat) {

int[] lps = new int[[Link]()];
int len = 0, i = 1;
while (i < [Link]()) {
if ([Link](i) == [Link](len)) {
lps[i++] = ++len;
} else {
if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
}
return lps;
}
 24. Bellman-Ford Algorithm
Description:
Computes shortest paths from a single source in a weighted graph, handling negative weights.

Time Complexity:

• O(V × E)

Java Code:

java
CopyEdit
void bellmanFord(int V, int[][] edges, int src) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;

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

for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}

for (int[] edge : edges) {

int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
[Link]("Graph contains negative weight cycle");
}

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

[Link]("Distance from " + src + " to " + i + " is " +
dist[i]);
}

25. Boyer-Moore Algorithm

Description:
A highly efficient string searching algorithm using bad character and good suffix heuristics.

Time Complexity:

• Best case: O(n/m), Worst case: O(n × m)

Java Code (Bad Character Heuristic Only):

java
CopyEdit
void badCharHeuristic(char[] str, int size, int[] badchar) {
[Link](badchar, -1);
 for (int i = 0; i < size; i++)
badchar[str[i]] = i;
}

void boyerMoore(String txt, String pat) {

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

int[] badchar = new int[256];

badCharHeuristic([Link](), m, badchar);

int s = 0;
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && [Link](j) == [Link](s + j))
j--;
if (j < 0) {
[Link]("Pattern occurs at index " + s);
s += (s + m < n) ? m - badchar[[Link](s + m)] : 1;
} else {
s += [Link](1, j - badchar[[Link](s + j)]);
}
}
}