Skip to content

Expert · Competitive programming, interviews and careers · topic 39 of 42 · 40 min

Core DSA patterns in C++

Explanation

A handful of patterns solve a large share of placement and contest problems: prefix sums, two pointers, binary search (including on the answer), hashing with maps and sets, BFS and DFS on graphs, and simple dynamic programming. Learn each pattern with its C++ STL tools and its time complexity.

Why patterns?

Most problems are variations of a few ideas. When you can recognise the pattern ("sum of a range many times? prefix sums"), the C++ code is short because the STL does the heavy lifting. DSA means Data Structures and Algorithms.

1. Prefix sums: fast range sums

cpp
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i];
// sum of a[l..r] (inclusive, 0-based) = pre[r + 1] - pre[l], in O(1) per query
O(n) to build, O(1) per query, instead of O(n) per query.

2. Two pointers on sorted data

cpp
// Does a sorted array have two values adding up to target?
int i = 0, j = n - 1;
while (i < j) {
    long long s = a[i] + a[j];
    if (s == target) { /* found */ break; }
    if (s < target) ++i; else --j;
}
Each step moves one pointer, so it is O(n) instead of O(n²) for checking all pairs.

3. Binary search on the answer

If a yes/no question "can we do it with value X?" switches from no to yes at one point as X grows, you can binary search X. Example: the smallest daily speed that finishes reading all chapters in D days. Each check is O(n), and binary search needs about 30–60 checks, so the total is O(n log maxValue).

cpp
long long lo = 1, hi = 1'000'000'000;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;      // avoids overflow of (lo + hi)
    if (canFinish(mid)) hi = mid; else lo = mid + 1;
}
// lo is the smallest value for which canFinish is true
A standard template: keep the answer inside [lo, hi] and shrink by half.

4. Hashing: seen before?

cpp
unordered_map<long long, int> seenAt;           // value -> index
for (int i = 0; i < n; ++i) {
    if (auto it = seenAt.find(target - a[i]); it != seenAt.end()) {
        cout << it->second << ' ' << i << '\n';  // the "two sum" problem in O(n)
        break;
    }
    seenAt[a[i]] = i;
}
Maps and sets turn "search the whole array again" into O(1) average lookups.

5. Graphs: BFS and DFS

cpp
// Shortest path in an unweighted graph with BFS
vector<vector<int>> adj(n);                   // adjacency list
vector<int> dist(n, -1);
queue<int> q;
dist[src] = 0;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}
BFS visits nodes in order of distance. It runs in O(V + E). For weighted graphs, use Dijkstra with a min priority_queue.

DFS (depth-first search) goes deep before backtracking, using recursion or a stack. It finds connected components, detects cycles and drives topological sort. For n up to about 10^5, an iterative DFS avoids stack overflow from deep recursion.

6. Dynamic programming (DP)

cpp
// Number of ways to climb n stairs taking 1 or 2 steps at a time
vector<long long> ways(n + 1, 0);
ways[0] = 1;
for (int i = 1; i <= n; ++i) {
    ways[i] = ways[i - 1] + (i >= 2 ? ways[i - 2] : 0);
}
DP stores answers to smaller sub-problems in a table so each is computed once.
Think of it like this: DP is like a student who writes each solved sum in a notebook. When the same sum appears again in a bigger problem, she copies the answer from the notebook instead of solving it again. Plain recursion is the student who re-solves everything from scratch every time.

Pattern finder

Clue in the problemTry
Many range-sum queries on a fixed arrayprefix sums
Sorted array, pairs or windowstwo pointers / sliding window
"Minimum X such that…" with a monotonic checkbinary search on the answer
"Have we seen…", counting frequenciesunordered_map / set
Grid or network, fewest stepsBFS
Count ways / best value from choices that overlapdynamic programming
Always pick the current bestgreedy, often with sort or priority_queue
Tip: The tasks below are in Python because they run right here in the browser; the ideas are exactly the same in C++. Write the C++ version on your computer afterwards.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Core DSA patterns in C++ · 1/6

DSA patterns

A few patterns solve most coding round problems. Learn to recognise them.

