Essential Algorithms and Data Structures: A Quick Reference

Essential Algorithms and Data Structures

Longest Increasing Subsequence (LIS):

• Subproblem: dp[i] = length of LIS ending at index i
• Recursion: dp[i] = max(dp[j] + 1 for j < i and arr[j] < arr[i])
• Base case: dp[i] = 1 (every element is a subsequence of length 1)
• Time Complexity: O(n^2), O(n log n) with binary search optimization.

Longest Alternating Subsequence (LAS):

• Subproblem: dp[i][0] (increasing), dp[i][1] (decreasing)
• Recursion: dp[i][0] = max(dp[j][1] + 1 for j < i and arr[j] < arr[i]), dp[i][1] = max(dp[j][0] + 1 for j < i and arr[j] > arr[i])
• Base case: dp[0][0] = 1, dp[0][1] = 1
• Time Complexity: O(n^2)

0/1 Knapsack Problem:

• Subproblem: dp[i][w] = maximum value for the first i items and weight limit w
• Recursion: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) if wi <= w
• Base case: dp[0][w] = 0 (no items to take)
• Time Complexity: O(nW) where W is the max weight capacity.

Kruskal’s Algorithm (MST): Sort edges by weight. Add the smallest edge that doesn’t form a cycle using Union-Find (Disjoint Set Union). Time Complexity: O(E log V)

Prim’s Algorithm (MST): Start from an arbitrary node, add the smallest edge that connects a node in the MST to a node outside it. Time Complexity: O(E log V) with a priority queue (Min-Heap).

Dijkstra’s Algorithm (Shortest Path): Input: Weighted, directed graph with non-negative weights. Use a priority queue to always extend the shortest known path. Time Complexity: O(E log V)

Huffman Coding (Greedy Encoding): Build a binary tree based on frequency of characters. Time Complexity: O(n log n) for n symbols.

DFS (Depth-First Search): Use a stack (or recursion) explores as far as possible along a branch before backtracking. Time Complexity: O(V+E)

BFS (Breadth-First Search): Use a queue. Explores all neighbors at the present depth before moving on to nodes at the next depth level. Time Complexity: O(V+E)

Bellman-Ford Algorithm (Shortest Path with Negative Weights): Input: Weighted directed graph with possible negative edge weights. Relaxation: For each edge, update the shortest path if a better path is found. Time Complexity: O(VE)

Floyd-Warshall Algorithm (All-Pairs Shortest Path): Input: Weighted directed graph. Use dynamic programming to compute the shortest paths between all pairs of nodes. Time Complexity: O(V^3)

Merge Sort: Recursively divide the array into halves, then merge them in sorted order. Time Complexity: O(n log n)

Quick Sort: Pick a pivot, partition the array, and recursively sort the two halves. Time Complexity: O(n log n) on average, O(n^2) in the worst case.

Binary Search: Efficiently find the target value in a sorted array by repeatedly halving the search range. Time Complexity: O(log n)

Union-Find / Disjoint Set Data Structure Operations: Find (find the root of a set), Union (merge two sets). Union by Rank and Path Compression optimize the performance. Time Complexity: Almost constant, O(α(n)), where α(n) is the inverse Ackermann function.

Matrix Multiplication (Divide and Conquer): Time Complexity: Standard: O(n^3), Strassen’s algorithm: O(n^{2.81})

Topological Sort (Directed Acyclic Graph): Sort nodes of a directed graph in linear order where for every directed edge uv, vertex u comes before v. Use DFS or Kahn’s Algorithm (BFS).

Recursion to Iteration: Often recursion can be turned into an iterative approach using a stack (e.g., DFS).

Memoization: If the problem involves overlapping subproblems, consider memoizing results to avoid recomputing them.

Bottom-Up DP: Often more efficient in terms of space than top-down recursion with memoization.