Algorithms library essentials

next_permutation, unique, reverse, rotate, min/max, bounds, and small utilities that save minutes in a contest.

next_permutation and prev_permutation

next_permutation(begin, end) transforms the range to the lexicographically next arrangement; returns false if already at last (descending order).

Workflow: sort ascending first, then do { ... } while (next_permutation(a.begin(), a.end())) to enumerate all unique permutations — O(n!) iterations, only viable for small n (typically n ≤ 8–10).

Use cases: brute force orderings, assignment problems tiny enough for exhaustive search.

Example — try all orderings of {1,2,3}:

vector<int> p = {1, 2, 3};
sort(p.begin(), p.end());
int best = INT_MAX;
do {
    int cost = 0;
    for (int i = 0; i + 1 < (int)p.size(); i++)
        cost += abs(p[i] - p[i + 1]);  // example objective
    best = min(best, cost);
} while (next_permutation(p.begin(), p.end()));

Example — prev_permutation (go backward):

vector<int> a = {3,2,1};
if (prev_permutation(a.begin(), a.end())) { /* now previous lex order */ }

unique + erase idiom

unique removes consecutive duplicates, compactifying to the front; returns new “logical” end iterator.

Must sort first if you want globally unique elements:

sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

O(n) after sort dominated by sort cost.

Example — count distinct after compress:

vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
int distinct = (int)b.size();

Example — unique on already grouped data (no sort):

string s = "aaabbbcca";
s.erase(unique(s.begin(), s.end()), s.end());  // "abca"

min, max, minmax, clamp

min / max with initializer lists: min({a,b,c}) (C++11).

minmax(a,b) returns a pair — one comparison instead of two branches.

clamp(x, lo, hi) (C++17) keeps value in interval — readable in solution code.

swap, reverse, rotate — know they exist to avoid off-by-one hand code.

Example — minmax_element on array:

vector<int> a = {3, 1, 4, 1, 5};
auto [mnIt, mxIt] = minmax_element(a.begin(), a.end());
int lo = *mnIt, hi = *mxIt;

Example — clamp:

long long x = stoll(s);
x = clamp(x, 0LL, 1000000LL);

Example — reverse substring / segment:

reverse(s.begin(), s.end());
reverse(a.begin() + l, a.begin() + r + 1);

Example — rotate (circular shift left by k):

int k = 2;
rotate(a.begin(), a.begin() + k, a.end());

accumulate, partial_sum, iota

<numeric> headers:

iota(begin, end, start) fills start, start+1, ... — great for vector<int> id(n); iota(id.begin(), id.end(), 0);
accumulate for sums; watch overflow — use long long initial value: accumulate(a.begin(), a.end(), 0LL).
partial_sum, adjacent_difference for constructive problems.

Example — iota + permutations / indices:

vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) { return w[i] < w[j]; });

Example — safe accumulate:

long long sum = accumulate(a.begin(), a.end(), 0LL);

Example — partial_sum (prefix sums in place):

vector<long long> p = a;
partial_sum(p.begin(), p.end(), p.begin());
// p[i] = a[0]+...+a[i]

Example — adjacent_difference:

vector<int> a = {1, 3, 6, 10};
vector<int> d(a.size());
adjacent_difference(a.begin(), a.end(), d.begin());
// d: 1, 2, 3, 4 (first is a[0])

binary_search

binary_search(begin, end, x) returns bool — true if x exists in sorted range. Often you still want lower_bound to get position.

includes, merge, set_union, set_intersection — occasional geometry / sweep or “two sorted arrays” problems.

Example — binary_search:

sort(a.begin(), a.end());
bool has = binary_search(a.begin(), a.end(), x);

Example — merge two sorted vectors:

vector<int> a = {1,3,5}, b = {2,4,6}, c;
merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
// c = 1,2,3,4,5,6

Example — set_intersection:

vector<int> a = {1,2,3,4}, b = {2,4,6}, out;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));
// out = 2, 4

Complexity mindset

Most <algorithm> routines on iterators are exactly what they claim — log linear for sort, linear for unique/reverse, etc.

Rule: before writing 15 lines of manual indexing, grep your mental STL catalog — the bug surface shrinks.

Complexity Analysis

Time Complexity

Varies: O(n) for unique/reverse; O(n!) permutations if enumerating all

Space Complexity

O(1) extra unless algorithm allocates

accumulate needs 0LL (or wider) to avoid int overflow on sums

Growth Rate Comparison