Basic Syntax & Patterns
STL Containers
STL Algorithms
String Manipulation
Pointers & Memory Management
Trees & Graphs
Dynamic Programming
Sorting & Searching
Mathematical Algorithms
Advanced Patterns
Interview Tips

Basic Syntax & Patterns

Essential Headers & Namespace

#include <iostream>      // Input/output
#include <vector>        // Dynamic arrays
#include <string>        // Strings
#include <algorithm>     // STL algorithms
#include <map>          // Ordered map
#include <unordered_map> // Hash map
#include <set>          // Ordered set
#include <unordered_set> // Hash set
#include <queue>        // Queue, priority_queue
#include <stack>        // Stack
#include <deque>        // Double-ended queue
#include <climits>      // INT_MAX, INT_MIN
#include <cmath>        // Math functions
 
using namespace std;

Input/Output Optimization

// Fast I/O for competitive programming
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
 
// Reading until EOF
int x;
while (cin >> x) {
    // Process x
}
 
// Reading a line with spaces
string line;
getline(cin, line);

Common Data Types & Limits

// Integer types
int num = 42;                    // 32-bit: -2^31 to 2^31-1
long long bigNum = 1234567890LL; // 64-bit: -2^63 to 2^63-1
unsigned int positiveNum = 42U;  // 32-bit: 0 to 2^32-1
 
// Constants
const int INF = INT_MAX;         // 2147483647
const long long LINF = LLONG_MAX; // 9223372036854775807
const int MOD = 1e9 + 7;         // Common modulo for problems
 
// Auto type inference
auto result = 42;                // int
auto lambda = [](int x) { return x * 2; };

Lambda Functions

// Basic lambda
auto add = [](int a, int b) { return a + b; };
 
// Lambda with capture
int multiplier = 5;
auto multiply = [multiplier](int x) { return x * multiplier; };
 
// Capture by reference
auto increment = [&multiplier](int x) { 
    multiplier++; 
    return x + multiplier; 
};
 
// Generic lambda (C++14)
auto genericLambda = [](auto x, auto y) { return x + y; };

Range-based For Loops

vector<int> nums = {1, 2, 3, 4, 5};
 
// Read-only iteration
for (const auto& num : nums) {
    cout << num << " ";
}
 
// Modifying elements
for (auto& num : nums) {
    num *= 2;
}
 
// Index-based with enumerate pattern
for (int i = 0; i < nums.size(); ++i) {
    cout << "Index " << i << ": " << nums[i] << "\n";
}

Commonly Used Macros

#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
 
// Loop macros
#define for0(i, n) for (int i = 0; i < n; ++i)
#define for1(i, n) for (int i = 1; i <= n; ++i)
#define fore(i, a, b) for (int i = a; i <= b; ++i)

STL Containers

Vector (Dynamic Array)

// Declaration and initialization
vector<int> v1;                    // Empty vector
vector<int> v2(5);                 // Size 5, filled with 0s
vector<int> v3(5, 10);             // Size 5, filled with 10s
vector<int> v4 = {1, 2, 3, 4, 5}; // Initializer list
vector<int> v5(v4);                // Copy constructor
 
// Common operations - O(1) amortized for push_back
v1.push_back(42);         // Add element to end
v1.pop_back();            // Remove last element
int size = v1.size();     // Get size
bool empty = v1.empty();  // Check if empty
v1.clear();               // Remove all elements
 
// Access - O(1)
int first = v1[0];        // No bounds checking
int first_safe = v1.at(0); // Bounds checking
int last = v1.back();     // Last element
int* data = v1.data();    // Pointer to underlying array
 
// Insertion/Deletion - O(n) for middle operations
v1.insert(v1.begin() + 2, 99);           // Insert at position
v1.erase(v1.begin() + 2);                // Erase at position
v1.erase(v1.begin() + 1, v1.begin() + 3); // Erase range
 
// Resize and reserve
v1.resize(10);            // Change size
v1.reserve(100);          // Reserve capacity

String

// Declaration and initialization
string s1;                        // Empty string
string s2(10, 'a');              // "aaaaaaaaaa"
string s3 = "Hello";             // From literal
string s4(s3);                   // Copy
 
// Common operations
s1 += "World";           // Concatenation
s1.append(" C++");       // Append
int len = s1.length();   // Get length
bool empty = s1.empty(); // Check if empty
 
// Access and modification
char ch = s1[0];         // Character access
s1[0] = 'h';            // Modify character
 
// Substring and searching
string sub = s1.substr(0, 5);     // Substring from index 0, length 5
size_t pos = s1.find("World");    // Find substring (returns string::npos if not found)
size_t pos2 = s1.find('W');       // Find character
 
// Conversion
int num = stoi("123");            // String to int
long long bigNum = stoll("123456789"); // String to long long
double d = stod("3.14");          // String to double
string numStr = to_string(42);    // Number to string

Pair and Tuple

// Pair - holds two values
pair<int, string> p1 = {42, "answer"};
pair<int, string> p2 = make_pair(42, "answer");
 
// Access
int first = p1.first;
string second = p1.second;
 
// Comparison (lexicographic)
pair<int, int> a = {1, 2};
pair<int, int> b = {1, 3};
bool less = a < b;  // true
 
// Tuple - holds multiple values
tuple<int, string, double> t1 = {42, "hello", 3.14};
tuple<int, string, double> t2 = make_tuple(42, "hello", 3.14);
 
// Access
int val = get<0>(t1);      // Get first element
string str = get<1>(t1);   // Get second element
 
// Structured bindings (C++17)
auto [x, y, z] = t1;       // Unpack tuple

Map (Ordered Key-Value Store)

// Declaration - O(log n) operations, keys are sorted
map<string, int> m1;                    // Empty map
map<string, int> m2 = {{"apple", 5}, {"banana", 3}};
 
// Insertion - O(log n)
m1["key"] = 42;                         // Insert/update
m1.insert({"another", 10});             // Insert pair
m1.insert(make_pair("third", 20));      // Insert with make_pair
 
// Access - O(log n)
int val = m1["key"];                    // Returns 0 if key doesn't exist
int val_safe = m1.at("key");            // Throws exception if key doesn't exist
 
// Search - O(log n)
auto it = m1.find("key");               // Returns iterator
if (it != m1.end()) {
    cout << it->first << ": " << it->second << "\n";
}
bool exists = m1.count("key") > 0;      // Check existence
 
// Deletion - O(log n)
m1.erase("key");                        // By key
m1.erase(it);                           // By iterator
 
// Iteration - sorted order
for (const auto& [key, value] : m1) {   // C++17 structured binding
    cout << key << ": " << value << "\n";
}
for (auto it = m1.begin(); it != m1.end(); ++it) {
    cout << it->first << ": " << it->second << "\n";
}

Unordered Map (Hash Table)

