DSA Patterns Cheatsheet

A comprehensive collection of essential Data Structures & Algorithms patterns

---

Table of Contents

• Pattern Categories
• Competitive Programming Tips
• Template & Setup
• Common Patterns
• Complexity Cheatsheet
• Resources

---

Pattern Categories

Arrays & Strings

Pattern	File	Key Problems	Time Complexity
Two Pointers	two_pointers.cpp	3Sum, Container With Most Water	O(n)
Sliding Window	sliding_window.cpp	Longest Substring, Subarray Sum	O(n)
Prefix Sum	prefix_sum.cpp	Range Sum Query, Subarray Sum	O(1) query
Kadane's Algorithm	kadane.cpp	Maximum Subarray, Maximum Product	O(n)

String Patterns

Pattern	File	Key Problems	Time Complexity
Hash Maps & Anagrams	string_patterns.cpp	Group Anagrams, Two Sum	O(n)
Sliding Window	string_patterns.cpp	Min Window Substring	O(n)
KMP Algorithm	string_patterns.cpp	Pattern Matching	O(n+m)
Rolling Hash	string_patterns.cpp	Rabin-Karp, Longest Prefix	O(n)

Data Structures

Pattern	File	Key Problems	Time Complexity
Stack & Queue	stack_queue.cpp	Valid Parentheses, Min Stack	O(1) ops
Linked Lists	linkedlist.cpp	Reverse List, Detect Cycle	O(n)
Heaps & Priority Queue	heap_priority_queue.cpp	Top K, Merge K Lists	O(log n) ops
Trie (Prefix Tree)	trie.cpp	Word Search II, Auto-complete	O(m) ops

Binary Search

Pattern	File	Key Problems	Time Complexity
Binary Search	binary_search.cpp	Search Insert Position, First/Last	O(log n)

Sorting & Custom Comparators

Pattern	File	Key Problems	Time Complexity
Sorting Algorithms	sorting_algorithms.cpp	Quick Sort, Merge Sort, Heap Sort	O(n log n)
Custom Comparators	sorting_algorithms.cpp	Merge Intervals, Meeting Rooms	O(n log n)

Matrix & 2D Arrays

Pattern	File	Key Problems	Time Complexity
Matrix Traversal	matrix_patterns.cpp	Spiral Matrix, Rotate Image	O(mn)
Matrix Search	matrix_patterns.cpp	Search 2D Matrix	O(log mn)
Island Problems	matrix_patterns.cpp	Number of Islands, Max Area	O(mn)

Backtracking & Combinatorics

Pattern	File	Key Problems	Time Complexity
Generate All	backtracking_patterns.cpp	Subsets, Permutations	O(2^n)
Constraint Satisfaction	backtracking_patterns.cpp	N-Queens, Sudoku Solver	O(b^d)
Word Search	backtracking_patterns.cpp	Word Search, Palindrome Partition	O(4^mn)

Bit Manipulation

Pattern	File	Key Problems	Time Complexity
XOR Properties	bit_patterns.cpp	Single Number, Missing Number	O(n)
Bit Operations	bit_patterns.cpp	Power of Two, Reverse Bits	O(1)
Subset Generation	bit_patterns.cpp	Generate Subsets using Bits	O(2^n)

Binary Search

Pattern	File	Key Problems	Time Complexity
Binary Search	binary_search.cpp	Search Insert Position, First/Last	O(log n)

Sorting & Custom Comparators

Pattern	File	Key Problems	Time Complexity
Sorting Algorithms	sorting_algorithms.cpp	Quick Sort, Merge Sort, Heap Sort	O(n log n)
Custom Comparators	sorting_algorithms.cpp	Merge Intervals, Meeting Rooms	O(n log n)

Trees

Pattern	File	Key Problems	Time Complexity
Traversals	traversals.cpp	Inorder, Preorder, Postorder, Level Order	O(n)
LCA	lca.cpp	Lowest Common Ancestor	O(log n)
Tree DP	tree_dp.cpp	Diameter, Path Sum, Subtree Queries	O(n)

Graphs

