This chapter is a focused crash course on the C++ features you will use repeatedly while learning DSA and preparing for coding interviews. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.

Before we get into the language itself, let us address something practical. On 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:

Each header serves a specific purpose in DSA:

A 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.

C++ is a statically typed language, meaning every variable must have a declared type. For DSA, you will use a small set of types over and over.

The most dangerous pitfall with types in C++ is integer overflow, and it is far more dangerous here than in Java or Python. In Java, overflow wraps around predictably. In Python, integers have arbitrary precision and never overflow. But 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.

Consider the classic binary search:

This is not a theoretical concern. When left and right are both above 1 billion, their sum exceeds int range. In Java, this wraps to a negative number (still a bug, but predictable). In C++, the compiler might optimize the code in ways that make the bug impossible to debug.

When should you use long long instead of int? Four common scenarios:

The 1LL * trick is the idiomatic way to promote an expression to long long before overflow happens:

Notice the placement of the cast. (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.

The size_t Trap

Every STL container's .size() method returns size_t, which is an unsigned integer. This creates a subtle and dangerous bug:

The ternary operator is a compact alternative to if-else that you will use often for inline decisions:

The `auto` keyword lets the compiler deduce the type for you. It is especially useful with iterators and complex types:

Most operators in C++ work as you would expect, but a few deserve special attention for DSA.

Modular arithmetic with % appears in hashing, cyclic array problems, and math-heavy questions. C++11 defines that % can return negative values for negative operands: -7 % 3 gives -1, not 2. To get a positive result:

Many problems ask you to return the result "modulo 10^9 + 7" to prevent overflow in the output:

Bitwise Operations

Bit manipulation problems are common in DSA. Here are the operators and patterns you need:

Common bitmask patterns:

__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

Note that C++ does not have an unsigned right shift operator like Java's >>>. If you need unsigned shift behavior, cast to unsigned int first.

Control Flow and Loops

C++ gives you four loop forms you will use constantly in DSA:

Structured bindings (C++17) let you unpack pairs, tuples, and map entries directly:

Short-circuit evaluation with && and || is critical for bounds checking:

This section covers the most important performance concept in C++ DSA: how you pass arguments to functions.

C++ gives you three ways to pass parameters:

When you pass a vector<int> 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 the single most common C++ performance mistake in coding interviews.

The swap function is built into C++ and works with any type:

Unlike Java where you need a temp variable for array swaps, C++ swap is a single function call.

Lambda Functions

Lambdas are anonymous functions that you will use heavily for custom sort comparators and recursive helper functions. The syntax is:

The capture clause [] controls which variables from the surrounding scope the lambda can access:

Recursive Lambdas with function<>

For recursive helper functions inside a method (common for DFS, backtracking), you need function<> because a lambda cannot refer to itself through auto:

Backtracking Pattern

Here is the classic backtracking template in C++, showing pass-by-reference semantics:

Notice that results.push_back(path) creates a copy of the current path vector. Unlike Java where you must write new ArrayList<>(path) to avoid storing a reference, C++ containers are value types and copy automatically on insertion. This is one area where C++ is actually simpler than Java.

If you are coming from Java or Python, pointers are the biggest new concept you need for C++ DSA. The good news is you only need a small subset of pointer knowledge for coding interviews.

Why Pointers in DSA?

Linked lists and trees are defined using pointers in C++. On LeetCode and in interviews, the node definitions look like this:

The * in ListNode* next means "next is a pointer to a ListNode." A pointer holds the memory address of an object, not the object itself.

Essential Pointer Operations

The arrow operator -> is used to access members through a pointer. It is equivalent to (*ptr).member. You will use -> hundreds of times in linked list and tree problems.

`nullptr` is the C++11 replacement for NULL. Always use nullptr for null pointers. It is type-safe and avoids ambiguity with integer 0.

new and Memory Leaks

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.

Pointers vs References

A 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.

For 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).

C++ 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.

Vector Operations

2D Vectors

The standard way to create a matrix in C++:

DP table initialization follows the same pattern:

4-Directional Movement

Grid problems frequently require visiting neighbors in four directions. Here is the standard pattern:

Useful Vector Operations

C++ std::string has one major advantage over Java and Python strings: it is mutable. You can modify characters in-place without creating a new string.

Essential String Methods

Notice that s == t compares content directly, unlike Java where you must use .equals(). All comparison operators (==, !=, <, >, <=, >=) work on strings in C++ and compare lexicographically.

String-Number Conversions

String Parsing with stringstream

When you need to split a string by spaces or other delimiters:

Character Arithmetic

Character-to-index conversion is the same pattern as Java:

The frequency array pattern appears in dozens of problems:

Character Utility Functions

From <cctype>:

These are especially useful for the "Valid Palindrome" family of problems where you need to ignore non-alphanumeric characters.

The Standard Template Library (STL) is C++'s collection framework. Mastering it is essential for DSA. This section covers every container you will use in coding interviews.

unordered_map -- The HashMap (O(1) Average)

unordered_map is C++'s hash map. You will use it in nearly every other problem for frequency counting, lookups, and memoization.

map[key] auto-inserts a default value if the key is missing. For unordered_map<char, int>, 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++, cleaner than Java's getOrDefault.

Two Sum using unordered_map:

unordered_set -- The HashSet (O(1) Average)

unordered_set stores unique elements with O(1) average lookup. Use it for visited tracking, duplicate detection, and membership testing.

map and set -- The TreeMap and TreeSet (O(log n), Sorted)

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.

