Arrays are fixed-size, contiguous blocks of memory offering O(1) access by index. In Java, they’re static (int[]), requiring a predefined size, making them ideal for predictable, small datasets like lookup tables or buffers. Their limitation is immutability—resizing requires a new array. Use Arrays utility methods (e.g., sort, binarySearch) for added functionality.

• Use Cases: Storing fixed-size game scores, matrix operations.
• Complexity: Access O(1), Insert/Delete O(n).
• Example: Rotating an array.

public class ArrayRotation {
    public static void rotate(int[] arr, int k) {
        int n = arr.length;
        k = k % n; // Normalize rotation steps
        reverse(arr, 0, n - 1); // Reverse full array
        reverse(arr, 0, k - 1); // Reverse first k elements
        reverse(arr, k, n - 1); // Reverse remaining elements
    }

    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        rotate(arr, 2);
        System.out.println(Arrays.toString(arr)); // [4, 5, 1, 2, 3]
    }
}
                                

ArrayList is a dynamic array that grows automatically (by doubling its capacity) when full, backed by an internal array. It offers O(1) access and amortized O(1) appends but O(n) insertions/deletions due to shifting. Use it for resizable lists where random access dominates over frequent modifications. Thread safety requires Collections.synchronizedList.

• Use Cases: Dynamic task lists, in-memory caches.
• Complexity: Access O(1), Append O(1) amortized, Insert/Delete O(n).
• Example: Filtering even numbers.

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static List<Integer> filterEvens(List<Integer> numbers) {
        List<Integer> evens = new ArrayList<>();
        for (int num : numbers) {
            if (num % 2 == 0) evens.add(num);
        }
        return evens;
    }

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6));
        List<Integer> result = filterEvens(nums);
        System.out.println(result); // [2, 4, 6]
    }
}
                                

LinkedList is a doubly-linked list with nodes containing data and references to next/previous nodes. It excels at O(1) insertions/deletions at known positions (e.g., head, tail) but has O(n) access due to traversal. Use it for frequent additions/removals or as a Deque. Memory overhead is higher than ArrayList due to node pointers.

• Use Cases: Undo stacks, playlist navigation.
• Complexity: Access O(n), Insert/Delete O(1) at known position.
• Example: Custom singly-linked list reversal.

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

public class LinkedListReversal {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode reversed = reverseList(head);
        while (reversed != null) {
            System.out.print(reversed.val + " "); // 3 2 1
            reversed = reversed.next;
        }
    }
}
                                

A Stack follows LIFO (Last In, First Out), supporting O(1) push/pop operations. Java’s legacy Stack class extends Vector, but ArrayDeque is preferred for efficiency (no synchronization overhead). Stacks are critical for recursion, backtracking, or undo mechanisms.

• Use Cases: Browser history, expression evaluation.
• Complexity: Push/Pop O(1), Peek O(1).
• Example: Checking balanced parentheses.

import java.util.ArrayDeque;
import java.util.Deque;

public class StackBalancer {
    public static boolean isBalanced(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : expr.toCharArray()) {
            if (c == '(') stack.push(c);
            else if (c == ')') {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("((()))")); // true
        System.out.println(isBalanced("(()")); // false
    }
}
                                

A Queue follows FIFO (First In, First Out), with O(1) enqueue/dequeue at ends when using ArrayDeque. Java’s LinkedList also implements Queue, but ArrayDeque is faster for non-concurrent use. Queues manage ordered tasks or breadth-first traversals.

• Use Cases: Task scheduling, print queues.
• Complexity: Enqueue/Dequeue O(1).
• Example: Simple queue simulation.

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueSimulator {
    public static void processTasks(Queue<String> tasks) {
        while (!tasks.isEmpty()) {
            System.out.println("Processing: " + tasks.poll());
        }
    }

    public static void main(String[] args) {
        Queue<String> tasks = new ArrayDeque<>();
        tasks.offer("Task 1");
        tasks.offer("Task 2");
        tasks.offer("Task 3");
        processTasks(tasks); // Task 1, Task 2, Task 3
    }
}
                                

A Binary Search Tree is a hierarchical structure where each node has at most two children, with left subtree values less than the node and right subtree values greater. It enables O(log n) search, insert, and delete in balanced cases, though it can degrade to O(n) if unbalanced. Java’s TreeSet uses a red-black tree, but custom BSTs are common in interviews.

