∞

Algo Infinity Verse

📝 DSA Cheat Sheets

Comprehensive quick reference guides for core data structures and algorithms.

📊

Arrays

Complexity Table

Access Search Insertion Deletion
O(1) O(n) O(n) O(n)
Space Complexity (Average/Worst): O(n)

Common Operations

  • Access: Retrieve element at index i via offset.
  • Search: Scan array element-by-element (Linear) or halves (Binary, if sorted).
  • Insertion/Deletion: Shift elements to adjust index placements.

Important Notes

  • Elements are stored contiguously in memory, enabling constant-time random access.
  • Static arrays have a fixed size; dynamic arrays resize by doubling capacity ($O(1)$ amortized insertion).

Interview Tips

  • Always check for edge cases: empty array, single element, or index out of bounds.
  • If the input array is sorted, consider using the Two Pointers or Binary Search techniques.

Common Coding Patterns

  • Two Pointers: Opposite ends (Two Sum) or slow/fast runner.
  • Sliding Window: Subarray tracking for bounds/sums.
  • Kadane's Algorithm: Maximizing subarray sums in $O(n)$ time.
🔤

Strings

Complexity Table

Access Search (KMP) Concatenate Comparison
O(1) O(n + m) O(n + m) O(n)
Space Complexity (Average/Worst): O(n)

Common Operations

  • Length check: Retrieve number of characters.
  • Substring extraction: Copy a slice of characters from index i to j.
  • Pattern matching: Locate sub-patterns (KMP, Rabin-Karp).

Important Notes

  • In many languages (JS, Python, Java), strings are immutable. Changes generate new strings.
  • Substrings of length k take $O(k)$ time and space to copy or instantiate.

Interview Tips

  • Use a character frequency hash map or fixed-size ASCII array ($128$ or $256$ elements) to count characters.
  • Palindrome checks are best handled using a two-pointer convergence pattern.

Common Coding Patterns

  • Sliding Window: Track unique characters (e.g., Longest Substring Without Repeating).
  • Two Pointers: Palindromes, reverse character arrays.
  • Hashing/Frequency Arrays: Anagram tracking, duplicate checks.
🔗

Linked Lists

Complexity Table

Access Search Insert (Head/Tail) Delete (Node)
O(n) O(n) O(1) O(1)
Space Complexity (Average/Worst): O(n)

Common Operations

  • Traversal: Step from node to node via pointers until pointer is null.
  • Reversal: Pivot pointers in-place to reverse directions.
  • Cycle Detection: Check if a traversal path loops back on itself.

Important Notes

  • Nodes are non-contiguous in memory. Insertion/deletion does not require shifting elements.
  • Sentinel or dummy nodes simplify insertion/deletion logic at list edges.

Interview Tips

  • Verify pointer references are updated in the correct order to prevent losing node connections.
  • Test with empty lists, single node lists, and lists containing cyclic loops.

Common Coding Patterns

  • Fast & Slow Pointers: Floyd's cycle finder, finding list midpoints.
  • Dummy Head: Simplifies merged list operations or node deletion.
  • In-place Pointer Swapping: Reversing lists or swapping node pairs.
🌳

Trees

Complexity Table (BST)

Operation Average (Balanced) Worst (Skewed)
Search O(log n) O(n)
Insertion O(log n) O(n)
Deletion O(log n) O(n)
Space Complexity (Balanced / Skewed): O(log n) / O(n)

Common Operations

  • DFS (Traversals): Pre-order, In-order, Post-order paths recursively.
  • BFS (Level-order): Visit nodes level-by-level using a Queue.
  • BST Properties: Left subtree < Node < Right subtree.

Important Notes

  • An In-order traversal on a Binary Search Tree (BST) visits elements in sorted order.
  • Recursion depth space is determined by tree height: $O(\log n)$ balanced, $O(n)$ skewed.

Interview Tips

  • Most tree problems are recursive. Define base cases (e.g. if (root === null)) clearly.
  • Remember that BFS uses an iterative Queue, while DFS uses recursion or a Stack.

Common Coding Patterns

  • DFS (Recursion): Tree depth, checking symmetric properties, path sums.
  • BFS (Queue): Minimum depth, level averages, right-side views.
  • Divide & Conquer: BST conversions, serializing structures.
🕸️

Graphs

Complexity Table

Algorithm Time Complexity Space Complexity
DFS / BFS O(V + E) O(V)
Dijkstra O((V + E) log V) O(V)
Kruskal (MST) O(E log E) O(V)
Adjacency List / Matrix Space: O(V + E) / O(V²)

Common Operations

  • DFS: Explore nodes recursively as deep as possible before backtracking.
  • BFS: Explore nodes level-by-level using a Queue.
  • Topological Sort: Order DAG vertices linearly.

Important Notes

  • Adjacency Lists are space-efficient; Adjacency Matrices allow $O(1)$ edge query lookups.
  • Cycles in directed graphs are detected using a recursion/visited stack state.

Interview Tips

  • BFS is the optimal choice for finding the shortest path in an unweighted graph.
  • Ensure you keep a visited set to avoid entering infinite cycles in general graphs.

Common Coding Patterns

  • DFS (Pathfinding): Island counting, connected components, cycle checks.
  • BFS (Shortest Path): Word transformations, matrix maze routing.
  • Union-Find: Dynamic connectivity, minimum spanning trees.
🎯

Dynamic Programming

Complexity Table

Problem Class Time Complexity Space Complexity
Climbing Stairs O(n) O(1) / O(n)
0/1 Knapsack O(n * W) O(n * W) / O(W)
LCS / LIS O(n * m) / O(n²) O(n * m) / O(n)
General Space: O(n) / O(n²) optimized to O(1)

Common Operations

  • Subproblems: Break global problem into overlapping smaller pieces.
  • Memoization: Cache recursive states top-down.
  • Tabulation: Fill iteration tables bottom-up from base cases.

Important Notes

  • Applicable only if optimal substructure and overlapping subproblems are present.
  • DP array space can often be optimized to $O(1)$ by retaining only the last few indices.

Interview Tips

  • Think of DP if a problem asks for "min/max value", "number of ways", or "feasibility".
  • Write a recursive brute-force solution first, then memoize it to speed up your coding.

Common Coding Patterns

  • Fibonacci Sequence: climbing stairs, house robber.
  • 0/1 Knapsack: coin change, partition equal subset sums.
  • LCS/LIS: edit distance, grid paths, longest common sequences.