The power of map and set lies in their lower_bound and upper_bound methods:

These are equivalent to Java's TreeMap.ceilingKey(), floorKey(), firstKey(), and lastKey().

Use 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.

multiset -- Sorted Set with Duplicates

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.

The biggest multiset pitfall is erase(value) removing ALL occurrences. Always use erase(find(value)) to remove a single occurrence. This mistake appears frequently in sliding window problems.

stack

The stack adaptor provides LIFO access:

Note that pop() returns void, not the removed element. You must call top() before pop() if you need the value. This is different from Java's pop() which returns the element.

queue

The queue adaptor provides FIFO access, used extensively for BFS:

BFS template:

Level-order BFS (processing one level at a time):

deque

deque (double-ended queue) supports O(1) insertion and removal at both ends:

The classic use case is the monotonic deque for sliding window maximum/minimum:

priority_queue -- MAX-Heap by Default!

This is the single most important thing to remember about C++ containers for DSA: `priority_queue` is a MAX-heap by default. This is the opposite of Java's PriorityQueue (min-heap) and Python's heapq (min-heap).

The three template arguments for a min-heap are:

C++ priority_queue is a MAX-heap by default, opposite of Java and Python. To get a min-heap, use priority_queue<int, vector<int>, greater<int>>. Forgetting this in an interview means your Dijkstra returns the longest path instead of the shortest.

Dijkstra's algorithm using a min-heap of pairs:

Note 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.

Containers Quick Reference

Python equivalents marked with `` are from the third-party sortedcontainers library.

Sorting is one of the most frequent operations in DSA. C++ provides sort() from <algorithm>, which uses Introsort (a hybrid of quicksort, heapsort, and insertion sort) and is guaranteed O(n log n).

Sorting Complex Types

Sorting intervals by start time (Merge Intervals pattern):

Sorting by multiple keys:

stable_sort

stable_sort preserves the relative order of equal elements. Use it when the original order matters for elements that compare equal:

nth_element -- O(n) Kth Element

For "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:

Safe Comparators

Unlike Java where comparators return an int and subtraction can overflow (a - b overflows for large values), C++ comparators return bool. This means there is no overflow risk:

C++ has a richer standard algorithm library than Java or Python. The <algorithm> and <numeric> headers provide dozens of functions that eliminate common boilerplate.

Binary Search Family

These work on sorted ranges:

lower_bound and upper_bound together can count occurrences of a value in a sorted range:

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.

Numeric Algorithms

Element Queries

Transformation Algorithms

Iterators 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.

Iterator Basics

Iterator Invalidation Rules

This is one of the most important C++ concepts 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.

Safe Erase Pattern for Maps and Sets

The erase method returns an iterator to the next valid element. Use this in a loop:

This pattern works for map, set, unordered_map, and unordered_set.

Erase-Remove Idiom for Vectors

remove and remove_if from <algorithm> 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:

This is called the erase-remove idiom and is one of the most well-known C++ patterns.

C++20 added erase_if as a cleaner alternative:

In 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"), knowing these patterns is essential.

Recursive 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.

When recursion is too deep, convert to an iterative approach using an explicit stack:

C++ does not reliably optimize tail recursion (it depends on the compiler and optimization level), so do not rely on it.

There are two main ways to represent graphs in C++, and your choice depends on whether node IDs are contiguous integers.

Approach 1: vector<vector<int>> (Contiguous Node IDs)

This is the most common approach when nodes are numbered 0 to n-1:

Approach 2: unordered_map<int, vector<int>> (Sparse/Non-Contiguous IDs)

Use this when node IDs are not contiguous or can be arbitrary values:

Weighted Graphs

For weighted graphs, use pairs to store {neighbor, weight}:

pair is a built-in two-element container that you will use constantly in C++ DSA. Unlike Java, which has no built-in Pair class, C++ pairs are first-class citizens that work with sorting, sets, maps, and priority queues.

pair<T1, T2>

Pairs compare lexicographically (by first element, then second). This is incredibly useful:

tuple<T1, T2, T3>

For three or more elements, use tuple:

For 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).

Two patterns appear frequently for avoiding duplicate results in combination/permutation problems.

Pattern 1: Sort and Skip

Sort the input, then skip consecutive duplicates:

For backtracking problems (like 3Sum or Combination Sum II):

Pattern 2: Sort + unique + Erase

For removing all duplicates from a vector:

Pattern 3: Set-Based

Use a set to track seen combinations:

The sort-and-skip approach is preferred in interviews because it avoids the overhead of a set and is the "standard" technique interviewers expect.

This section collects the small but important patterns that come up repeatedly across DSA problems.

Swap

Sentinel Values

Be 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.

Math Utilities

The 1LL * Trick (Reiterated)

This pattern is so important it deserves repeating:

Type Conversions

Deep Copy

C++ vectors are value types. Assigning one vector to another creates a complete deep copy:

This is different from Java where List<Integer> copy = original just copies the reference. In C++, if you want a reference, use &:

In 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.

ListNode

TreeNode

TrieNode

Graph Node (for problems with custom node structures)

Constructor Initializer Lists

The : 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.

C++ 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.

Fast I/O

For problems with heavy input/output, add these two lines at the start of main:

This 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 is essential for competitive programming and some interview platforms.

reserve() for Vectors

When you know the approximate size of a vector, reserve pre-allocates memory to avoid repeated reallocations:

Pass by const &

This was covered in the functions section, but bears repeating: always pass containers by reference.

Avoiding TLE: Common Pitfalls