Kaushik's Notes

DSA Patterns

2 min read

  1. Strings & Its Patterns
  • KMP Algorithm
  • Z-Algorithm
  • Rabin-Karp Algorithm
  • Longest Common Subsequence (LCS)
  • Edit Distance
  • Regular Expression Matching
  • Palindrome Problems
  1. Dynamic Programming (DP) & Its Patterns
  • Fibonacci/Simple Recurrence
  • 0/1 Knapsack
  • Unbounded Knapsack
  • Longest Common Subsequence (LCS)
  • Longest Increasing Subsequence (LIS)
  • Grid-Based DP
  • Interval DP
  • Tree DP
  • Bitmasking/State Compression
  • Digit DP
  • Probability/Expectation DP
  1. Graphs & Its Patterns
  • DFS/BFS Traversal
  • Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
  • Topological Sort
  • Cycle Detection
  • Connected Components
  • Minimum Spanning Tree (MST)
  • Union-Find (Disjoint Set Union - DSU)
  • Grid-Based Graph Problems
  • Graph Coloring
  • Strongly Connected Components (SCC)
  • Eulerian & Hamiltonian Paths
  • Planets & Queries (Advanced Graph Problems)
  1. Trees & Its Patterns
  • Distance Between Nodes (LCA, BFS/DFS)
  • Sum of Distances (Rerooting Technique)
  • Subtree Queries (Segment Trees, Heavy-Light Decomposition)
  • Binary Lifting (LCA Optimization)
  • Tree DP (Dynamic Programming on Trees)
  • Path Queries (Prefix Sums, Binary Lifting)
  • Tree Construction (BST, Trie, etc.)
  1. Heap (Priority Queue) & Its Patterns
  • Top K Elements
  • Merge K Sorted Structures
  • Two Heaps for Medians
  • Sliding Window Heaps
  • Greedy Heap Applications
  • Heap-based Game Theory
  1. Linked Lists & Its Patterns
  • Fast and Slow Pointers (Two Pointers)
  • Reversing Linked Lists
  • Merging and Partitioning Lists
  • Dummy Node Technique
  • List Manipulation Operations
  • List Transformations
  • Basic List Operations Implementation

→  Secondary/Supporting Data Structures for interviews

  • Hash Maps / Hash Sets (used in string matching, graph traversals, etc.)
  • Stacks & Queues (used in DFS/BFS, parsing, etc.)
  • Binary Search Trees (BST) (used in some tree-based problems)
  • Trie (Prefix Tree) (used in string matching problems)
  • Segment Trees & Fenwick Trees (used in range queries, subtree problems)
  • Monotonic Stacks/Queues (used in sliding window problems)

Graph View

Backlinks