• Use Cases: Sorted data storage, autocomplete.
• Complexity: Search/Insert/Delete O(log n) average, O(n) worst.
• Example: BST insertion and search.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class BST {
    private TreeNode root;

    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) node.left = insertRec(node.left, val);
        else node.right = insertRec(node.right, val);
        return node;
    }

    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode node, int val) {
        if (node == null) return false;
        if (node.val == val) return true;
        return val < node.val ? searchRec(node.left, val) : searchRec(node.right, val);
    }

    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        System.out.println(bst.search(3)); // true
        System.out.println(bst.search(4)); // false
    }
}
                                

A Heap is a complete binary tree where each node satisfies the heap property (min-heap: parent ≤ children; max-heap: parent ≥ children). Java’s PriorityQueue implements a min-heap with O(log n) insert/remove and O(1) peek. Heaps are essential for priority scheduling or graph algorithms like Dijkstra’s.

• Use Cases: Job scheduling, top-K problems.
• Complexity: Insert/Remove O(log n), Peek O(1).
• Example: Finding K largest elements.

import java.util.PriorityQueue;

public class HeapExample {
    public static int[] findKLargest(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.offer(num);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2};
        int[] result = findKLargest(arr, 3);
        System.out.println(Arrays.toString(result)); // [4, 5, 9]
    }
}
                                

A Hash Table uses a hash function to map keys to indices in an array, offering O(1) average-case access, insert, and delete. Java’s HashMap handles collisions with linked lists (or trees since Java 8 for high collision cases). It’s perfect for lookups but requires a good hash function to minimize collisions.

• Use Cases: Caching, frequency counting.
• Complexity: Access/Insert/Delete O(1) average, O(n) worst.
• Example: Counting character frequencies.

import java.util.HashMap;
import java.util.Map;

public class HashMapCounter {
    public static Map<Character, Integer> countChars(String str) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : str.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        return freq;
    }

    public static void main(String[] args) {
        String str = "hello";
        Map<Character, Integer> result = countChars(str);
        System.out.println(result); // {h=1, e=1, l=2, o=1}
    }
}
                                

A Graph consists of vertices (nodes) and edges (connections), represented as an adjacency list (Map) or matrix. It models relationships—directed or undirected, weighted or unweighted. Java lacks a built-in graph class, so custom implementations are common for traversals (DFS, BFS) or pathfinding.

• Use Cases: Social networks, shortest paths.
• Complexity: DFS/BFS O(V + E), Space O(V).
• Example: BFS traversal.

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() { adjList = new HashMap<>(); }

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()); // For undirected
    }

    public List<Integer> bfs(int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            result.add(vertex);
            for (int neighbor : adjList.getOrDefault(vertex, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        System.out.println(g.bfs(0)); // [0, 1, 2, 3]
    }
}
                                

QuickSort is a divide-and-conquer sorting algorithm that picks a pivot, partitions the array around it, and recursively sorts subarrays. It’s in-place (minimal extra space) and efficient for large datasets, though its O(n²) worst case occurs with already sorted or reverse-sorted arrays. Pivot choice (e.g., random) mitigates this.

• Use Cases: General-purpose sorting, in-memory data.
• Complexity: Average O(n log n), Worst O(n²), Space O(log n).
• Example: Sorting an array.

public class QuickSort {
    public 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);
        }
    }

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

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [11, 12, 22, 25, 34, 64, 90]
    }
}
                                

MergeSort is a stable, divide-and-conquer sorting algorithm that splits an array into halves, recursively sorts them, and merges the sorted halves. It guarantees O(n log n) time regardless of input, making it reliable for linked lists or external sorting, though it uses O(n) extra space.

• Use Cases: Sorting linked lists, stable sorting needs.
• Complexity: O(n log n), Space O(n).
• Example: Sorting an array.

public class MergeSort {
    public static 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);
        }
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1, n2 = r - m;
        int[] L = new int[n1], R = new int[n2];
        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];
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [3, 9, 10, 27, 38, 43, 82]
    }
}
                                

Binary Search efficiently finds an element in a sorted array by repeatedly dividing the search space in half. It’s O(log n) due to its logarithmic reduction, but requires pre-sorted data. Java’s Arrays.binarySearch is a built-in option, though custom implementations are common in interviews.

• Use Cases: Lookup in sorted data, range queries.
• Complexity: O(log n), Space O(1) iterative.
• Example: Finding a target value.

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // Not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40, 50};
        int target = 10;
        int result = binarySearch(arr, target);
        System.out.println(result); // 3 (index of 10)
    }
}
                                