// Declaration - O(1) average operations
unordered_map<string, int> um1;
unordered_map<string, int> um2 = {{"apple", 5}, {"banana", 3}};
 
// Operations same as map but O(1) average, O(n) worst case
um1["key"] = 42;
int val = um1["key"];
auto it = um1.find("key");
um1.erase("key");
 
// Custom hash function for pairs
struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};
unordered_map<pair<int, int>, int, PairHash> pairMap;

Set (Ordered Unique Elements)

// Declaration - O(log n) operations, sorted unique elements
set<int> s1;                            // Empty set
set<int> s2 = {3, 1, 4, 1, 5};          // {1, 3, 4, 5} - duplicates removed
 
// Insertion - O(log n)
s1.insert(42);                          // Returns pair<iterator, bool>
auto [iter, inserted] = s1.insert(42);  // C++17: check if actually inserted
 
// Search - O(log n)
auto it = s1.find(42);                  // Returns iterator
bool exists = s1.count(42) > 0;         // Check existence
bool contains = s1.contains(42);        // C++20
 
// Deletion - O(log n)
s1.erase(42);                          // By value
s1.erase(it);                          // By iterator
 
// Range operations
auto lower = s1.lower_bound(30);        // First element >= 30
auto upper = s1.upper_bound(50);        // First element > 50

Unordered Set (Hash Set)

// Declaration - O(1) average operations
unordered_set<int> us1;
unordered_set<int> us2 = {1, 2, 3, 4, 5};
 
// Operations same as set but O(1) average
us1.insert(42);
bool exists = us1.count(42) > 0;
us1.erase(42);

Multi-containers (Allow Duplicates)

// Multiset - allows duplicate elements
multiset<int> ms = {1, 2, 2, 3, 3, 3};
ms.insert(2);                          // Now has three 2's
int count_2 = ms.count(2);             // Returns 3
 
// Multimap - allows duplicate keys
multimap<string, int> mm;
mm.insert({"grade", 85});
mm.insert({"grade", 90});
auto range = mm.equal_range("grade");   // Get range of all "grade" entries

Queue and Stack

// Queue (FIFO) - front insertion/deletion O(1)
queue<int> q;
q.push(1);                             // Add to back
q.push(2);
int front = q.front();                 // Access front element
q.pop();                               // Remove front element
bool empty = q.empty();
 
// Stack (LIFO) - top insertion/deletion O(1)
stack<int> st;
st.push(1);                            // Add to top
st.push(2);
int top = st.top();                    // Access top element
st.pop();                              // Remove top element
 
// Priority Queue (Max Heap by default)
priority_queue<int> pq_max;            // Max heap
priority_queue<int, vector<int>, greater<int>> pq_min; // Min heap
pq_max.push(3);
pq_max.push(1);
pq_max.push(4);
int max_elem = pq_max.top();           // Returns 4
pq_max.pop();
 
// Custom comparator for priority queue
struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;    // Min heap by second element
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> custom_pq;

Deque (Double-Ended Queue)

// Deque - O(1) insertion/deletion at both ends
deque<int> dq;
dq.push_front(1);                      // Add to front
dq.push_back(2);                       // Add to back
dq.pop_front();                        // Remove from front
dq.pop_back();                         // Remove from back
 
// Random access like vector
int elem = dq[0];                      // O(1) access
dq.insert(dq.begin() + 2, 99);        // O(n) insertion in middle

STL Algorithms

Sorting and Searching

vector<int> nums = {3, 1, 4, 1, 5, 9};
 
// Sorting - O(n log n)
sort(nums.begin(), nums.end());                    // Ascending
sort(nums.begin(), nums.end(), greater<int>());    // Descending
sort(nums.begin(), nums.end(), [](int a, int b) { // Custom comparator
    return a % 10 < b % 10;  // Sort by last digit
});
 
// Stable sort - maintains relative order of equal elements
stable_sort(nums.begin(), nums.end());
 
// Partial sort - only first k elements are sorted
partial_sort(nums.begin(), nums.begin() + 3, nums.end());
 
// Binary search - O(log n), requires sorted array
bool found = binary_search(nums.begin(), nums.end(), 5);
 
// Lower/Upper bound - O(log n)
auto lower = lower_bound(nums.begin(), nums.end(), 3); // First element >= 3
auto upper = upper_bound(nums.begin(), nums.end(), 3); // First element > 3
int pos = lower - nums.begin();                        // Position of lower bound
 
// Equal range - returns pair of lower_bound and upper_bound
auto [first, last] = equal_range(nums.begin(), nums.end(), 3);

Finding and Counting

vector<int> nums = {1, 2, 3, 4, 5, 3, 6};
 
// Find - O(n)
auto it = find(nums.begin(), nums.end(), 3);       // First occurrence
if (it != nums.end()) {
    int pos = it - nums.begin();  // Position found
}
 
// Find with condition - O(n)
auto it2 = find_if(nums.begin(), nums.end(), [](int x) {
    return x > 4;  // First element > 4
});
 
// Count - O(n)
int count_3 = count(nums.begin(), nums.end(), 3);  // Count of 3s
int count_gt4 = count_if(nums.begin(), nums.end(), [](int x) {
    return x > 4;  // Count elements > 4
});
 
// Min/Max elements - O(n)
auto min_it = min_element(nums.begin(), nums.end());
auto max_it = max_element(nums.begin(), nums.end());
auto [min_it2, max_it2] = minmax_element(nums.begin(), nums.end());
 
// Check if sorted
bool is_sorted_asc = is_sorted(nums.begin(), nums.end());

Modifying Algorithms

vector<int> nums = {1, 2, 3, 4, 5};
vector<int> dest(5);
 
// Copy - O(n)
copy(nums.begin(), nums.end(), dest.begin());
 
// Transform - apply function to each element O(n)
transform(nums.begin(), nums.end(), nums.begin(), [](int x) {
    return x * x;  // Square each element
});
 
// Transform two ranges
vector<int> other = {1, 1, 1, 1, 1};
transform(nums.begin(), nums.end(), other.begin(), nums.begin(), 
          [](int a, int b) { return a + b; });
 
// Fill - O(n)
fill(nums.begin(), nums.end(), 42);           // Fill with value
fill_n(nums.begin(), 3, 99);                 // Fill first 3 elements
 
// Generate - O(n)
int counter = 0;
generate(nums.begin(), nums.end(), [&counter]() {
    return counter++;  // Fill with 0, 1, 2, ...
});
 
// Replace - O(n)
replace(nums.begin(), nums.end(), 2, 99);    // Replace all 2s with 99
replace_if(nums.begin(), nums.end(), [](int x) {
    return x > 5;  // Replace elements > 5 with 0
}, 0);
 
// Remove - O(n), doesn't actually remove, returns new end
auto new_end = remove(nums.begin(), nums.end(), 3);
nums.erase(new_end, nums.end());             // Actually remove
 