Prefer a video by a teacher? Find free videos on “dsa patterns prefix sum two pointers binary search on answer bfs c++” on YouTube ↗

In real life: Metro route planning

A city metro app answers "fewest stations from A to B". Stations are nodes and direct links are edges, so it is a breadth-first search on an unweighted graph. For "fastest by minutes", each edge gets a travel time and the app switches to Dijkstra's algorithm with a min priority_queue.

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

int main() {
    int n = 5;                                   // stations 0..4
    vector<vector<int>> adj(n);
    auto link = [&](int a, int b) { adj[a].push_back(b); adj[b].push_back(a); };
    link(0, 1); link(1, 2); link(2, 3); link(0, 4); link(4, 3);
    vector<int> dist(n, -1);
    queue<int> q;
    dist[0] = 0; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    cout << dist[3] << '\n';                     // 2 (0 → 4 → 3)
}
BFS finds the route 0 → 4 → 3 with 2 hops instead of 0 → 1 → 2 → 3.

Practice (0/4 done)

Task 1 · Code · Python

Prefix sums (in Python, same idea as C++): write range_sums(nums, queries) where queries is a list of (l, r) pairs, 0-based and inclusive. Return a list with the sum of nums[l..r] for each query. Build a prefix array once so each query is O(1).

Task 2 · Code · Python

Two pointers: nums is sorted in increasing order. Write pair_with_sum(nums, target) that returns a tuple (i, j) with i < j and nums[i] + nums[j] == target, or None if there is no such pair. Use one pointer at each end (O(n)).

Task 3 · Question

A grid maze asks for the minimum number of moves from start to exit. Which algorithm fits?

Task 4 · Practice

In C++ on your computer, solve these CSES problems: "Static Range Sum Queries" (prefix sums), "Sum of Two Values" (hashing or two pointers) and "Labyrinth" (BFS on a grid). Write the pattern used at the top of each file as a comment.

Quick quiz

Question 1

1.After building prefix sums once, how long does one range-sum query take?

Question 2

2.Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?

Question 3

3.What is the time complexity of BFS with an adjacency list?

Question 4

4.What makes dynamic programming faster than plain recursion for problems like Fibonacci?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

After building prefix sums once, how long does one range-sum query take?

Answer: O(1)

It is a single subtraction.

Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?

Answer: It avoids overflow when lo + hi is larger than the type can hold

lo + hi can overflow for large values; the difference cannot.

What is the time complexity of BFS with an adjacency list?

Answer: O(V + E)

Each vertex and edge is processed a constant number of times.

What makes dynamic programming faster than plain recursion for problems like Fibonacci?

Answer: Each sub-problem's answer is stored and reused instead of recomputed

Overlapping sub-problems are solved once.

What is the time complexity of binary search?Related

Answer: O(log n)

The search range halves every step.

From Data-structure questions in JavaScript

Directed edges 0→1, 0→2, 1→3, 2→3. A DFS from 0 meets vertex 3 a second time. Is there a cycle?Related

Answer: No: 3 is finished (black), not on the current path

Only an edge to a grey vertex (on the current path) closes a cycle. This is a diamond.

From Depth-first search (DFS)

Which answer about std::move is correct?Related

Answer: It is a cast to an rvalue; the actual move happens in the move constructor or assignment

std::move itself does no work at run time.

From C++ interview questions and how to answer them

A perfect binary tree has n nodes. What is the worst extra space of BFS on it?Related

Answer: O(n), because the last level holds about n/2 nodes

The queue holds a whole level at a time, and the bottom level of a perfect tree has about half of all nodes.

From Traversals: DFS and BFS

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Classic C++ pitfalls in contests and coding rounds →

Next steps

  1. 3 more topics in “Competitive programming, interviews and careers” before its exam: Classic C++ pitfalls in contests and coding rounds, C++ interview questions and how to answer them, Careers with C++ and your next steps.
  2. Module 10 exam: Contests, interviews and careers · 12 questions · 20 min, without help. 5 topics of this module still to finish first.
  3. 42 topics left in the course before the final exam.

← Previous: Competitive programming with C++: setup and time limits