DFS explores a graph or tree by diving as deep as possible along each branch before backtracking. It uses recursion or a stack, making it ideal for pathfinding or detecting cycles. Its O(V + E) complexity suits sparse graphs, though it may not find the shortest path.

• Use Cases: Maze solving, topological sorting.
• Complexity: O(V + E), Space O(V).
• Example: DFS on a graph.

import java.util.*;

public class DFSGraph {
    private Map<Integer, List<Integer>> adjList;

    public DFSGraph() { adjList = new HashMap<>(); }

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    }

    public List<Integer> dfs(int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        dfsRec(start, visited, result);
        return result;
    }

    private void dfsRec(int vertex, Set<Integer> visited, List<Integer> result) {
        visited.add(vertex);
        result.add(vertex);
        for (int neighbor : adjList.getOrDefault(vertex, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsRec(neighbor, visited, result);
            }
        }
    }

    public static void main(String[] args) {
        DFSGraph g = new DFSGraph();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        System.out.println(g.dfs(0)); // [0, 1, 3, 2]
    }
}
                                

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems, storing results to avoid recomputation. Fibonacci numbers are a classic DP example—each number is the sum of the two preceding ones. Memoization (top-down) or tabulation (bottom-up) reduces naive recursion’s O(2^n) to O(n).

• Use Cases: Optimization problems, sequence computation.
• Complexity: O(n) time, O(n) space (tabulation).
• Example: Bottom-up Fibonacci.

public class FibonacciDP {
    public static long fibonacci(int n) {
        if (n <= 1) return n;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibonacci(n)); // 55
    }
}
                                

The 0/1 Knapsack problem finds the maximum value achievable with items (weight, value) within a capacity limit, without fractional selection. DP builds a table to store subproblem solutions, optimizing over recursion’s exponential time.

• Use Cases: Resource allocation, budget planning.
• Complexity: O(nW) time, O(nW) space (n = items, W = capacity).
• Example: 0/1 Knapsack solution.

public class Knapsack {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;
        System.out.println(knapsack(weights, values, capacity)); // 9
    }
}
                                

The Greedy Activity Selection problem maximizes the number of non-overlapping activities by always picking the next activity that finishes earliest. It assumes sorted finish times and achieves optimality with a single pass.

• Use Cases: Scheduling meetings, resource allocation.
• Complexity: O(n log n) with sorting, O(n) after.
• Example: Selecting maximum activities.

public class ActivitySelection {
    public static List<Integer> selectActivities(int[] start, int[] finish) {
        List<Integer> selected = new ArrayList<>();
        selected.add(0); // First activity
        int lastFinish = finish[0];
        for (int i = 1; i < start.length; i++) {
            if (start[i] >= lastFinish) {
                selected.add(i);
                lastFinish = finish[i];
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        List<Integer> result = selectActivities(start, finish);
        System.out.println(result); // [0, 1, 4] (indices of selected activities)
    }
}
                                

Huffman Coding is a greedy algorithm for lossless data compression, assigning shorter codes to frequent characters using a min-heap. It builds a binary tree where leaf nodes are characters, and paths represent codes.

• Use Cases: File compression (e.g., ZIP), text encoding.
• Complexity: O(n log n), Space O(n).
• Example: Basic Huffman tree construction.

import java.util.*;

class HuffmanNode {
    char data;
    int freq;
    HuffmanNode left, right;
    HuffmanNode(char data, int freq) { this.data = data; this.freq = freq; }
}

public class HuffmanCoding {
    public static void printCodes(HuffmanNode root, String code) {
        if (root == null) return;
        if (root.data != '\0') System.out.println(root.data + ": " + code);
        printCodes(root.left, code + "0");
        printCodes(root.right, code + "1");
    }

    public static HuffmanNode buildHuffmanTree(char[] chars, int[] freq) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
        for (int i = 0; i < chars.length; i++) pq.offer(new HuffmanNode(chars[i], freq[i]));
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode parent = new HuffmanNode('\0', left.freq + right.freq);
            parent.left = left;
            parent.right = right;
            pq.offer(parent);
        }
        return pq.poll();
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd'};
        int[] freq = {5, 1, 3, 2};
        HuffmanNode root = buildHuffmanTree(chars, freq);
        printCodes(root, ""); // a: 0, b: 110, c: 10, d: 111
    }
}
                                