Pattern	File	Key Problems	Time Complexity
DFS/BFS	dfs_bfs.cpp	Connected Components, Shortest Path	O(V+E)
Dijkstra	dijkstra.cpp	Shortest Path, Network Delay	O(E log V)
Union Find	union_find.cpp	Connected Components, MST	O(α(n))
Topological Sort	topo_sort.cpp	Course Schedule, Alien Dictionary	O(V+E)

Dynamic Programming

Pattern	File	Key Problems	Time Complexity
1D DP	dp_1d.cpp	Fibonacci, Climbing Stairs, House Robber	O(n)
2D DP	dp_2d.cpp	Unique Paths, Edit Distance	O(nm)
LIS/LCS	lis_lcs.cpp	Longest Increasing Subsequence	O(n log n)
Knapsack	knapsack.cpp	0/1 Knapsack, Coin Change	O(nW)

Greedy Algorithms

Pattern	File	Key Problems	Time Complexity
Interval Scheduling	greedy_patterns.cpp	Meeting Rooms, Merge Intervals	O(n log n)
Greedy Choice	greedy_patterns.cpp	Jump Game, Gas Station	O(n)
Optimization	greedy_patterns.cpp	Minimum Cost, Maximum Profit	O(n log n)

Game Theory

Pattern	File	Key Problems	Time Complexity
Minimax	game_theory_patterns.cpp	Stone Game, Predict Winner	O(n²)
Nim Games	game_theory_patterns.cpp	Nim Game, Stone Game II	O(n)
Zero-Sum Games	game_theory_patterns.cpp	Optimal Strategy, Game Winning	O(n²)

Math & Number Theory

Pattern	File	Key Problems	Time Complexity
GCD/LCM	gcd_lcm.cpp	Greatest Common Divisor	O(log min(a,b))
Prime Numbers	primes.cpp	Sieve, Primality Testing	O(n log log n)
Modular Arithmetic	modular.cpp	Fast Exponentiation, Modular Inverse	O(log n)

Design Patterns (LeetCode Design Tag)

Pattern	File	Key Problems	Time Complexity
Cache Systems	design_patterns.cpp	LRU Cache, LFU Cache, Time-Based KV	O(1) ops
Data Structures	design_patterns.cpp	Stack/Queue, HashSet/HashMap, Trie	O(1) - O(log n)
Iterators	design_patterns.cpp	BST Iterator, Peeking Iterator	O(1) amortized
Specialized	design_patterns.cpp	Hit Counter, Twitter, Snake Game	Varies

Advanced Data Structures

Pattern	File	Key Problems	Time Complexity
Segment Tree	segment_tree.cpp	Range Sum/Min/Max Query	O(log n)
Fenwick Tree	fenwick_tree.cpp	Range Sum, Inversion Count	O(log n)

System Design Patterns

Pattern	File	Key Problems	Time Complexity
LRU Cache	system_design_patterns.cpp	LRU Cache, LFU Cache	O(1) ops
Rate Limiter	system_design_patterns.cpp	Token Bucket, Sliding Window	O(1)
Consistent Hashing	system_design_patterns.cpp	Load Balancing, Distributed Systems	O(log n)

Template & Utilities

Pattern	File	Key Problems	Time Complexity
CP Template	cp_template.cpp	Fast I/O, Common Macros, Debugging	O(1)
Common Utilities	cp_template.cpp	GCD, Power, Modular Operations	Varies

---

Template & Setup

Optimized CP Template

See cp_template.cpp for the complete template.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr);

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Debug helper (works only in local environment)
#ifdef DEBUG
#define debug(x) cerr << #x << " = " << (x) << "\n"
#else
#define debug(x)
#endif

int main() {
    FAST;
    
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for(auto &x : arr) cin >> x;
        
        sort(all(arr));
        for(auto x : arr)
            cout << x << " ";
        cout << "\n";
    }
    
    return 0;
}

VS Code Setup for CP

// .vscode/settings.json
{
    "files.associations": {
        "*.cpp": "cpp"
    },
    "code-runner.executorMap": {
        "cpp": "cd $dir && g++ -std=c++17 -O2 -o $fileNameWithoutExt $fileName && ./$fileNameWithoutExt"
    },
    "code-runner.runInTerminal": true,
    "C_Cpp.default.cppStandard": "c++17"
}

Compilation Commands

