Basics

The time complexity of a program tells you how fast its number of steps grows as the input gets bigger. Make the input 10 times longer, and one program makes the same number of steps, another 10 times more, and a third 100 times more. Knowing it, you can tell whether an algorithm is fast enough for the input sizes you expect, before you write any code.

An array keeps $n$ values in cells with indices 0 to n - 1, and reads or changes any cell by its index in $O(1)$ time. A vector is the C++ array that knows its size and can grow at the end.

A grid is a table of cells, such as a maze, a game board or a map, usually given as rows of characters. Most grid problems need the neighbours of a cell, visited with one loop over a short list of moves and a check that each neighbour is inside the grid. To find the shortest route through a maze, see BFS.

A string stores text as a row of characters numbered from 0; in C++ it is std::string. To find a pattern in a text of millions of characters, see the prefix function.

A pair keeps two values together as one value, and a tuple keeps any fixed number of them. They compare element by element: sort, min and max order them by the first element and use the next one only to break ties. Use them for a small record of two or three values that must be sorted or compared; for more values, a struct with a comparator reads better.

A floating-point number, such as double in C++, stores a number with a fraction (3.5, 0.1, 66.6667) using a fixed number of digits, about 15–16. Most fractions are stored only approximately, so solutions compare doubles with a small tolerance and print them with a fixed number of digits after the point. If every value in the problem is an integer, keep it in an integer type, which is exact.

A number system writes a number with digits whose worth depends on their place. Turning digits in base $b$ into a value, and back, takes one short loop each way. Look for it when a problem says "in base $k$", "binary representation" or "the number of ones in binary", or writes numbers with letters as digits.

A big integer is a number stored as an array of its digits, and the program adds and multiplies such numbers column by column, the way it is done on paper. It is needed when a problem asks for every digit of a number beyond long long, which stops at about 9.2 \cdot 10^{18} (see integer types). If only the remainder of the answer is needed, use modular arithmetic instead.

Brute force solves a problem by trying every possible answer and checking each one. It works when there are few enough possible answers to try them all within the time limit. It also helps test a faster solution: run both programs on many small random inputs and compare their answers.

Sorting puts the elements of an array in order: numbers from smallest to largest, names from A to Z, or by any rule you choose, such as "higher score first, equal scores by name". It is useful in many places: once an array is sorted, finding the two closest numbers, counting the different values or searching for a value becomes quick. Common sorting algorithms are bubble sort, insertion sort, merge sort, quicksort and counting sort.

Counting sort puts numbers, or records with a number as their key, in order by counting how many times each value occurs. It works when the values are small whole numbers, such as marks from 0 to 100; for large or arbitrary values, use std::sort.

Coordinate compression replaces every value by its place among the distinct values in sorted order: the smallest value becomes 0, the next one 1, and so on. An array indexed by value then needs only as many cells as there are distinct values. Use it when the values are large (up to 10^9, negative, or not integers) but few, say n \le 2 \cdot 10^5, an array indexed by value would help, and only which values are equal or smaller matters.

Prefix sums let a program answer many questions of the form "what is the sum of elements $l$ to $r$?" with one subtraction each, after one pass over the array. If the values change between the questions, use a Fenwick tree instead.

2D prefix sums let a program answer many questions of the form "what is the sum of this rectangle of a table?" with four terms each, after one pass over the table. They work when the table doesn't change between the questions. If cells change in between, use a 2D Fenwick tree instead.

A difference array applies many changes of the form "add x to every element from l to r" with two small writes each, and one running total at the end gives the final array. If the values must be read between the changes, use a Fenwick tree instead.

Binary search finds a number in a sorted array, or the place where it would go, by looking at the middle and throwing away the half that can't hold it. The same loop finds the longest length or the shortest time that still passes a yes/no check. To find the highest point of a function that goes up and then down, use ternary search instead.

Ternary search finds the top (the highest point) of an array or a function that rises and then falls, or the lowest point of one that falls and then rises, with two looks per round. If the question is where a sorted array or a yes/no check turns from "no" to "yes", use binary search instead.

The two pointers technique finds the longest run of consecutive elements of an array whose sum stays within a limit, or a pair with a given sum in a sorted array, by moving two indices that each go in one direction only. It replaces a double loop of n^2 steps with one pass of at most $2n$. The run search needs elements that are not negative; with negative numbers it can skip the answer.

A sweep line walks along a line through the points where intervals start or end, in sorted order, and keeps track of what is open between them. It handles $n$ intervals in O(n \log n) time, however large the coordinates are. If the coordinates are small (up to about 10^6), a difference array over every unit of the line is simpler. Reach for a sweep when a problem has intervals (time periods, buildings) and the answer depends on how many, or which, are open at each place.

Recursion solves a problem with a function that calls itself on a smaller problem of the same kind and combines the answers. It fits problems that contain copies of themselves, such as folders inside folders, or a formula defined through its own smaller values.

A bitmask stores a set of items in one integer: bit $i$ is 1 if item $i$ is in the set. One int holds up to 31 items and a long long up to 63. Because every set is a number, one loop over the numbers from $0$ to 2^n - 1 goes through every subset, which solves "try every subset" problems with n \le 20 without recursion.

A greedy algorithm builds an answer step by step, each time taking the choice that looks best right now and never taking it back. It is usually a sort and one pass, so its time complexity is O(n \log n), but it gives the right answer only for some problems. When a choice can turn out wrong later, use dynamic programming instead.

Backtracking lists every arrangement that obeys a rule: every order of some numbers, every subset, every way to put queens on a chessboard so that none attacks another. If a problem asks only how many arrangements there are and that number is huge, count them with dynamic programming instead.