Dijkstra’s Algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edges. It uses a priority queue to greedily select the next closest vertex, updating distances as it explores.

• Use Cases: GPS navigation, network routing.
• Complexity: O((V + E) log V) with heap, Space O(V).
• Example: Shortest path calculation.

import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) { this.to = to; this.weight = weight; }
}

public class Dijkstra {
    public static int[] dijkstra(Map<Integer, List<Edge>> graph, int source, int vertices) {
        int[] dist = new int[vertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], d = curr[1];
            if (d > dist[u]) continue;
            for (Edge e : graph.getOrDefault(u, Collections.emptyList())) {
                int v = e.to, weight = e.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(new Edge(1, 4), new Edge(2, 1)));
        graph.put(1, Arrays.asList(new Edge(3, 1)));
        graph.put(2, Arrays.asList(new Edge(1, 2), new Edge(3, 5)));
        graph.put(3, Collections.emptyList());
        int[] dist = dijkstra(graph, 0, 4);
        System.out.println(Arrays.toString(dist)); // [0, 3, 1, 4]
    }
}
                                

Kruskal’s Algorithm finds the Minimum Spanning Tree (MST) of an undirected, weighted graph by greedily adding the smallest edges that don’t form cycles. It uses a Union-Find data structure to detect cycles efficiently.

• Use Cases: Network design (e.g., cabling), clustering.
• Complexity: O(E log E), Space O(V).
• Example: MST construction.

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, weight;
    Edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; }
    @Override public int compareTo(Edge o) { return Integer.compare(this.weight, o.weight); }
}

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }
    void union(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return;
        if (rank[pu] < rank[pv]) parent[pu] = pv;
        else if (rank[pu] > rank[pv]) parent[pv] = pu;
        else { parent[pv] = pu; rank[pu]++; }
    }
}

public class Kruskal {
    public static List<Edge> kruskal(List<Edge> edges, int vertices) {
        List<Edge> mst = new ArrayList<>();
        Collections.sort(edges);
        UnionFind uf = new UnionFind(vertices);
        for (Edge e : edges) {
            if (uf.find(e.u) != uf.find(e.v)) {
                uf.union(e.u, e.v);
                mst.add(e);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 1));
        edges.add(new Edge(1, 2, 2));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 3));
        List<Edge> mst = kruskal(edges, 4);
        mst.forEach(e -> System.out.println(e.u + " - " + e.v + ": " + e.weight));
        // 0 - 2: 1, 1 - 2: 2, 2 - 3: 3
    }
}
                                

The Knuth-Morris-Pratt (KMP) algorithm efficiently searches for a pattern in a text by precomputing a longest prefix-suffix (LPS) array, avoiding redundant comparisons. It’s O(n + m) versus naive O(nm), where n is text length and m is pattern length.

• Use Cases: Text editors, DNA sequence matching.
• Complexity: O(n + m), Space O(m).
• Example: Finding pattern occurrences.

public class KMP {
    public static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> indices = new ArrayList<>();
        int[] lps = computeLPS(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                indices.add(i - j);
                j = lps[j - 1];
            } else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return indices;
    }

    private static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0, i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i++] = len;
            } else if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABC";
        List<Integer> result = kmpSearch(text, pattern);
        System.out.println(result); // [10]
    }
}
                                

Rabin-Karp uses hashing to find pattern matches in a text, sliding a window and comparing hash values. It’s O(n + m) on average, though O(nm) in worst cases (hash collisions). A rolling hash reduces recomputation.

• Use Cases: Plagiarism detection, multi-pattern search.
• Complexity: O(n + m) average, O(nm) worst, Space O(1).
• Example: Pattern search with rolling hash.

public class RabinKarp {
    private static final int d = 256; // Number of characters
    private static final int q = 101; // Prime number for modulo

    public static List<Integer> rabinKarpSearch(String text, String pattern) {
        List<Integer> indices = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m > n) return indices;

        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 + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        for (int i = 0; i <= n - m; i++) {
            if (p == t) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (pattern.charAt(j) != text.charAt(i + j)) {
                        match = false;
                        break;
                    }
                }
                if (match) indices.add(i);
            }
            if (i < n - m) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;
                if (t < 0) t += q;
            }
        }
        return indices;
    }

    public static void main(String[] args) {
        String text = "GEEKSFORGEEKS";
        String pattern = "GEEKS";
        List<Integer> result = rabinKarpSearch(text, pattern);
        System.out.println(result); // [0, 8]
    }
}