# For competitive programming (optimized)
g++ -std=c++17 -O2 -Wall -Wextra -o solution solution.cpp

# For debugging
g++ -std=c++17 -g -DLOCAL -o solution solution.cpp

# One-liner for contests
alias cpr="g++ -std=c++17 -O2 -o sol"

---

Competitive Programming Tips

Problem-Solving Strategy

1. Read & Understand (2-3 min)

   • Identify input/output format
   • Find constraints and edge cases
   • Look for patterns in examples

2. Pattern Recognition (1-2 min)

   • Array/String → Two pointers, Sliding window
   • Tree/Graph → DFS/BFS, DP on trees
   • Optimization → DP, Greedy, Binary search
   • Range queries → Segment tree, Fenwick tree

3. Implementation (10-15 min)

   • Use templates from this repository
   • Focus on correctness first, then optimize
   • Handle edge cases

4. Testing (2-3 min)

   • Test with given examples
   • Think of edge cases
   • Dry run with small inputs

Time-Saving Tricks

// Fast I/O for large inputs
ios::sync_with_stdio(false);
cin.tie(nullptr);

// Vector initialization shortcuts
vector<int> dp(n, -1);           // Initialize with -1
vector<vector<int>> grid(n, vector<int>(m, 0)); // 2D grid

// STL shortcuts
sort(all(v));                    // Sort entire vector
reverse(all(v));                 // Reverse vector
v.erase(unique(all(v)), v.end()); // Remove duplicates

// Common patterns
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

---

Common Patterns

Pattern Recognition Guide

Problem Type	Common Keywords	Suggested Approach
Two Sum/Pair	"pair", "two elements", "target sum"	Two pointers, Hash map
Subarray/Substring	"contiguous", "subarray", "substring"	Sliding window, Prefix sum
Path/Connection	"path", "connected", "reachable"	DFS/BFS, Union Find
Optimization	"minimum", "maximum", "optimal"	DP, Greedy, Binary search
Range Query	"range", "interval", "segment"	Segment tree, Fenwick tree
Counting	"count", "number of ways"	DP, Combinatorics

Mental Models

// Two Pointers Template
int left = 0, right = n - 1;
while (left < right) {
    if (condition) left++;
    else right--;
}

// Sliding Window Template
int left = 0, right = 0;
while (right < n) {
    // Expand window
    while (invalid_condition) {
        // Shrink window
        left++;
    }
    // Update answer
    right++;
}

// Binary Search Template
int left = 0, right = n;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) right = mid;
    else left = mid + 1;
}

---

Complexity Cheatsheet

Time Complexities

Algorithm	Best	Average	Worst	Space
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)
DFS/BFS	O(V + E)	O(V + E)	O(V + E)	O(V)
Dijkstra	O(E log V)	O(E log V)	O(E log V)	O(V)

Data Structure Operations

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Hash Table	O(1)	O(1)	O(1)	O(1)	O(n)
Binary Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Heap	O(1)	O(n)	O(log n)	O(log n)	O(n)
Segment Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(n)

Constraint Guidelines

// n <= 10^8:   O(log n), O(1)
// n <= 10^6:   O(n), O(n log n)
// n <= 10^4:   O(n²)
// n <= 500:    O(n³)
// n <= 20:     O(2^n), O(n!)
// n <= 10:     O(n!)

---

Resources

Learning Platforms

• LeetCode - Practice problems with solutions
• Codeforces - Competitive programming contests
• AtCoder - High-quality contest problems
• HackerRank - Coding challenges and tutorials

Reference Materials

• CP-Algorithms - Comprehensive algorithm explanations
• USACO Guide - Structured competitive programming curriculum
• Competitive Programming 4 - Steven Halim's book
• Introduction to Algorithms (CLRS) - Classic algorithms textbook

Tools & Extensions

• Competitive Programming Helper - VS Code extension
• LeetCode Extension - Practice in VS Code
• Polygon - Problem preparation platform

---

Contributing

1. Fork the repository
2. Add new patterns or improve existing ones
3. Ensure code follows the template format
4. Add relevant LeetCode problem links
5. Submit a pull request

---

⭐ Star this repository if it helped you in your competitive programming journey! ⭐