{"title":"C++ Crash Course for DSA","description":"","content":"This chapter is a focused crash course on C++ features that come up repeatedly in DSA and coding interviews. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.\n\n---\n\n# Common Includes\n\nOn LeetCode, most headers are included automatically. But when writing C++ locally or on some interview platforms, you need to know what to include. Here are the headers that cover 95% of DSA problems:\n\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n#include \n#include // queue and priority_queue\n#include \n#include \n#include // sort, lower_bound, reverse, etc.\n#include // INT_MAX, INT_MIN, LLONG_MAX\n#include // accumulate, iota, gcd\n#include // greater<>, function<>\n#include // stringstream for parsing\n#include // sqrt, abs, pow, ceil, floor\n\nusing namespace std; // acceptable in interviews, not in production\n```\n\n\nEach header serves a specific purpose in DSA:\n\n\n| Header | What It Provides | DSA Use Case |\n|--------|-----------------|--------------|\n| `` | `vector` | Dynamic arrays, adjacency lists, DP tables |\n| `` | `string` | String manipulation, character operations |\n| `` | `unordered_map` | Frequency counting, Two Sum, O(1) lookups |\n| `` | `unordered_set` | Visited tracking, duplicate detection |\n| `` / `` | `map`, `set` | Sorted access, range queries |\n| `` | `queue`, `priority_queue` | BFS, heaps, Dijkstra |\n| `` | `stack` | Monotonic stack, iterative DFS |\n| `` | `deque` | Sliding window, double-ended operations |\n| `` | `sort`, `lower_bound`, `reverse`, etc. | Sorting, binary search, STL algorithms |\n| `` | `INT_MAX`, `INT_MIN`, `LLONG_MAX` | Sentinel values, overflow boundaries |\n| `` | `accumulate`, `iota`, `gcd` | Prefix sums, number theory |\n| `` | `greater<>`, `function<>` | Min-heap comparator, recursive lambdas |\n| `` | `stringstream` | String tokenization, parsing |\n| `` | `sqrt`, `ceil`, `floor`, `abs` | Math operations |\n\n\nA note on `using namespace std;`. In production code, this is considered bad practice because it pollutes the global namespace. In coding interviews and competitive programming, it is universally accepted and saves you from typing `std::` before every STL type. Use it in interviews without hesitation.\n\n---\n\n# Variables, Types, and the Overflow Trap\n\nC++ is a statically typed language, meaning every variable must have a declared type. For DSA, a small set of types covers most problems.\n\n\n| Type | Size | Range | DSA Use Case |\n|------|------|-------|--------------|\n| `int` | 4 bytes | -2.1B to 2.1B | Array indices, counters, most values |\n| `long long` | 8 bytes | -9.2 x 10^18 to 9.2 x 10^18 | Prefix sums, large products, overflow-prone math |\n| `char` | 1 byte | -128 to 127 (signed) | Characters, frequency arrays |\n| `bool` | 1 byte | `true` / `false` | Visited arrays, flags |\n| `double` | 8 bytes | ±1.7 x 10^308 | Rarely used, some geometry problems |\n| `size_t` | 8 bytes (64-bit) | 0 to 18.4 x 10^18 | Return type of `.size()` (unsigned!) |\n\n\nThe most dangerous pitfall with types in C++ is **integer overflow**. In C++, **signed integer overflow is undefined behavior**. The compiler can do literally anything, including optimizing away your bounds checks or producing incorrect results silently.\n\nConsider the classic binary search:\n\n\n```cpp\n// BUG: if left + right > INT_MAX, this is undefined behavior\nint mid = (left + right) / 2;\n\n// CORRECT: safe from overflow\nint mid = left + (right - left) / 2;\n```\n\n\nThis is not a theoretical concern. When `left` and `right` are both above 1 billion, their sum exceeds `int` range. In C++, the compiler might optimize the code in ways that make the bug impossible to debug.\n\nWhen should you use `long long` instead of `int`? Use `long long` in these cases:\n\n1. **Prefix sums** of arrays with large values (sum of 10^5 elements each up to 10^9 gives 10^14)\n2. **Multiplication** of two large ints (e.g., `n * (n - 1)` where n is near 10^5)\n3. **Factorial or combination** calculations\n4. **Modulo problems** where intermediate sums can exceed int range before taking mod\n\nThe `1LL *` trick is the idiomatic way to promote an expression to `long long` before overflow happens:\n\n\n```cpp\n// Overflow: 100000 * 99999 > INT_MAX, undefined behavior\nint wrong = n * (n - 1);\n\n// Safe: 1LL promotes the entire expression to long long\nlong long correct = 1LL * n * (n - 1);\n\n// Also safe: explicit cast BEFORE multiplication\nlong long alsoCorrect = (long long)n * (n - 1);\n\n// WRONG: casting AFTER multiplication is too late, UB already happened\nlong long stillWrong = (long long)(n * (n - 1));\n```\n\n\nThe placement of the cast matters. `(long long)n * (n - 1)` first promotes `n` to `long long`, then performs `long long` multiplication. But `(long long)(n * (n - 1))` performs `int` multiplication first (which is UB if it overflows), then casts the corrupted result.\n\n### The `size_t` Trap\n\nEvery STL container's `.size()` method returns `size_t`, which is an **unsigned** integer. This creates a subtle and dangerous bug:\n\n\n```cpp\nvector v; // empty vector\n// BUG: v.size() is 0 (unsigned), subtracting 1 wraps to 18446744073709551615\nfor (int i = 0; i < v.size() - 1; i++) {\n // This loop runs ~18 quintillion times\n}\n\n// SAFE: cast to int first\nfor (int i = 0; i < (int)v.size() - 1; i++) {\n // Correctly does not execute\n}\n\n// ALSO SAFE: check emptiness first\nif (v.size() >= 2) {\n for (int i = 0; i < v.size() - 1; i++) { ... }\n}\n```\n\n\n**The ternary operator** is a compact alternative to if-else for inline decisions:\n\n\n```cpp\nint result = (a > b) ? a : b; // Same as max(a, b)\nstring label = (count == 1) ? \"item\" : \"items\";\n```\n\n\n**The **`auto`** keyword** lets the compiler deduce the type for you. It is especially useful with iterators and complex types:\n\n\n```cpp\nauto it = map.find(key); // instead of unordered_map::iterator\nauto [key, value] = *map.begin(); // structured binding (C++17)\nfor (auto& [k, v] : myMap) { ... } // clean map iteration\n```\n\n\n---\n\n# Operators and Control Flow\n\nMost operators in C++ work as you would expect, but a few deserve special attention for DSA.\n\n**Modular arithmetic** with `%` appears in hashing, cyclic array problems, and math-heavy questions. In C++, integer division truncates toward zero, so `%` can return a negative result when an operand is negative: `-7 % 3` gives `-1`, not `2`. To get a positive result:\n\n\n```cpp\nint positiveMod = ((n % m) + m) % m;\n```\n\n\nMany problems ask you to return the result \"modulo 10^9 + 7\" to prevent overflow in the output:\n\n\n```cpp\nconst int MOD = 1e9 + 7;\n\n// Apply modulo during computation, not just at the end\nlong long result = 0;\nfor (int i = 0; i < n; i++) {\n result = (result + values[i]) % MOD;\n}\nreturn (int)result;\n```\n\n\n### Bitwise Operations\n\nBit manipulation problems are common in DSA. Here are the operators and patterns you need:\n\n\n| Operator | Meaning | Example | DSA Use |\n|----------|---------|---------|---------|\n| `&` | AND | `n & 1` | Check odd/even |\n| `\\|` | OR | `mask \\| (1 << i)` | Set bit i |\n| `^` | XOR | `a ^ b` | Find single number, swap |\n| `~` | NOT | `~mask` | Invert bits |\n| `<<` | Left shift | `1 << i` | Create bit mask |\n| `>>` | Right shift | `n >> 1` | Divide by 2 |\n\n\nCommon bitmask patterns:\n\n\n```cpp\n// Check if bit i is set\nbool isSet = (mask >> i) & 1;\n\n// Set bit i\nmask |= (1 << i);\n\n// Clear bit i\nmask &= ~(1 << i);\n\n// Toggle bit i\nmask ^= (1 << i);\n\n// Count set bits (GCC/Clang built-in, works on LeetCode)\nint bits32 = __builtin_popcount(mask); // for int (use either)\nint bits64 = __builtin_popcountll(mask64); // for long long\n```\n\n\n`__builtin_popcount` is available on every major online judge including LeetCode. Using it shows you know the C++ toolchain. The alternative is the Brian Kernighan algorithm (`n &= (n - 1)` clears the lowest set bit on each iteration), which works in any C++ environment but is more verbose.\n\nNote that C++ does not have a dedicated unsigned right shift operator. Right shift on a signed type sign-extends (arithmetic shift). If you need unsigned (logical) shift behavior, cast to the matching unsigned type first: `unsigned int` for `int`, `unsigned long long` for `long long`.\n\n### Control Flow and Loops\n\nC++ has four loop forms commonly used in DSA:\n\n\n```cpp\n// Index-based (most common)\nfor (int i = 0; i < n; i++) { ... }\n\n// Backward iteration\nfor (int i = n - 1; i >= 0; i--) { ... }\n\n// Range-based for (C++11): iterating over containers\nfor (int num : nums) { ... } // by value (copies element)\nfor (int& num : nums) { ... } // by reference (can modify)\nfor (const int& num : nums) { ... } // by const reference (read-only, no copy)\n\n// Structured bindings in range-based for (C++17)\nfor (auto& [key, val] : myMap) { ... } // clean map iteration\n```\n\n\n**Structured bindings** (C++17) let you unpack pairs, tuples, and map entries directly:\n\n\n```cpp\nauto [key, value] = *myMap.begin();\nfor (auto& [k, v] : myMap) {\n // k is the key, v is the value\n}\npair p = {3, 4};\nauto [x, y] = p;\n```\n\n\n**Short-circuit evaluation** with `&&` and `||` matters for bounds checking:\n\n\n```cpp\n// Safe: if i is out of bounds, grid[i][j] is never accessed\nif (i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] == 1) { ... }\n```\n\n\n---\n\n# Functions and Pass-by-Reference\n\nThis section covers a key performance concept in C++ DSA: how you pass arguments to functions.\n\nC++ gives you three ways to pass parameters:\n\n\n```cpp\nvoid byValue(vector v) { ... } // copies entire vector, SLOW!\nvoid byRef(vector& v) { ... } // modifies original, fast\nvoid byConstRef(const vector& v) { ... } // read-only, no copy, fast\n```\n\n\nWhen you pass a `vector` by value, C++ copies the entire vector. For a recursive function called n times with a vector of size n, this turns your O(n) algorithm into O(n^2). This is a common C++ performance mistake.\n\nThe `swap` function is built into C++ and works with any type:\n\n\n```cpp\nswap(arr[i], arr[j]); // swaps in-place, no temp variable needed\n```\n\n\nC++ `swap` is a single function call that swaps two values in-place with no temp variable needed.\n\n### Lambda Functions\n\nLambdas are anonymous functions, used heavily for custom sort comparators and recursive helper functions. The syntax is:\n\n\n```cpp\n// Basic lambda\nauto add = [](int a, int b) { return a + b; };\n\n// Lambda with capture\nint target = 5;\nauto matches = [target](int x) { return x == target; }; // capture target by value\nauto matches2 = [&target](int x) { return x == target; }; // capture target by reference\n\n// Capture everything by reference (most common in DSA)\nauto fn = [&]() { /* can access all outer variables */ };\n\n// Capture everything by value\nauto fn2 = [=]() { /* copies of all outer variables */ };\n```\n\n\nThe capture clause `[]` controls which variables from the surrounding scope the lambda can access:\n\n\n| Capture | Meaning | When to Use |\n|---------|---------|-------------|\n| `[]` | Nothing | Standalone comparators |\n| `[&]` | All by reference | Recursive helpers, DFS |\n| `[=]` | All by value | Rarely needed in DSA |\n| `[&x, y]` | `x` by ref, `y` by value | Fine-grained control |\n\n\n### Recursive Lambdas with `function<>`\n\nFor recursive helper functions inside a method (common for DFS, backtracking), you need `function<>` because a lambda cannot refer to itself through `auto`:\n\n\n```cpp\n// DFS using a recursive lambda\nfunction dfs = [&](int node) {\n visited[node] = true;\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) dfs(neighbor);\n }\n};\ndfs(startNode);\n```\n\n\n### Backtracking Pattern\n\nHere is the classic backtracking template in C++, showing pass-by-reference semantics:\n\n\n```cpp\nvoid backtrack(vector& path, vector>& results, vector& nums) {\n if (path.size() == nums.size()) {\n results.push_back(path); // C++ copies the vector automatically\n return;\n }\n for (int i = 0; i < nums.size(); i++) {\n path.push_back(nums[i]);\n backtrack(path, results, nums);\n path.pop_back(); // undo choice\n }\n}\n```\n\n\n`results.push_back(path)` creates a copy of the current `path` vector. C++ containers are value types and copy automatically on insertion, so you do not need to write any extra code to avoid storing a reference.\n\n---\n\n# Pointers and Memory (DSA Essentials)\n\nPointers are central to working with linked structures in C++. You only need a small subset of pointer knowledge for coding interviews.\n\n### Why Pointers in DSA?\n\nLinked lists and trees are defined using pointers in C++. On LeetCode and in interviews, the node definitions look like this:\n\n\n```cpp\nstruct ListNode {\n int val;\n ListNode* next;\n ListNode(int val) : val(val), next(nullptr) {}\n};\n\nstruct TreeNode {\n int val;\n TreeNode* left;\n TreeNode* right;\n TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}\n};\n```\n\n\nThe `*` in `ListNode* next` means \"next is a pointer to a ListNode.\" A pointer holds the memory address of an object, not the object itself.\n\n### Essential Pointer Operations\n\n\n```cpp\n// Creating nodes on the heap\nListNode* head = new ListNode(1);\nhead->next = new ListNode(2);\nhead->next->next = new ListNode(3);\n\n// Accessing members through a pointer\nint value = head->val; // arrow operator for pointers\nListNode* nextNode = head->next;\n\n// Null check\nif (head == nullptr) { ... } // always check before dereferencing\nif (head != nullptr && head->next != nullptr) { ... }\n\n// Building a linked list concisely\nListNode* head = new ListNode(1, new ListNode(2, new ListNode(3)));\n// (Requires a two-argument constructor)\n```\n\n\nThe **arrow operator** `->` is used to access members through a pointer. It is equivalent to `(*ptr).member`. It is used heavily in linked list and tree problems.\n\n`nullptr` is the C++11 replacement for `NULL`. Always use `nullptr` for null pointers. It is type-safe and avoids ambiguity with integer 0.\n\n### `new` and Memory Leaks\n\n`new` allocates memory on the heap and returns a pointer. In production C++, you must eventually call `delete` to free that memory. But in coding interviews, **memory leaks are universally accepted**. No interviewer will ask you to free tree nodes after solving a problem.\n\n\n```cpp\nTreeNode* root = new TreeNode(1);\nroot->left = new TreeNode(2);\nroot->right = new TreeNode(3);\n// No need to delete in interviews\n```\n\n\n### Pointers vs References\n\nA reference (`&`) is an alias for an existing variable. It cannot be null and cannot be reassigned. A pointer (`*`) can be null, can be reassigned, and requires explicit dereferencing.\n\n\n```cpp\nint x = 5;\nint& ref = x; // ref IS x, any change to ref changes x\nint* ptr = &x; // ptr POINTS TO x, use *ptr to access the value\n\nref = 10; // x is now 10\n*ptr = 20; // x is now 20\nptr = nullptr; // valid: pointer can be null\n// ref = nullptr; // INVALID: reference cannot be null\n```\n\n\nFor DSA, the rule is simple: use references for function parameters (to avoid copies), use pointers for linked structures (nodes that can be null and need to be reassigned).\n\n---\n\n# Arrays and Vectors\n\nC++ has both C-style arrays and the `vector` class. For DSA, **always use **`vector` unless you need a fixed-size array for something like a frequency counter.\n\n\n```cpp\nint arr[5] = {0}; // C-style, fixed size, stack-allocated\nvector vec(5, 0); // vector, dynamic, heap-allocated\nvector vec2 = {1, 2, 3}; // initializer list\n```\n\n\n### Vector Operations\n\n\n| Operation | Syntax | Time | DSA Use |\n|-----------|--------|------|---------|\n| Append | `v.push_back(x)` | O(1) amortized | Building results |\n| Construct in-place | `v.emplace_back(args...)` | O(1) amortized | Constructing pairs/objects |\n| Pop last | `v.pop_back()` | O(1) | Stack operations |\n| Access by index | `v[i]` | O(1) | Random access |\n| Size | `v.size()` | O(1) | Loop bounds |\n| Empty check | `v.empty()` | O(1) | Guard clauses |\n| Front/Back | `v.front()`, `v.back()` | O(1) | Peek operations |\n| Insert at position | `v.insert(it, x)` | O(n) | Avoid in tight loops |\n| Erase at position | `v.erase(it)` | O(n) | Avoid in tight loops |\n| Reserve capacity | `v.reserve(n)` | O(n) | Pre-allocate, avoid reallocation |\n| Resize | `v.resize(n, val)` | O(n) | Set size with default value |\n| Clear | `v.clear()` | O(n) | Reset container |\n\n\n### 2D Vectors\n\nThe standard way to create a matrix in C++:\n\n\n```cpp\nint rows = 3, cols = 4;\nvector> matrix(rows, vector(cols, 0));\n\n// Access\nmatrix[row][col] = 5;\n\n// Dimensions\nint numRows = matrix.size();\nint numCols = matrix[0].size();\n```\n\n\nDP table initialization follows the same pattern:\n\n\n```cpp\n// 1D DP\nvector dp(n + 1, 0);\n\n// 2D DP\nvector> dp(m + 1, vector(n + 1, 0));\n\n// 2D boolean visited array\nvector> visited(rows, vector(cols, false));\n```\n\n\n### 4-Directional Movement\n\nGrid problems frequently require visiting neighbors in four directions. Here is the standard pattern:\n\n\n```cpp\nint dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right\n\nfor (auto& [dr, dc] : dirs) {\n int nr = row + dr, nc = col + dc;\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {\n // process neighbor (nr, nc)\n }\n}\n```\n\n\n\n```mermaid\nflowchart TD\n UP[\"(row-1, col)
Up\"]:::secondary\n LEFT[\"(row, col-1)
Left\"]:::secondary\n CENTER[\"(row, col)
Current\"]:::primary\n RIGHT[\"(row, col+1)
Right\"]:::secondary\n DOWN[\"(row+1, col)
Down\"]:::secondary\n\n UP --> CENTER\n LEFT --> CENTER\n CENTER --> RIGHT\n CENTER --> DOWN\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Useful Vector Operations\n\n\n```cpp\n// Fill with a value\nfill(dp.begin(), dp.end(), INT_MAX);\n\n// Copy a vector (vectors are value types, this is a deep copy)\nvector copy = original;\n\n// Copy a range\nvector sub(original.begin() + 2, original.begin() + 5);\n\n// Initialize with iota (0, 1, 2, 3, ...)\nvector ids(n);\niota(ids.begin(), ids.end(), 0);\n```\n\n\n---\n\n# Strings\n\nC++ `std::string` is **mutable**. You can modify characters in-place without creating a new string.\n\n\n```cpp\nstring s = \"hello\";\ns[0] = 'H'; // Direct modification, no StringBuilder or join() needed\ns += \" world\"; // Append (amortized O(1) for single chars)\ns.push_back('!'); // Append a single character\ns.pop_back(); // Remove last character\n```\n\n\n### Essential String Methods\n\n\n| Method | Example | DSA Use |\n|--------|---------|---------|\n| `s[i]` | `s[0]` | Access/modify character |\n| `s.size()` / `s.length()` | `s.size()` | Both work identically |\n| `s.empty()` | `s.empty()` | Check if empty |\n| `s.substr(pos, len)` | `s.substr(0, 3)` | Extract substring |\n| `s.find(sub)` | `s.find(\"ab\")` | Find substring (`string::npos` if not found) |\n| `s.push_back(c)` | `s.push_back('a')` | Append character |\n| `s.pop_back()` | `s.pop_back()` | Remove last character |\n| `s.front()` / `s.back()` | `s.back()` | First/last character |\n| `s == t` | `s == t` | Content comparison |\n| `s < t` | `s < t` | Lexicographic comparison |\n| `s + t` | `s + t` | Concatenation |\n\n\n`s == t` compares content directly. All comparison operators (`==`, `!=`, `<`, `>`, `<=`, `>=`) work on strings in C++ and compare lexicographically.\n\n### String-Number Conversions\n\n\n```cpp\n// Number to string\nstring s = to_string(42); // \"42\"\nstring s = to_string(3.14); // \"3.140000\"\n\n// String to number\nint n = stoi(\"42\"); // 42\nlong long big = stoll(\"999999999999\"); // for large numbers\ndouble d = stod(\"3.14\"); // 3.14\n```\n\n\n### String Parsing with `stringstream`\n\nWhen you need to split a string by spaces or other delimiters:\n\n\n```cpp\nstringstream ss(\"hello world foo\");\nstring word;\nwhile (ss >> word) {\n // processes \"hello\", \"world\", \"foo\"\n}\n\n// Split by custom delimiter\nstringstream ss2(\"a,b,c,d\");\nstring token;\nwhile (getline(ss2, token, ',')) {\n // processes \"a\", \"b\", \"c\", \"d\"\n}\n```\n\n\n### Character Arithmetic\n\nCharacter-to-index conversion uses simple arithmetic:\n\n\n```cpp\nchar c = 'f';\nint index = c - 'a'; // Maps 'a'-'z' to 0-25\nchar back = (char)('a' + 5); // Maps 5 back to 'f'\nint digit = c - '0'; // Maps '0'-'9' to 0-9\n```\n\n\nThe **frequency array** pattern appears in dozens of problems:\n\n\n```cpp\nint freq[26] = {0};\nfor (char c : s) {\n freq[c - 'a']++;\n}\n// freq[0] = count of 'a', freq[1] = count of 'b', etc.\n```\n\n\n### Character Utility Functions\n\nFrom ``:\n\n\n```cpp\nisalpha(c) // true if letter (a-z, A-Z)\nisdigit(c) // true if digit (0-9)\nisalnum(c) // true if letter or digit\ntolower(c) // lowercase version\ntoupper(c) // uppercase version\n```\n\n\nThese are especially useful for the \"Valid Palindrome\" family of problems where you need to ignore non-alphanumeric characters.\n\n---\n\n# STL Containers\n\nThe Standard Template Library (STL) is C++'s collection framework, and the foundation of C++ DSA code. This section covers every container commonly used in coding interviews.\n\n\n```mermaid\nflowchart TD\n STL[\"STL Containers\"]:::primary\n\n SEQ[\"Sequence
Containers\"]:::secondary\n ASSOC[\"Associative
Containers
(Sorted, Red-Black Tree)\"]:::orange\n UNORD[\"Unordered
Containers
(Hash Table)\"]:::green\n ADAPT[\"Container
Adaptors\"]:::teal\n\n VEC[\"vector\"]:::secondary\n DEQ[\"deque\"]:::secondary\n\n MAP[\"map\"]:::orange\n SET[\"set\"]:::orange\n MSET[\"multiset\"]:::orange\n\n UMAP[\"unordered_map\"]:::green\n USET[\"unordered_set\"]:::green\n\n STK[\"stack\"]:::teal\n QUE[\"queue\"]:::teal\n PQ[\"priority_queue\"]:::teal\n\n STL --> SEQ\n STL --> ASSOC\n STL --> UNORD\n STL --> ADAPT\n\n SEQ --> VEC\n SEQ --> DEQ\n\n ASSOC --> MAP\n ASSOC --> SET\n ASSOC --> MSET\n\n UNORD --> UMAP\n UNORD --> USET\n\n ADAPT --> STK\n ADAPT --> QUE\n ADAPT --> PQ\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#3bc9db,stroke:#000,color:#000\n```\n\n\n### `unordered_map`: The HashMap (O(1) Average)\n\n`unordered_map` is C++'s hash map. It appears in nearly every other problem for frequency counting, lookups, and memoization.\n\n\n```cpp\nunordered_map map;\n\n// Insert / Update\nmap[key] = value; // insert or overwrite\nmap[key]++; // auto-inserts 0 if missing, then increments\n\n// Lookup\nif (map.count(key)) { ... } // 1 if exists, 0 if not\nif (map.find(key) != map.end()) { ... } // iterator-based check\nint val = map[key]; // WARNING: auto-inserts default if missing!\n\n// Safe lookup (no auto-insert)\nauto it = map.find(key);\nif (it != map.end()) {\n int val = it->second;\n}\n\n// Delete\nmap.erase(key);\n\n// Size\nmap.size();\nmap.empty();\n\n// Iterate\nfor (auto& [key, val] : map) {\n // process key-value pair\n}\n```\n\n\n`map[key]` auto-inserts a default value if the key is missing. For `unordered_map`, writing `map[c]++` works without checking if `c` exists first because the default value for `int` is 0. This makes frequency counting a one-liner in C++.\n\n**Two Sum** using `unordered_map`:\n\n\n```cpp\nvector twoSum(vector& nums, int target) {\n unordered_map seen; // value -> index\n for (int i = 0; i < nums.size(); i++) {\n int complement = target - nums[i];\n if (seen.count(complement)) {\n return {seen[complement], i};\n }\n seen[nums[i]] = i;\n }\n return {};\n}\n```\n\n\n### `unordered_set`: The HashSet (O(1) Average)\n\n`unordered_set` stores unique elements with O(1) average lookup. Use it for visited tracking, duplicate detection, and membership testing.\n\n\n```cpp\nunordered_set visited;\n\n// Insert\nvisited.insert(node);\n// insert returns pair, the bool tells if insertion happened\nauto [it, inserted] = visited.insert(node);\nif (!inserted) { /* node was already in the set */ }\n\n// Check membership\nif (visited.count(node)) { ... }\n\n// Delete\nvisited.erase(node);\n\n// Iterate\nfor (int val : visited) { ... }\n```\n\n\n### `map` and `set`: The TreeMap and TreeSet (O(log n), Sorted)\n\n`map` and `set` are backed by red-black trees, keeping elements sorted at all times. Use them when you need sorted iteration, range queries, or floor/ceiling operations.\n\n\n```cpp\nmap sortedMap;\nsortedMap[3] = \"three\";\nsortedMap[1] = \"one\";\nsortedMap[5] = \"five\";\n// Iteration order: 1, 3, 5 (always sorted by key)\n\nset sortedSet = {5, 3, 1, 4, 2};\n// Iteration order: 1, 2, 3, 4, 5\n```\n\n\nThe power of `map` and `set` lies in their `lower_bound` and `upper_bound` methods:\n\n\n```cpp\nset s = {10, 20, 30, 40, 50};\n\nauto it = s.lower_bound(25); // points to 30 (first element >= 25)\nauto it2 = s.upper_bound(30); // points to 40 (first element > 30)\n\n// \"Floor\" (largest element <= target)\nauto it = s.upper_bound(25);\nif (it != s.begin()) {\n --it;\n int floor = *it; // 20\n}\n\n// First and last elements\nint smallest = *s.begin();\nint largest = *s.rbegin();\n```\n\n\nUse `map`/`set` when the problem requires finding the nearest element, range queries, or maintaining a sorted window. Common examples include sliding window median, meeting room scheduling, and interval problems. For everything else, prefer `unordered_map`/`unordered_set` for O(1) performance.\n\n### `multiset`: Sorted Set with Duplicates\n\n`multiset` allows duplicate elements, which `set` does not. This is useful for problems like \"Sliding Window Median\" where you need a sorted container that supports duplicates.\n\n\n```cpp\nmultiset ms = {3, 1, 4, 1, 5};\n// Contents: {1, 1, 3, 4, 5}\n\nms.insert(3);\n// Contents: {1, 1, 3, 3, 4, 5}\n\n// CAREFUL: erase(value) removes ALL occurrences\nms.erase(3); // removes BOTH 3s: {1, 1, 4, 5}\n\n// To remove only ONE occurrence, erase by iterator\nms.insert(3);\nms.insert(3); // {1, 1, 3, 3, 4, 5}\nms.erase(ms.find(3)); // removes ONE 3: {1, 1, 3, 4, 5}\n```\n\n\nThe main `multiset` pitfall: `erase(value)` removes ALL occurrences. Always use `erase(find(value))` to remove a single occurrence. This mistake appears frequently in sliding window problems.\n\n### `stack`\n\nThe stack adaptor provides LIFO access:\n\n\n```cpp\nstack stk;\n\nstk.push(1); // push onto top\nstk.push(2);\nint top = stk.top(); // peek: 2\nstk.pop(); // remove top (returns void!)\nbool empty = stk.empty();\nint sz = stk.size();\n```\n\n\nNote that `pop()` returns `void`, not the removed element. You must call `top()` before `pop()` if you need the value.\n\n### `queue`\n\nThe queue adaptor provides FIFO access, used extensively for BFS:\n\n\n```cpp\nqueue q;\n\nq.push(1); // enqueue\nq.push(2);\nint front = q.front(); // peek: 1\nq.pop(); // dequeue (returns void!)\nbool empty = q.empty();\nint sz = q.size();\n```\n\n\n**BFS template:**\n\n\n```cpp\nqueue> q;\nvector> visited(rows, vector(cols, false));\n\nq.push({startRow, startCol});\nvisited[startRow][startCol] = true;\n\nwhile (!q.empty()) {\n auto [row, col] = q.front();\n q.pop();\n\n for (auto& [dr, dc] : dirs) {\n int nr = row + dr, nc = col + dc;\n if (nr >= 0 && nr < rows && nc >= 0 && nc < cols\n && !visited[nr][nc] && grid[nr][nc] == 1) {\n visited[nr][nc] = true;\n q.push({nr, nc});\n }\n }\n}\n```\n\n\n**Level-order BFS** (processing one level at a time):\n\n\n```cpp\nint level = 0;\nwhile (!q.empty()) {\n int levelSize = q.size(); // capture size BEFORE processing\n for (int i = 0; i < levelSize; i++) {\n auto [row, col] = q.front();\n q.pop();\n // process and add neighbors\n }\n level++;\n}\n```\n\n\n### `deque`\n\n`deque` (double-ended queue) supports O(1) insertion and removal at both ends:\n\n\n```cpp\ndeque dq;\n\ndq.push_back(1); // add to back\ndq.push_front(0); // add to front\ndq.pop_back(); // remove from back\ndq.pop_front(); // remove from front\ndq.front(); // peek front\ndq.back(); // peek back\ndq[i]; // random access (O(1))\n```\n\n\nThe classic use case is the **monotonic deque** for sliding window maximum/minimum:\n\n\n```cpp\n// Sliding window maximum\ndeque dq; // stores indices, front is always the max\nvector result;\n\nfor (int i = 0; i < nums.size(); i++) {\n // Remove indices outside the window\n while (!dq.empty() && dq.front() < i - k + 1) {\n dq.pop_front();\n }\n // Remove smaller elements from back (they can never be the max)\n while (!dq.empty() && nums[dq.back()] <= nums[i]) {\n dq.pop_back();\n }\n dq.push_back(i);\n\n if (i >= k - 1) {\n result.push_back(nums[dq.front()]);\n }\n}\n```\n\n\n### `priority_queue`: MAX-Heap by Default!\n\nThe most important detail for C++ heaps: `priority_queue`** is a MAX-heap by default**.\n\n\n```cpp\n// MAX-heap (default), largest element on top\npriority_queue maxHeap;\n\n// MIN-heap, smallest element on top\npriority_queue, greater> minHeap;\n```\n\n\nThe three template arguments for a min-heap are:\n\n1. `int`: the element type\n2. `vector`: the underlying container\n3. `greater`: the comparator (greater makes it a min-heap, counterintuitively)\n\n\n```cpp\n// Max-heap operations\npriority_queue pq;\npq.push(3);\npq.push(1);\npq.push(4);\nint top = pq.top(); // 4 (largest)\npq.pop(); // removes 4 (returns void!)\n```\n\n\nC++ `priority_queue` is a MAX-heap by default. To get a min-heap, use `priority_queue, greater>`. Forgetting this will make your Dijkstra return the longest path instead of the shortest.\n\n**Dijkstra's algorithm** using a min-heap of pairs:\n\n\n```cpp\n// Min-heap of {distance, node}\npriority_queue, vector>, greater>> pq;\nvector dist(n, INT_MAX);\n\ndist[start] = 0;\npq.push({0, start});\n\nwhile (!pq.empty()) {\n auto [d, u] = pq.top();\n pq.pop();\n\n if (d > dist[u]) continue; // skip outdated entries\n\n for (auto& [v, w] : graph[u]) {\n if (dist[u] + w < dist[v]) {\n dist[v] = dist[u] + w;\n pq.push({dist[v], v});\n }\n }\n}\n```\n\n\nNote that pairs in the priority queue compare lexicographically (by first element, then second). Putting distance as the first element ensures the min-heap orders by distance.\n\n### Containers Quick Reference\n\n\n| Container | Key Ops | Time | When to Use |\n|-----------|---------|------|-------------|\n| `vector` | `push_back`, `[]`, `size` | O(1) access/append | Dynamic arrays, DP tables |\n| `unordered_map` | `[]`, `count`, `find` | O(1) avg | Frequency counting, lookups |\n| `unordered_set` | `insert`, `count` | O(1) avg | Visited tracking, dedup |\n| `map` | `lower_bound`, `upper_bound` | O(log n) | Sorted access, range queries |\n| `set` | `lower_bound`, `upper_bound` | O(log n) | Sorted unique elements |\n| `multiset` | `insert`, `erase(find())` | O(log n) | Sorted with duplicates |\n| `stack` | `push`, `pop`, `top` | O(1) | Monotonic stack, DFS |\n| `queue` | `push`, `pop`, `front` | O(1) | BFS |\n| `deque` | `push_front`, `push_back` | O(1) both ends | Sliding window |\n| `priority_queue` | `push`, `pop`, `top` | O(log n) | Heaps (**MAX** default!) |\n\n\n---\n\n# Sorting and Comparators\n\nSorting is one of the most frequent operations in DSA. C++ provides `sort()` from ``, which uses Introsort (a hybrid of quicksort, heapsort, and insertion sort) and is guaranteed O(n log n).\n\n\n```cpp\nvector nums = {3, 1, 4, 1, 5};\n\n// Ascending (default)\nsort(nums.begin(), nums.end());\n\n// Descending\nsort(nums.begin(), nums.end(), greater());\n\n// Custom comparator with lambda\nsort(nums.begin(), nums.end(), [](int a, int b) {\n return a > b; // descending\n});\n```\n\n\n### Sorting Complex Types\n\nSorting intervals by start time (Merge Intervals pattern):\n\n\n```cpp\nvector> intervals = {{3, 5}, {1, 4}, {2, 6}};\nsort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {\n return a[0] < b[0]; // sort by first element\n});\n```\n\n\nSorting by multiple keys:\n\n\n```cpp\n// Sort by second element, then by first element as tiebreaker\nvector> points = {{1, 3}, {2, 1}, {3, 1}};\nsort(points.begin(), points.end(), [](auto& a, auto& b) {\n if (a.second != b.second) return a.second < b.second;\n return a.first < b.first;\n});\n```\n\n\n### `stable_sort`\n\n`stable_sort` preserves the relative order of equal elements. Use it when the original order matters for elements that compare equal:\n\n\n```cpp\nstable_sort(v.begin(), v.end(), comparator);\n```\n\n\n### `nth_element`: O(n) Kth Element\n\nFor \"Kth Largest Element\" type problems, `nth_element` rearranges the vector so the kth element is in its sorted position, with all smaller elements before it and all larger elements after. It runs in O(n) average time:\n\n\n```cpp\nvector nums = {3, 1, 4, 1, 5, 9, 2, 6};\nint k = 3;\nnth_element(nums.begin(), nums.begin() + k, nums.end());\n// nums[k] is now the (k+1)th smallest element\n// Elements before k are all <= nums[k], elements after are all >= nums[k]\n```\n\n\n### Safe Comparators\n\nC++ comparators return `bool`, not an `int`. This means there is no overflow risk from subtraction tricks:\n\n\n```cpp\n// SAFE in C++: returns bool, no subtraction needed\nsort(nums.begin(), nums.end(), [](int a, int b) { return a < b; });\n\n// C++ does not have this problem because comparators are boolean\n```\n\n\nOne rule matters for custom comparators: use strict comparison (`<` or `>`), never `<=` or `>=`. The comparator must return `false` when two elements are equal. Returning `true` for equal elements violates the strict weak ordering that `sort` and the ordered containers require, which is undefined behavior and can crash.\n\n---\n\n# STL Algorithms and Idioms\n\nThe `` and `` headers provide dozens of functions that eliminate common boilerplate.\n\n### Binary Search Family\n\nThese work on **sorted** ranges:\n\n\n```cpp\nvector v = {1, 3, 5, 7, 9};\n\n// First element >= target\nauto it = lower_bound(v.begin(), v.end(), 5); // points to 5\n\n// First element > target\nauto it2 = upper_bound(v.begin(), v.end(), 5); // points to 7\n\n// Boolean: does target exist?\nbool found = binary_search(v.begin(), v.end(), 5); // true\n\n// Get index from iterator\nint idx = lower_bound(v.begin(), v.end(), 5) - v.begin(); // 2\n```\n\n\n`lower_bound` and `upper_bound` together can count occurrences of a value in a sorted range:\n\n\n```cpp\nint count = upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target);\n```\n\n\n`lower_bound` returns an iterator to the first element >= target. `upper_bound` returns an iterator to the first element > target. If the element is not found, both return where it would be inserted to maintain sorted order.\n\n### Numeric Algorithms\n\n\n```cpp\n// Sum of elements\nint sum = accumulate(v.begin(), v.end(), 0);\n\n// CAREFUL: use 0LL for long long sum to avoid overflow\nlong long bigSum = accumulate(v.begin(), v.end(), 0LL);\n\n// GCD (C++17)\nint g = gcd(12, 8); // 4\n\n// Fill with sequential values (0, 1, 2, 3, ...)\nvector ids(n);\niota(ids.begin(), ids.end(), 0);\n```\n\n\n### Element Queries\n\n\n```cpp\n// Max and min element (returns iterator)\nint maxVal = *max_element(v.begin(), v.end());\nint minVal = *min_element(v.begin(), v.end());\n\n// Count occurrences\nint cnt = count(v.begin(), v.end(), target);\n\n// Find first occurrence (returns iterator, end() if not found)\nauto it = find(v.begin(), v.end(), target);\nif (it != v.end()) {\n int idx = it - v.begin();\n}\n```\n\n\n### Transformation Algorithms\n\n\n```cpp\n// Reverse\nreverse(v.begin(), v.end());\nreverse(s.begin(), s.end()); // works on strings too\n\n// Remove consecutive duplicates (must sort first for all duplicates)\nsort(v.begin(), v.end());\nauto newEnd = unique(v.begin(), v.end());\nv.erase(newEnd, v.end()); // actually shrink the vector\n\n// Next permutation (for generating permutations in order)\nsort(v.begin(), v.end());\ndo {\n // process current permutation\n} while (next_permutation(v.begin(), v.end()));\n\n// Fill with a value\nfill(v.begin(), v.end(), 0);\nfill(dp.begin(), dp.end(), INT_MAX);\n```\n\n\n---\n\n# Iterators and Iterator Invalidation\n\nIterators are C++'s way of pointing to elements in containers. You have already been using them implicitly with `begin()`, `end()`, and range-based for loops. This section covers the explicit iterator operations and, more importantly, the rules about when iterators become invalid.\n\n### Iterator Basics\n\n\n```cpp\nvector v = {10, 20, 30, 40, 50};\n\nauto it = v.begin(); // points to first element (10)\nauto end = v.end(); // points PAST the last element\n\n// Advance and access\n++it; // move to next element\nint val = *it; // dereference: 20\n\n// Navigate\nauto it2 = next(it); // returns iterator to next element (30)\nauto it3 = prev(it2); // returns iterator to previous element (20)\nadvance(it, 2); // moves it forward 2 positions (now at 40)\n\n// Reverse iterators\nauto rit = v.rbegin(); // points to last element (50)\nauto rend = v.rend(); // points before first element\n```\n\n\n### Iterator Invalidation Rules\n\nThis is a foundational C++ concept for DSA. When you modify a container, some or all existing iterators may become **invalid** (pointing to garbage memory). Using an invalid iterator is undefined behavior.\n\n\n| Container | Insert Invalidates | Erase Invalidates |\n|-----------|-------------------|-------------------|\n| `vector` | All iterators if reallocation occurs, otherwise iterators at and after insertion point | Iterators at and after erased position |\n| `deque` | All iterators | All iterators |\n| `list` | No iterators | Only the erased iterator |\n| `map` / `set` | No iterators | Only the erased iterator |\n| `unordered_map` / `unordered_set` | All iterators if rehash occurs | Only the erased iterator |\n\n\n---\n\n# Iterating and Modifying Collections Safely\n\n### Safe Erase Pattern for Maps and Sets\n\nThe `erase` method returns an iterator to the next valid element. Use this in a loop:\n\n\n```cpp\nfor (auto it = map.begin(); it != map.end(); ) {\n if (it->second < threshold) {\n it = map.erase(it); // erase returns next valid iterator\n } else {\n ++it;\n }\n}\n```\n\n\nThis pattern works for `map`, `set`, `unordered_map`, and `unordered_set`.\n\n### Erase-Remove Idiom for Vectors\n\n`remove` and `remove_if` from `` do not actually remove elements from a vector. They move the unwanted elements to the end and return an iterator to the new logical end. You must call `erase` to actually shrink the vector:\n\n\n```cpp\nvector v = {1, 2, 3, 4, 5, 6};\n\n// Remove all even numbers\nv.erase(\n remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }),\n v.end()\n);\n// v is now {1, 3, 5}\n```\n\n\nThis is called the **erase-remove idiom** and is one of the most well-known C++ patterns.\n\nC++20 added `erase_if` as a cleaner alternative:\n\n\n```cpp\n// C++20 (available on most modern judges)\nerase_if(v, [](int x) { return x % 2 == 0; });\n```\n\n\nIn practice, most DSA problems build new collections rather than modifying during iteration. But when the problem requires in-place modification (like \"Remove Duplicates from Sorted Array\"), these patterns matter.\n\n---\n\n# Recursion and the Call Stack\n\nRecursive functions use the call stack, and C++ has a finite stack size, typically 1-8 MB depending on the platform. Each function call uses roughly 100-200 bytes of stack space, which means you can recurse about 10,000 to 50,000 levels deep before hitting a stack overflow.\n\n\n| Scenario | Typical Depth | Risk |\n|----------|--------------|------|\n| Balanced binary tree | O(log n) | Safe for n up to 10^6 |\n| Linked list / skewed tree | O(n) | Dangerous if n > 10,000 |\n| Backtracking | O(depth) | Usually safe (depth is small) |\n| DFS on graph | O(V) | Dangerous for large graphs |\n\n\nWhen recursion is too deep, convert to an iterative approach using an explicit stack:\n\n\n```cpp\n// Recursive DFS\nvoid dfs(int node, vector>& graph, vector& visited) {\n visited[node] = true;\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n dfs(neighbor, graph, visited);\n }\n }\n}\n\n// Iterative DFS (safe for any depth)\nvoid dfsIterative(int start, vector>& graph, vector& visited) {\n stack stk;\n stk.push(start);\n\n while (!stk.empty()) {\n int node = stk.top();\n stk.pop();\n\n if (visited[node]) continue;\n visited[node] = true;\n\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n stk.push(neighbor);\n }\n }\n }\n}\n```\n\n\nC++ does not reliably optimize tail recursion (it depends on the compiler and optimization level), so do not rely on it.\n\n---\n\n# Graph Representation\n\nThere are two main ways to represent graphs in C++, and your choice depends on whether node IDs are contiguous integers.\n\n### Approach 1: `vector>` (Contiguous Node IDs)\n\nThis is the most common approach when nodes are numbered 0 to n-1:\n\n\n```cpp\nint n = 5;\nvector> graph(n); // adjacency list\n\n// Build from edge list\nfor (auto& edge : edges) {\n graph[edge[0]].push_back(edge[1]);\n graph[edge[1]].push_back(edge[0]); // for undirected graphs\n}\n\n// Traverse neighbors of node u\nfor (int neighbor : graph[u]) {\n // process neighbor\n}\n```\n\n\n### Approach 2: `unordered_map>` (Sparse/Non-Contiguous IDs)\n\nUse this when node IDs are not contiguous or can be arbitrary values:\n\n\n```cpp\nunordered_map> graph;\n\nfor (auto& edge : edges) {\n graph[edge[0]].push_back(edge[1]);\n graph[edge[1]].push_back(edge[0]);\n}\n```\n\n\n### Weighted Graphs\n\nFor weighted graphs, use pairs to store `{neighbor, weight}`:\n\n\n```cpp\nvector>> graph(n); // {neighbor, weight}\n\nfor (auto& edge : edges) {\n int u = edge[0], v = edge[1], w = edge[2];\n graph[u].push_back({v, w});\n graph[v].push_back({u, w}); // for undirected\n}\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph Adjacency List\n N0[\"Node 0\"]:::primary --> L0[\"[1, 2]\"]:::secondary\n N1[\"Node 1\"]:::primary --> L1[\"[0, 3]\"]:::secondary\n N2[\"Node 2\"]:::primary --> L2[\"[0, 3]\"]:::secondary\n N3[\"Node 3\"]:::primary --> L3[\"[1, 2, 4]\"]:::secondary\n N4[\"Node 4\"]:::primary --> L4[\"[3]\"]:::secondary\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n\n| Representation | When to Use | Pros | Cons |\n|---------------|-------------|------|------|\n| `vector>` | Nodes are 0 to n-1 | Fast, cache-friendly, O(1) access | Wastes space for sparse graphs |\n| `unordered_map>` | Sparse/string/arbitrary node IDs | Flexible | Slightly slower due to hashing |\n\n\n---\n\n# Pair and Tuple\n\n`pair` is a built-in two-element container, used constantly in C++ DSA. C++ pairs are first-class citizens that work with sorting, sets, maps, and priority queues.\n\n### `pair`\n\n\n```cpp\n// Creating pairs\npair p = {3, 4};\npair p2 = make_pair(3, 4);\n\n// Accessing elements\nint first = p.first;\nint second = p.second;\n\n// Structured bindings (C++17): cleaner access\nauto [x, y] = p;\n```\n\n\nPairs compare **lexicographically** (by first element, then second), which is useful for:\n\n\n```cpp\n// Pairs in a set (like storing coordinates)\nset> visited;\nvisited.insert({row, col});\nif (visited.count({row, col})) { ... }\n\n// Pairs in a priority_queue (sorted by first element)\n// For Dijkstra: {distance, node} sorts by distance automatically\npriority_queue, vector>, greater>> pq;\npq.push({0, start});\n\n// Pairs in a vector (sorting by first, then second)\nvector> edges;\nsort(edges.begin(), edges.end()); // lexicographic sort, no comparator needed\n```\n\n\n### `tuple`\n\nFor three or more elements, use `tuple`:\n\n\n```cpp\n// Creating tuples\ntuple t = {1, 2, 3};\nauto t2 = make_tuple(1, 2, 3);\n\n// Accessing elements\nauto [a, b, c] = t; // structured bindings (preferred)\nint first = get<0>(t); // pre-C++17 access\n\n// Tuples also compare lexicographically\nset> visited3D;\nvisited3D.insert({x, y, z});\n```\n\n\nFor most DSA problems, `pair` is sufficient. Use `tuple` when you need three or more values (e.g., `{distance, row, col}` in a grid BFS with weights).\n\n---\n\n# Deduplication Patterns\n\nTwo patterns appear frequently for avoiding duplicate results in combination/permutation problems.\n\n### Pattern 1: Sort and Skip\n\nSort the input, then skip consecutive duplicates:\n\n\n```cpp\nsort(nums.begin(), nums.end());\nfor (int i = 0; i < nums.size(); i++) {\n if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate\n // process nums[i]\n}\n```\n\n\nFor backtracking problems (like 3Sum or Combination Sum II):\n\n\n```cpp\nvoid backtrack(int start, vector& nums, vector& path, vector>& results) {\n results.push_back(path);\n for (int i = start; i < nums.size(); i++) {\n if (i > start && nums[i] == nums[i - 1]) continue; // skip at this level\n path.push_back(nums[i]);\n backtrack(i + 1, nums, path, results);\n path.pop_back();\n }\n}\n```\n\n\n### Pattern 2: Sort + `unique` + Erase\n\nFor removing all duplicates from a vector:\n\n\n```cpp\nsort(v.begin(), v.end());\nv.erase(unique(v.begin(), v.end()), v.end());\n```\n\n\n### Pattern 3: Set-Based\n\nUse a set to track seen combinations:\n\n\n```cpp\nset> seen;\n// ... during backtracking:\nif (seen.insert(path).second) {\n results.push_back(path);\n}\n```\n\n\nThe sort-and-skip approach is preferred because it avoids the overhead of a set and is the standard technique for this pattern.\n\n---\n\n# Common DSA Idioms\n\nThis section collects the small but important patterns that come up repeatedly across DSA problems.\n\n### Swap\n\n\n```cpp\nswap(a, b); // works with any type\nswap(nums[i], nums[j]); // swap elements in a vector\n// STL swap handles the temp variable internally\n```\n\n\n### Sentinel Values\n\n\n```cpp\nint minVal = INT_MAX; // 2,147,483,647\nint maxVal = INT_MIN; // -2,147,483,648\nlong long llMax = LLONG_MAX; // 9,223,372,036,854,775,807\nlong long llMin = LLONG_MIN;\n\n// Or using numeric_limits (more explicit)\nint minVal2 = numeric_limits::max();\nint maxVal2 = numeric_limits::min();\n```\n\n\nBe careful with `INT_MIN`: `abs(INT_MIN)` is undefined behavior because the positive equivalent exceeds the `int` range. If a problem involves absolute values, consider using `long long`.\n\n### Math Utilities\n\n\n```cpp\nmax(a, b); // returns larger\nmin(a, b); // returns smaller\nabs(a); // absolute value (use with caution for INT_MIN)\n\n// Ceiling division for positive a and b\nint ceilDiv = (a + b - 1) / b;\n\n// Three-way max/min\nmax({a, b, c}); // initializer list version\nmin({a, b, c});\n```\n\n\n### The `1LL *` Trick (Reiterated)\n\n\n```cpp\n// Prevents int overflow in multiplication\nlong long result = 1LL * a * b;\n\n// Common in modular arithmetic\nlong long mod_result = 1LL * a * b % MOD;\n```\n\n\n### Type Conversions\n\n\n```cpp\n// Number to string\nto_string(42); // \"42\"\n\n// String to number\nstoi(\"42\"); // int\nstoll(\"999999999999\"); // long long\nstod(\"3.14\"); // double\n\n// size_t to int (safe for DSA constraints where n < 2^31)\nint n = (int)v.size();\n\n// char to int (digit)\nint d = c - '0';\n\n// int to char (digit)\nchar c = '0' + d;\n```\n\n\n### Deep Copy\n\nC++ vectors are **value types**. Assigning one vector to another creates a complete deep copy:\n\n\n```cpp\nvector original = {1, 2, 3};\nvector copy = original; // deep copy\ncopy[0] = 99; // original is unchanged\n\n// 2D vectors also deep copy\nvector> matrix2 = matrix; // full deep copy\n```\n\n\nIn C++, assigning a container creates a full copy by default. If you want a reference instead, use `&`:\n\n\n```cpp\nvector& ref = original; // ref IS original, not a copy\nref[0] = 99; // original is changed\n```\n\n\n---\n\n# OOP Basics for DSA\n\nIn DSA, you use `struct` to define nodes for linked lists, trees, tries, and graphs. C++ `struct` is identical to `class` except that members are public by default, which is what you want for DSA nodes.\n\n### ListNode\n\n\n```cpp\nstruct ListNode {\n int val;\n ListNode* next;\n ListNode(int val) : val(val), next(nullptr) {}\n ListNode(int val, ListNode* next) : val(val), next(next) {}\n};\n\n// Usage\nListNode* head = new ListNode(1);\nhead->next = new ListNode(2);\nhead->next->next = new ListNode(3);\n\n// One-liner construction\nListNode* head = new ListNode(1, new ListNode(2, new ListNode(3)));\n```\n\n\n### TreeNode\n\n\n```cpp\nstruct TreeNode {\n int val;\n TreeNode* left;\n TreeNode* right;\n TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}\n};\n\n// Usage\nTreeNode* root = new TreeNode(1);\nroot->left = new TreeNode(2);\nroot->right = new TreeNode(3);\n```\n\n\n### TrieNode\n\n\n```cpp\nstruct TrieNode {\n TrieNode* children[26];\n bool isEndOfWord;\n\n TrieNode() : isEndOfWord(false) {\n fill(begin(children), end(children), nullptr);\n }\n};\n\n// Usage\nTrieNode* root = new TrieNode();\n```\n\n\n### Graph Node (for problems with custom node structures)\n\n\n```cpp\nstruct Node {\n int val;\n vector neighbors;\n Node(int val) : val(val) {}\n};\n```\n\n\n### Constructor Initializer Lists\n\nThe `: val(val), next(nullptr)` syntax is a **constructor initializer list**. It initializes members directly rather than assigning them in the constructor body. For DSA, the practical benefit is cleaner, more concise constructors.\n\n\n```cpp\n// Initializer list (preferred)\nListNode(int val) : val(val), next(nullptr) {}\n\n// Equivalent but less idiomatic\nListNode(int val) {\n this->val = val;\n this->next = nullptr;\n}\n```\n\n\n---\n\n# Performance Considerations\n\nC++ is the fastest mainstream language for DSA. If you are getting TLE (Time Limit Exceeded) in C++, the issue is almost certainly your algorithm, not the language. That said, a few performance habits can make a difference.\n\n### Fast I/O\n\nFor problems with heavy input/output, add these two lines at the start of `main`:\n\n\n```cpp\nios_base::sync_with_stdio(false);\ncin.tie(nullptr);\n```\n\n\nThis disconnects C++ streams from C streams and unties `cin` from `cout`, making I/O significantly faster. On LeetCode this rarely matters (input parsing is handled for you), but it matters for competitive programming and some interview platforms.\n\n### `reserve()` for Vectors\n\nWhen you know the approximate size of a vector, `reserve` pre-allocates memory to avoid repeated reallocations:\n\n\n```cpp\nvector result;\nresult.reserve(n); // avoids reallocations during push_back\nfor (int i = 0; i < n; i++) {\n result.push_back(i);\n}\n```\n\n\n### Pass by `const &`\n\nAlways pass containers by reference (covered in the functions section).\n\n\n```cpp\n// SLOW: copies the entire vector on every call\nint solve(vector nums) { ... }\n\n// FAST: no copy\nint solve(const vector& nums) { ... }\n\n// FAST: when you need to modify the vector\nvoid solve(vector& nums) { ... }\n```\n\n\n### Avoiding TLE: Common Pitfalls\n\n\n| Pitfall | Slow | Fast | Why |\n|---------|------|------|-----|\n| Passing containers | By value | By `const &` | Avoids O(n) copy per call |\n| Map lookup + access | `if (m.count(k)) x = m[k];` | `auto it = m.find(k); if (it != m.end()) x = it->second;` | One lookup instead of two |\n| String in loop | `s = s + char` (creates new string) | `s += char` or `s.push_back(char)` | In-place append, no copy |\n| Large DP table | `vector>` created each call | Declare once, reuse | Avoids repeated allocation |\n| Using `endl` | `cout << x << endl;` | `cout << x << '\\n';` | `endl` flushes buffer |\n","pageType":"dsa"}

Get Premium