// Remove with condition
auto new_end2 = remove_if(nums.begin(), nums.end(), [](int x) {
    return x % 2 == 0;  // Remove even numbers
});
nums.erase(new_end2, nums.end());
 
// Unique - remove consecutive duplicates O(n)
sort(nums.begin(), nums.end());              // Usually sort first
auto unique_end = unique(nums.begin(), nums.end());
nums.erase(unique_end, nums.end());
 
// Reverse - O(n)
reverse(nums.begin(), nums.end());
 
// Rotate - O(n)
rotate(nums.begin(), nums.begin() + 2, nums.end()); // Rotate left by 2

Permutations

vector<int> nums = {1, 2, 3};
 
// Next/Previous permutation - O(n)
do {
    // Process current permutation
    for (int x : nums) cout << x << " ";
    cout << "\n";
} while (next_permutation(nums.begin(), nums.end()));
 
// Check if permutation
vector<int> other = {3, 1, 2};
bool is_perm = is_permutation(nums.begin(), nums.end(), other.begin());

Set Operations (on Sorted ranges)

vector<int> v1 = {1, 2, 3, 5, 6};
vector<int> v2 = {3, 4, 5, 7};
vector<int> result;
 
// Union - O(n + m)
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), 
          back_inserter(result));
 
// Intersection - O(n + m)
result.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                back_inserter(result));
 
// Difference - elements in first but not second
result.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
              back_inserter(result));
 
// Symmetric difference - elements in either but not both
result.clear();
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
                        back_inserter(result));
 
// Includes - check if second is subset of first
bool is_subset = includes(v1.begin(), v1.end(), v2.begin(), v2.end());

Numeric Algorithms

#include <numeric>
 
vector<int> nums = {1, 2, 3, 4, 5};
 
// Accumulate - sum/product - O(n)
int sum = accumulate(nums.begin(), nums.end(), 0);
int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
 
// Inner product - dot product of two vectors
vector<int> other = {2, 3, 4, 5, 6};
int dot_product = inner_product(nums.begin(), nums.end(), other.begin(), 0);
 
// Partial sum - running sum
vector<int> prefix_sums(nums.size());
partial_sum(nums.begin(), nums.end(), prefix_sums.begin());
 
// Adjacent difference
vector<int> differences(nums.size());
adjacent_difference(nums.begin(), nums.end(), differences.begin());
 
// Iota - fill with consecutive values
vector<int> sequence(10);
iota(sequence.begin(), sequence.end(), 1); // Fill with 1, 2, 3, ...
 
// GCD and LCM (C++17)
int gcd_val = gcd(12, 18);    // Returns 6
int lcm_val = lcm(12, 18);    // Returns 36

String Manipulation

String Operations

string s = "Hello World Programming";
 
// Character operations
bool is_alpha = isalpha(s[0]);         // Check if alphabetic
bool is_digit = isdigit('5');          // Check if digit  
bool is_lower = islower(s[0]);         // Check if lowercase
char upper_c = toupper(s[0]);          // Convert to uppercase
char lower_c = tolower(s[0]);          // Convert to lowercase
 
// String searching - O(n*m) naive, but optimized in practice
size_t pos = s.find("World");          // Find substring
size_t pos2 = s.find("World", 5);      // Find starting from position 5
size_t last_pos = s.rfind("o");        // Find last occurrence
 
// Multiple character search
size_t pos3 = s.find_first_of("aeiou"); // First vowel
size_t pos4 = s.find_last_of("aeiou");  // Last vowel
size_t pos5 = s.find_first_not_of(" "); // First non-space
 
// String replacement
s.replace(6, 5, "C++");               // Replace "World" with "C++"
// Result: "Hello C++ Programming"
 
// String insertion and deletion
s.insert(5, " Amazing");              // Insert at position 5
s.erase(5, 8);                       // Erase 8 characters from position 5

String Parsing and Tokenization

#include <sstream>
 
// Split string by delimiter
vector<string> split(const string& str, char delimiter) {
    vector<string> tokens;
    stringstream ss(str);
    string token;
    
    while (getline(ss, token, delimiter)) {
        if (!token.empty()) {
            tokens.push_back(token);
        }
    }
    return tokens;
}
 
// Example usage
string text = "apple,banana,cherry";
vector<string> fruits = split(text, ',');
 
// Using stringstream for parsing
string data = "123 456 789";
stringstream ss(data);
int num;
vector<int> numbers;
while (ss >> num) {
    numbers.push_back(num);
}
 
// Join strings
string join(const vector<string>& strings, const string& delimiter) {
    if (strings.empty()) return "";
    
    string result = strings[0];
    for (int i = 1; i < strings.size(); ++i) {
        result += delimiter + strings[i];
    }
    return result;
}

String Transformations

string text = "Hello World";
 
// Convert to lowercase/uppercase
transform(text.begin(), text.end(), text.begin(), ::tolower);
// Result: "hello world"
 
transform(text.begin(), text.end(), text.begin(), ::toupper);
// Result: "HELLO WORLD"
 
// Reverse string
reverse(text.begin(), text.end());
 
// Remove spaces
text.erase(remove(text.begin(), text.end(), ' '), text.end());
 
// Count characters
map<char, int> char_count;
for (char c : text) {
    char_count[c]++;
}
 
// Check if palindrome
bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}
 
// Alternative using STL
bool isPalindrome2(string s) {
    string reversed = s;
    reverse(reversed.begin(), reversed.end());
    return s == reversed;
}

Regular Expressions (C++11)

#include <regex>
 
string text = "The phone numbers are 123-456-7890 and 987-654-3210";
 
// Pattern matching
regex phone_pattern(R"(\d{3}-\d{3}-\d{4})");
smatch matches;
 
// Find first match
if (regex_search(text, matches, phone_pattern)) {
    cout << "Found: " << matches[0] << "\n";
}
 
// Find all matches
sregex_iterator iter(text.begin(), text.end(), phone_pattern);
sregex_iterator end;
for (; iter != end; ++iter) {
    cout << "Match: " << iter->str() << "\n";
}
 
// Replace using regex
string result = regex_replace(text, phone_pattern, "XXX-XXX-XXXX");
 
// Validate email pattern
bool isValidEmail(const string& email) {
    regex email_pattern(R"([a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,})");
    return regex_match(email, email_pattern);
}

Pointers & Memory Management

Pointers Basics

int num = 42;
int* ptr = &num;           // Pointer to num
int value = *ptr;          // Dereference pointer
*ptr = 100;               // Modify value through pointer
 
// Null pointer
int* null_ptr = nullptr;   // C++11 way (preferred)
int* old_null = NULL;      // C-style way
 
// Pointer arithmetic
int arr[] = {1, 2, 3, 4, 5};
int* p = arr;             // Points to first element
p++;                      // Points to second element
int diff = p - arr;       // Difference in elements (1)

Dynamic Memory Allocation

// Raw pointers (avoid in modern C++)
int* raw_ptr = new int(42);          // Single integer
int* raw_array = new int[100];       // Array
delete raw_ptr;                      // Don't forget to delete!
delete[] raw_array;                  // Use delete[] for arrays
 
// Smart pointers (C++11) - automatic memory management
#include <memory>
 
// unique_ptr - exclusive ownership
unique_ptr<int> unique_p = make_unique<int>(42);
unique_ptr<int[]> unique_arr = make_unique<int[]>(100);
 
// Move ownership (cannot copy)
unique_ptr<int> another_p = move(unique_p); // unique_p becomes null
 
// shared_ptr - shared ownership with reference counting
shared_ptr<int> shared_p = make_shared<int>(42);
shared_ptr<int> another_shared = shared_p;    // Both point to same object
int ref_count = shared_p.use_count();         // Returns 2
 
// weak_ptr - non-owning observer
weak_ptr<int> weak_p = shared_p;
if (auto locked = weak_p.lock()) {            // Convert to shared_ptr safely
    cout << *locked << "\n";
}

References

int num = 42;
int& ref = num;           // Reference must be initialized
ref = 100;               // Changes num to 100
 
// References vs pointers
// - References cannot be null
// - References cannot be reassigned
// - References don't need dereferencing
// - References have no arithmetic operations
 
// Function parameters
void modifyValue(int& val) {       // Pass by reference
    val *= 2;
}
 
void readOnlyAccess(const int& val) { // Const reference
    // val *= 2;  // Error: cannot modify
}
 
// Return references (be careful with local variables)
int& getElement(vector<int>& vec, int index) {
    return vec[index];            // Safe: vector exists after return
}

Memory Management Best Practices

class Resource {
private:
    int* data;
    size_t size;
 
public:
    // Constructor
    Resource(size_t n) : size(n), data(new int[n]) {}
    
    // Destructor
    ~Resource() {
        delete[] data;
    }
    
    // Copy constructor
    Resource(const Resource& other) : size(other.size), data(new int[size]) {
        copy(other.data, other.data + size, data);
    }
    
    // Copy assignment operator
    Resource& operator=(const Resource& other) {
        if (this != &other) {
            delete[] data;
            size = other.size;
            data = new int[size];
            copy(other.data, other.data + size, data);
        }
        return *this;
    }
    
    // Move constructor (C++11)
    Resource(Resource&& other) noexcept : size(other.size), data(other.data) {
        other.size = 0;
        other.data = nullptr;
    }
    
    // Move assignment operator (C++11)
    Resource& operator=(Resource&& other) noexcept {
        if (this != &other) {
            delete[] data;
            size = other.size;
            data = other.data;
            other.size = 0;
            other.data = nullptr;
        }
        return *this;
    }
};

Trees & Graphs

Binary Tree Node Structure

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

Tree Traversals

// Recursive traversals
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;
    inorderTraversal(root->left, result);   // Left
    result.push_back(root->val);            // Root
    inorderTraversal(root->right, result);  // Right
}
 
void preorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;
    result.push_back(root->val);            // Root
    preorderTraversal(root->left, result);  // Left
    preorderTraversal(root->right, result); // Right
}
 
void postorderTraversal(TreeNode* root, vector<int>& result) {
    if (!root) return;
    postorderTraversal(root->left, result);  // Left
    postorderTraversal(root->right, result); // Right
    result.push_back(root->val);             // Root
}
 
// Iterative inorder traversal
vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* current = root;
    
    while (current || !st.empty()) {
        while (current) {
            st.push(current);
            current = current->left;
        }
        current = st.top();
        st.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}
 
// Level order traversal (BFS)
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    
    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(currentLevel);
    }
    return result;
}

Tree Properties and Algorithms

// Tree height/depth
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
 
// Check if balanced binary tree
bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> height = [&](TreeNode* node) -> int {
        if (!node) return 0;
        
        int left = height(node->left);
        if (left == -1) return -1;
        
        int right = height(node->right);
        if (right == -1) return -1;
        
        if (abs(left - right) > 1) return -1;
        return 1 + max(left, right);
    };
    
    return height(root) != -1;
}
 
// Lowest Common Ancestor in BST
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    
    if (p->val < root->val && q->val < root->val) {
        return lowestCommonAncestor(root->left, p, q);
    } else if (p->val > root->val && q->val > root->val) {
        return lowestCommonAncestor(root->right, p, q);
    } else {
        return root;
    }
}
 
// Binary Tree to Array (Serialize)
string serialize(TreeNode* root) {
    if (!root) return "null";
    return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}
 
// Array to Binary Tree (Deserialize)
TreeNode* deserialize(string data) {
    queue<string> tokens;
    stringstream ss(data);
    string token;
    
    while (getline(ss, token, ',')) {
        tokens.push(token);
    }
    
    function<TreeNode*()> build = [&]() -> TreeNode* {
        string val = tokens.front();
        tokens.pop();
        
        if (val == "null") return nullptr;
        
        TreeNode* node = new TreeNode(stoi(val));
        node->left = build();
        node->right = build();
        return node;
    };
    
    return build();
}

Graph Representations

// Adjacency List (most common)
class Graph {
public:
    int vertices;
    vector<vector<int>> adjList;
    
    Graph(int v) : vertices(v), adjList(v) {}
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);  // For undirected graph
    }
};
 
// Adjacency Matrix
class GraphMatrix {
public:
    int vertices;
    vector<vector<int>> adjMatrix;
    
    GraphMatrix(int v) : vertices(v), adjMatrix(v, vector<int>(v, 0)) {}
    
    void addEdge(int u, int v, int weight = 1) {
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight;  // For undirected graph
    }
};
 
// Edge List
struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

Graph Traversal Algorithms

// DFS (Depth First Search) - Recursive
void dfsRecursive(const Graph& g, int vertex, vector<bool>& visited) {
    visited[vertex] = true;
    cout << vertex << " ";
    
    for (int neighbor : g.adjList[vertex]) {
        if (!visited[neighbor]) {
            dfsRecursive(g, neighbor, visited);
        }
    }
}
 
// DFS - Iterative with Stack
void dfsIterative(const Graph& g, int start) {
    vector<bool> visited(g.vertices, false);
    stack<int> st;
    st.push(start);
    
    while (!st.empty()) {
        int vertex = st.top();
        st.pop();
        
        if (!visited[vertex]) {
            visited[vertex] = true;
            cout << vertex << " ";
            
            // Add neighbors in reverse order for consistent traversal
            for (int i = g.adjList[vertex].size() - 1; i >= 0; i--) {
                if (!visited[g.adjList[vertex][i]]) {
                    st.push(g.adjList[vertex][i]);
                }
            }
        }
    }
}
 
// BFS (Breadth First Search)
void bfs(const Graph& g, int start) {
    vector<bool> visited(g.vertices, false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << vertex << " ";
        
        for (int neighbor : g.adjList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
 
// Shortest path in unweighted graph (BFS)
vector<int> shortestPath(const Graph& g, int start, int end) {
    vector<int> parent(g.vertices, -1);
    vector<bool> visited(g.vertices, false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty() && !visited[end]) {
        int vertex = q.front();
        q.pop();
        
        for (int neighbor : g.adjList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = vertex;
                q.push(neighbor);
            }
        }
    }
    
    // Reconstruct path
    vector<int> path;
    if (!visited[end]) return path;  // No path exists
    
    int current = end;
    while (current != -1) {
        path.push_back(current);
        current = parent[current];
    }
    reverse(path.begin(), path.end());
    return path;
}

Advanced Graph Algorithms

// Topological Sort (for DAG - Directed Acyclic Graph)
vector<int> topologicalSort(const Graph& g) {
    vector<int> indegree(g.vertices, 0);
    
    // Calculate indegrees
    for (int i = 0; i < g.vertices; i++) {
        for (int neighbor : g.adjList[i]) {
            indegree[neighbor]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < g.vertices; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        result.push_back(vertex);
        
        for (int neighbor : g.adjList[vertex]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    return result;  // Empty if cycle exists
}
 
// Detect Cycle in Undirected Graph
bool hasCycleUndirected(const Graph& g) {
    vector<bool> visited(g.vertices, false);
    
    function<bool(int, int)> dfs = [&](int vertex, int parent) -> bool {
        visited[vertex] = true;
        
        for (int neighbor : g.adjList[vertex]) {
            if (neighbor != parent) {
                if (visited[neighbor] || dfs(neighbor, vertex)) {
                    return true;
                }
            }
        }
        return false;
    };
    
    for (int i = 0; i < g.vertices; i++) {
        if (!visited[i] && dfs(i, -1)) {
            return true;
        }
    }
    return false;
}
 
// Dijkstra's Algorithm - Shortest Path with Weights
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, weight] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

Dynamic Programming

1D DP Patterns

// Fibonacci Numbers - Basic DP
int fibonacci(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
 
// Space optimized Fibonacci
int fibonacciOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
 
// Climbing Stairs - Similar to Fibonacci
int climbStairs(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
 
// House Robber - Maximum sum with no adjacent elements
int rob(vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];
    
    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);
    
    for (int i = 2; i < nums.size(); i++) {
        int current = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
 
// Longest Increasing Subsequence - O(n²) DP
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return *max_element(dp.begin(), dp.end());
}
 
// LIS Optimized with Binary Search - O(n log n)
int lengthOfLISOptimized(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

2D DP Patterns

// Unique Paths in Grid
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}
 
// Space optimized version
int uniquePathsOptimized(int m, int n) {
    vector<int> dp(n, 1);
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j-1];
        }
    }
    
    return dp[n-1];
}
 
// Minimum Path Sum
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    
    dp[0][0] = grid[0][0];
    
    // Fill first row
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // Fill first column
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // Fill rest of the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    return dp[m-1][n-1];
}
 
// Edit Distance (Levenshtein Distance)
int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    // Initialize base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j],    // Delete
                                   dp[i][j-1],      // Insert
                                   dp[i-1][j-1]});  // Replace
            }
        }
    }
    
    return dp[m][n];
}
 
// Longest Common Subsequence
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

Knapsack Problems

// 0/1 Knapsack
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][capacity];
}
 
// Space optimized 0/1 Knapsack
int knapsack01Optimized(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    
    for (int i = 0; i < weights.size(); i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}
 
// Unbounded Knapsack
int knapsackUnbounded(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity + 1, 0);
    
    for (int w = 1; w <= capacity; w++) {
        for (int i = 0; i < weights.size(); i++) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }
    
    return dp[capacity];
}
 
// Coin Change - Minimum coins
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}
 
// Coin Change - Number of ways
int coinChangeWays(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}

DP on Strings

// Palindromic Substrings Count
int countSubstrings(string s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;
    
    // Single characters
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }
    
    // Two characters
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }
    
    // Three or more characters
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }
    
    return count;
}
 
// Longest Palindromic Subsequence
int longestPalindromeSubseq(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // Single characters
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // Build up from smaller to larger substrings
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}
 
// Word Break
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.length() + 1, false);
    dp[0] = true;
    
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[s.length()];
}

Memoization Template

// Generic memoization with unordered_map
class Solution {
private:
    unordered_map<string, int> memo;
    
    string encodeState(int param1, int param2) {
        return to_string(param1) + "," + to_string(param2);
    }
    
public:
    int solve(int param1, int param2) {
        string key = encodeState(param1, param2);
        
        if (memo.count(key)) {
            return memo[key];
        }
        
        // Base cases
        if (/* base condition */) {
            return memo[key] = /* base value */;
        }
        
        // Recursive cases
        int result = 0;
        // ... compute result using recursive calls
        
        return memo[key] = result;
    }
};
 
// Using function<> with lambda for local memoization
int solveWithLambda(/* parameters */) {
    map<pair<int, int>, int> memo;
    
    function<int(int, int)> dp = [&](int x, int y) -> int {
        if (memo.count({x, y})) return memo[{x, y}];
        
        // Base cases and recursive logic
        int result = /* computation */;
        
        return memo[{x, y}] = result;
    };
    
    return dp(/* initial parameters */);
}

Sorting & Searching

Custom Sorting

vector<int> nums = {3, 1, 4, 1, 5, 9};
 
// Sort with custom comparator
sort(nums.begin(), nums.end(), [](int a, int b) {
    return a > b;  // Descending order
});
 
// Sort pairs by second element, then first
vector<pair<int, int>> pairs = {{1, 3}, {2, 1}, {1, 2}};
sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
});
 
// Sort strings by length, then lexicographically
vector<string> words = {"apple", "pie", "banana", "a"};
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.length() != b.length()) return a.length() < b.length();
    return a < b;
});
 
// Sort with multiple criteria using tuple comparison
struct Person {
    string name;
    int age;
    double score;
};
 
vector<Person> people;
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return make_tuple(a.age, -a.score, a.name) < 
           make_tuple(b.age, -b.score, b.name);  // Age asc, score desc, name asc
});

Binary Search Variations

// Basic binary search
bool binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow
        
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return false;
}
 
// Find first occurrence (leftmost)
int findFirst(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}
 
// Find last occurrence (rightmost)
int findLast(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;   // Continue searching right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}
 
// Search in rotated sorted array
int searchRotated(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        
        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}
 
// Find peak element (element greater than both neighbors)
int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;   // Peak is on the right
        } else {
            right = mid;      // Peak is on the left or at mid
        }
    }
    
    return left;
}
 
// Search for minimum in rotated sorted array
int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] > nums[right]) {
            left = mid + 1;   // Minimum is in right half
        } else {
            right = mid;      // Minimum is in left half or at mid
        }
    }
    
    return nums[left];
}

Advanced Searching Techniques

// Ternary search for finding maximum/minimum of unimodal function
double ternarySearch(double left, double right, function<double(double)> f) {
    const double EPS = 1e-9;
    
    while (right - left > EPS) {
        double mid1 = left + (right - left) / 3;
        double mid2 = right - (right - left) / 3;
        
        if (f(mid1) < f(mid2)) {
            left = mid1;      // Maximum is in [mid1, right]
        } else {
            right = mid2;     // Maximum is in [left, mid2]
        }
    }
    
    return (left + right) / 2;
}
 
// Binary search on answer (BSOA)
// Example: Find minimum capacity to ship packages within D days
int shipWithinDays(vector<int>& weights, int D) {
    int left = *max_element(weights.begin(), weights.end());
    int right = accumulate(weights.begin(), weights.end(), 0);
    
    auto canShip = [&](int capacity) -> bool {
        int days = 1, currentWeight = 0;
        
        for (int weight : weights) {
            if (currentWeight + weight > capacity) {
                days++;
                currentWeight = weight;
            } else {
                currentWeight += weight;
            }
        }
        
        return days <= D;
    };
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (canShip(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}
 
// K-th smallest element using quickselect (average O(n))
int quickSelect(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int pivot = partition(nums, left, right);
        
        if (pivot == k - 1) {
            return nums[pivot];
        } else if (pivot < k - 1) {
            left = pivot + 1;
        } else {
            right = pivot - 1;
        }
    }
    
    return -1;  // Should never reach here
}
 
int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    
    swap(nums[i], nums[right]);
    return i;
}

Sorting Algorithms Implementation

// Quick Sort
void quickSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int pi = partition(nums, low, high);
        quickSort(nums, low, pi - 1);
        quickSort(nums, pi + 1, high);
    }
}
 
// Merge Sort
void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}
 
void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    for (i = left, k = 0; i <= right; i++, k++) {
        nums[i] = temp[k];
    }
}
 
// Heap Sort
void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}
 
void heapSort(vector<int>& nums) {
    int n = nums.size();
    
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    
    // Extract elements from heap
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}
 
// Counting Sort (for integers in range)
void countingSort(vector<int>& nums, int maxVal) {
    vector<int> count(maxVal + 1, 0);
    
    // Count occurrences
    for (int num : nums) {
        count[num]++;
    }
    
    // Reconstruct array
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) {
            nums[index++] = i;
        }
    }
}
 
// Radix Sort
void radixSort(vector<int>& nums) {
    int maxVal = *max_element(nums.begin(), nums.end());
    
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(nums, exp);
    }
}
 
void countingSortByDigit(vector<int>& nums, int exp) {
    vector<int> output(nums.size());
    vector<int> count(10, 0);
    
    // Count occurrences of digits
    for (int num : nums) {
        count[(num / exp) % 10]++;
    }
    
    // Cumulative count
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // Build output array
    for (int i = nums.size() - 1; i >= 0; i--) {
        output[count[(nums[i] / exp) % 10] - 1] = nums[i];
        count[(nums[i] / exp) % 10]--;
    }
    
    nums = output;
}

Mathematical Algorithms

Number Theory

// GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
 
// LCM using GCD
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;  // Avoid overflow
}
 
// Extended Euclidean Algorithm - find x, y such that ax + by = gcd(a, b)
int extendedGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int gcd_val = extendedGCD(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd_val;
}
 
// Fast exponentiation - O(log n)
long long fastPower(long long base, long long exp, long long mod = LLONG_MAX) {
    long long result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    
    return result;
}
 
// Modular multiplicative inverse
long long modInverse(long long a, long long mod) {
    return fastPower(a, mod - 2, mod);  // When mod is prime
}
 
// Sieve of Eratosthenes - find all primes up to n
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime;
}
 
// Prime factorization
vector<pair<int, int>> primeFactors(int n) {
    vector<pair<int, int>> factors;
    
    for (int i = 2; i * i <= n; i++) {
        int count = 0;
        while (n % i == 0) {
            n /= i;
            count++;
        }
        if (count > 0) {
            factors.push_back({i, count});
        }
    }
    
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}
 
// Check if number is prime
bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    
    return true;
}

Bit Manipulation

// Basic bit operations
int setBit(int num, int pos) {
    return num | (1 << pos);
}
 
int clearBit(int num, int pos) {
    return num & ~(1 << pos);
}
 
int toggleBit(int num, int pos) {
    return num ^ (1 << pos);
}
 
bool checkBit(int num, int pos) {
    return (num & (1 << pos)) != 0;
}
 
// Count set bits (Brian Kernighan's algorithm)
int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Clear the lowest set bit
        count++;
    }
    return count;
}
 
// Alternative using built-in function
int countSetBitsBuiltin(int n) {
    return __builtin_popcount(n);  // For unsigned int
    // __builtin_popcountl for long
    // __builtin_popcountll for long long
}
 
// Check if power of 2
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
 
// Find the only non-duplicate number (XOR trick)
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}
 
// Find two non-duplicate numbers
vector<int> singleNumbers(vector<int>& nums) {
    int xor_result = 0;
    for (int num : nums) {
        xor_result ^= num;
    }
    
    // Find rightmost set bit
    int rightmost_bit = xor_result & (-xor_result);
    
    int num1 = 0, num2 = 0;
    for (int num : nums) {
        if (num & rightmost_bit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    
    return {num1, num2};
}
 
// Generate all subsets using bit manipulation
vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }
        result.push_back(subset);
    }
    
    return result;
}
 
// Reverse bits
unsigned int reverseBits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

Combinatorics

// Factorial with memoization
vector<long long> fact;
 
void precomputeFactorials(int n) {
    fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
    }
}
 
// Combination C(n, r) = n! / (r! * (n-r)!)
long long combination(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    
    return fact[n] / (fact[r] * fact[n - r]);
}
 
// Combination with modular arithmetic
long long combinationMod(int n, int r, int mod) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    
    long long numerator = fact[n] % mod;
    long long denominator = (fact[r] * fact[n - r]) % mod;
    
    return (numerator * modInverse(denominator, mod)) % mod;
}
 
// Pascal's Triangle for combinations
vector<vector<long long>> pascalTriangle(int n) {
    vector<vector<long long>> triangle(n + 1);
    
    for (int i = 0; i <= n; i++) {
        triangle[i].resize(i + 1);
        triangle[i][0] = triangle[i][i] = 1;
        
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    return triangle;
}
 
// Catalan numbers - C(n) = (2n)! / ((n+1)! * n!)
long long catalan(int n) {
    if (n <= 1) return 1;
    
    vector<long long> dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    
    return dp[n];
}
 
// Derangements - permutations where no element is in its original position
long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    if (n == 2) return 1;
    
    vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 1;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
    }
    
    return dp[n];
}

Geometry (Basic)

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(double t) const { return Point(x * t, y * t); }
    
    double dot(const Point& p) const { return x * p.x + y * p.y; }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
    double length() const { return sqrt(x * x + y * y); }
    double length2() const { return x * x + y * y; }  // Squared length
};
 
// Distance between two points
double distance(const Point& a, const Point& b) {
    return (a - b).length();
}
 
// Area of triangle using cross product
double triangleArea(const Point& a, const Point& b, const Point& c) {
    return abs((b - a).cross(c - a)) / 2.0;
}
 
// Check if point is on line segment
bool pointOnSegment(const Point& p, const Point& a, const Point& b) {
    return abs((p - a).cross(b - a)) < 1e-9 && 
           (p - a).dot(p - b) <= 1e-9;
}
 
// Line intersection
bool lineIntersection(const Point& a1, const Point& a2, 
                     const Point& b1, const Point& b2, Point& intersection) {
    Point da = a2 - a1;
    Point db = b2 - b1;
    Point dc = b1 - a1;
    
    double cross_product = da.cross(db);
    if (abs(cross_product) < 1e-9) return false;  // Parallel lines
    
    double t = dc.cross(db) / cross_product;
    intersection = a1 + da * t;
    return true;
}
 
// Convex hull using Graham scan
vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // Find bottom-most point (and leftmost in case of tie)
    int minIdx = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[minIdx].y || 
           (points[i].y == points[minIdx].y && points[i].x < points[minIdx].x)) {
            minIdx = i;
        }
    }
    swap(points[0], points[minIdx]);
    
    // Sort by polar angle
    Point pivot = points[0];
    sort(points.begin() + 1, points.end(), [&](const Point& a, const Point& b) {
        double cross = (a - pivot).cross(b - pivot);
        if (abs(cross) < 1e-9) {
            return (a - pivot).length2() < (b - pivot).length2();
        }
        return cross > 0;
    });
    
    // Build convex hull
    vector<Point> hull;
    for (const Point& p : points) {
        while (hull.size() >= 2 && 
               (hull[hull.size()-1] - hull[hull.size()-2]).cross(p - hull[hull.size()-2]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }
    
    return hull;
}

Advanced Patterns

Union-Find (Disjoint Set Union)

class UnionFind {
private:
    vector<int> parent, rank;
    int components;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        
        components--;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    int getComponents() const {
        return components;
    }
};
 
// Example: Number of islands
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int m = grid.size(), n = grid[0].size();
    UnionFind uf(m * n);
    int islands = 0;
    
    auto getId = [&](int i, int j) { return i * n + j; };
    
    // Count initial islands
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') islands++;
        }
    }
    uf.components = islands;
    
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                for (auto [di, dj] : directions) {
                    int ni = i + di, nj = j + dj;
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1') {
                        uf.unite(getId(i, j), getId(ni, nj));
                    }
                }
            }
        }
    }
    
    return uf.getComponents();
}

Trie (Prefix Tree)

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() : isEndOfWord(false) {}
};
 
class Trie {
private:
    TrieNode* root;
    
public:
    Trie() : root(new TrieNode()) {}
    
    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }
    
    bool search(const string& word) {
        TrieNode* node = findNode(word);
        return node && node->isEndOfWord;
    }
    
    bool startsWith(const string& prefix) {
        return findNode(prefix) != nullptr;
    }
    
    vector<string> getAllWordsWithPrefix(const string& prefix) {
        vector<string> result;
        TrieNode* node = findNode(prefix);
        if (!node) return result;
        
        dfs(node, prefix, result);
        return result;
    }
    
private:
    TrieNode* findNode(const string& prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
    
    void dfs(TrieNode* node, const string& current, vector<string>& result) {
        if (node->isEndOfWord) {
            result.push_back(current);
        }
        
        for (auto& [ch, child] : node->children) {
            dfs(child, current + ch, result);
        }
    }
};
 
// Word search in grid using Trie
class WordSearchTrie {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // Build Trie
        Trie trie;
        for (const string& word : words) {
            trie.insert(word);
        }
        
        vector<string> result;
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, trie.root, "", result);
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, 
             string word, vector<string>& result) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
            board[i][j] == '#' || node->children.find(board[i][j]) == node->children.end()) {
            return;
        }
        
        char ch = board[i][j];
        word += ch;
        node = node->children[ch];
        
        if (node->isEndOfWord) {
            result.push_back(word);
            node->isEndOfWord = false;  // Avoid duplicates
        }
        
        board[i][j] = '#';  // Mark as visited
        
        dfs(board, i+1, j, node, word, result);
        dfs(board, i-1, j, node, word, result);
        dfs(board, i, j+1, node, word, result);
        dfs(board, i, j-1, node, word, result);
        
        board[i][j] = ch;   // Restore
    }
};

Segment Tree

class SegmentTree {
private:
    vector<int> tree;
    int n;
    
    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    void updateHelper(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                updateHelper(2*node, start, mid, idx, val);
            } else {
                updateHelper(2*node+1, mid+1, end, idx, val);
            }
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    int queryHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;  // Out of range
        }
        if (l <= start && end <= r) {
            return tree[node];  // Complete overlap
        }
        // Partial overlap
        int mid = (start + end) / 2;
        return queryHelper(2*node, start, mid, l, r) + 
               queryHelper(2*node+1, mid+1, end, l, r);
    }
    
public:
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }
    
    void update(int idx, int val) {
        updateHelper(1, 0, n - 1, idx, val);
    }
    
    int query(int l, int r) {
        return queryHelper(1, 0, n - 1, l, r);
    }
};
 
// Range Maximum Query
class SegmentTreeMax {
private:
    vector<int> tree;
    int n;
    
public:
    SegmentTreeMax(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }
    
    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = max(tree[2*node], tree[2*node+1]);
        }
    }
    
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return INT_MIN;
        if (l <= start && end <= r) return tree[node];
        
        int mid = (start + end) / 2;
        return max(query(2*node, start, mid, l, r),
                  query(2*node+1, mid+1, end, l, r));
    }
    
    int queryMax(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

Fenwick Tree (Binary Indexed Tree)

class FenwickTree {
private:
    vector<int> tree;
    int n;
    
public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}
    
    FenwickTree(const vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
        for (int i = 0; i < n; i++) {
            update(i, arr[i]);
        }
    }
    
    void update(int idx, int delta) {
        for (++idx; idx <= n; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }
    
    int query(int idx) {  // Sum from 0 to idx
        int sum = 0;
        for (++idx; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
    
    int rangeQuery(int l, int r) {  // Sum from l to r
        return query(r) - (l > 0 ? query(l - 1) : 0);
    }
};
 
// 2D Fenwick Tree
class FenwickTree2D {
private:
    vector<vector<int>> tree;
    int m, n;
    
public:
    FenwickTree2D(int rows, int cols) : m(rows), n(cols), 
                                        tree(rows + 1, vector<int>(cols + 1, 0)) {}
    
    void update(int row, int col, int delta) {
        for (int i = row + 1; i <= m; i += i & -i) {
            for (int j = col + 1; j <= n; j += j & -j) {
                tree[i][j] += delta;
            }
        }
    }
    
    int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= i & -i) {
            for (int j = col + 1; j > 0; j -= j & -j) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    int rangeQuery(int row1, int col1, int row2, int col2) {
        return query(row2, col2) - query(row1 - 1, col2) - 
               query(row2, col1 - 1) + query(row1 - 1, col1 - 1);
    }
};

Backtracking Patterns

// N-Queens Problem
class NQueens {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        vector<bool> cols(n, false), diag1(2*n-1, false), diag2(2*n-1, false);
        
        backtrack(0, n, board, cols, diag1, diag2, result);
        return result;
    }
    
private:
    void backtrack(int row, int n, vector<string>& board,
                  vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2,
                  vector<vector<string>>& result) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
                continue;
            }
            
            // Place queen
            board[row][col] = 'Q';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = true;
            
            backtrack(row + 1, n, board, cols, diag1, diag2, result);
            
            // Remove queen
            board[row][col] = '.';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
        }
    }
};
 
// Sudoku Solver
class SudokuSolver {
public:
    bool solveSudoku(vector<vector<char>>& board) {
        return backtrack(board);
    }
    
private:
    bool backtrack(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (backtrack(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check row
            if (board[row][i] == c) return false;
            // Check column
            if (board[i][col] == c) return false;
            // Check 3x3 box
            if (board[3*(row/3) + i/3][3*(col/3) + i%3] == c) return false;
        }
        return true;
    }
};
 
// Generate Parentheses
vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    backtrack(current, 0, 0, n, result);
    return result;
}
 
void backtrack(string& current, int open, int close, int n, vector<string>& result) {
    if (current.length() == 2 * n) {
        result.push_back(current);
        return;
    }
    
    if (open < n) {
        current += '(';
        backtrack(current, open + 1, close, n, result);
        current.pop_back();
    }
    
    if (close < open) {
        current += ')';
        backtrack(current, open, close + 1, n, result);
        current.pop_back();
    }
}

Interview Tips

Common Pitfalls and Solutions

/*
1. Integer Overflow:
   - Use long long for large numbers
   - Check for overflow: if (a > INT_MAX - b) // overflow will occur
   - Use modular arithmetic when specified
*/
int multiply(int a, int b) {
    return (long long)a * b % MOD;  // Safe multiplication
}
 
/*
2. Array Index Out of Bounds:
   - Always check bounds: if (i >= 0 && i < n)
   - Use size_t for array indices to avoid negative values
   - Be careful with unsigned arithmetic
*/
bool isValidIndex(const vector<int>& arr, int i) {
    return i >= 0 && i < static_cast<int>(arr.size());
}
 
/*
3. Null Pointer Dereference:
   - Always check: if (ptr != nullptr)
   - Use smart pointers when possible
   - Initialize pointers: TreeNode* node = nullptr;
*/
 
/*
4. Infinite Loops:
   - Ensure loop variables are updated
   - Have clear termination conditions
   - Use debugger or print statements to trace
*/
 
/*
5. Memory Management:
   - Prefer STL containers over raw arrays
   - Use smart pointers for dynamic allocation
   - Be careful with references to local variables
*/
 
/*
6. Floating Point Precision:
   - Use epsilon for comparisons: abs(a - b) < 1e-9
   - Be careful with == for doubles
   - Consider using integers when possible
*/
bool doubleEqual(double a, double b) {
    return abs(a - b) < 1e-9;
}

Optimization Techniques

/*
1. Early Termination:
   - Return immediately when result is found
   - Use break/continue appropriately
*/
 
/*
2. Space-Time Tradeoffs:
   - Memoization: Trade space for time
   - Precomputation: Calculate once, use many times
   - Hash tables: Fast lookup at cost of space
*/
 
/*
3. Bit Manipulation Tricks:
   - x & (x-1): Remove lowest set bit
   - x & -x: Get lowest set bit
   - x ^ x: Always 0 (useful for finding unique elements)
   - x << 1: Multiply by 2
   - x >> 1: Divide by 2
*/
 
/*
4. Mathematical Optimizations:
   - Use mathematical formulas instead of loops
   - Leverage symmetry and patterns
   - Consider modular arithmetic properties
*/
 
/*
5. Algorithm Selection:
   - Choose appropriate sorting algorithm
   - Use appropriate data structure for the problem
   - Consider approximation algorithms for NP-hard problems
*/
 
/*
6. Compiler Optimizations:
   - Use const and references where appropriate
   - Prefer pre-increment (++i) over post-increment (i++)
   - Use reserve() for vectors when size is known
   - Enable compiler optimizations (-O2, -O3)
*/

Avi's Notes

Explorer

CPP Coding Interview Cheat-sheet

Table of Contents

Basic Syntax & Patterns

Essential Headers & Namespace

Input/Output Optimization

Common Data Types & Limits

Lambda Functions

Range-based For Loops

Commonly Used Macros

STL Containers

Vector (Dynamic Array)

String

Pair and Tuple

Map (Ordered Key-Value Store)

Unordered Map (Hash Table)

Set (Ordered Unique Elements)

Unordered Set (Hash Set)

Multi-containers (Allow Duplicates)

Queue and Stack

Deque (Double-Ended Queue)

STL Algorithms

Sorting and Searching

Finding and Counting

Modifying Algorithms

Permutations

Set Operations (on Sorted ranges)

Numeric Algorithms

String Manipulation

String Operations

String Parsing and Tokenization

String Transformations

Regular Expressions (C++11)

Pointers & Memory Management

Pointers Basics

Dynamic Memory Allocation

References

Memory Management Best Practices

Trees & Graphs

Binary Tree Node Structure

Tree Traversals

Tree Properties and Algorithms

Graph Representations

Graph Traversal Algorithms

Advanced Graph Algorithms

Dynamic Programming

1D DP Patterns

2D DP Patterns

Knapsack Problems

DP on Strings

Memoization Template

Sorting & Searching

Custom Sorting

Binary Search Variations

Advanced Searching Techniques

Sorting Algorithms Implementation

Mathematical Algorithms

Number Theory

Bit Manipulation

Combinatorics

Geometry (Basic)

Advanced Patterns

Union-Find (Disjoint Set Union)

Trie (Prefix Tree)

Segment Tree

Fenwick Tree (Binary Indexed Tree)

Backtracking Patterns

Interview Tips

Common Pitfalls and Solutions

Optimization Techniques

Graph View

Table of Contents