Skip to content

Tejas242/patterns

Repository files navigation

DSA Patterns Cheatsheet

C++17 LeetCode Codeforces

A comprehensive collection of essential Data Structures & Algorithms patterns


Table of Contents


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

Tools & Extensions


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! ⭐

About

A comprehensive collection of essential Data Structures & Algorithms patterns

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages