STL Algorithms

Quick Revisit

• USE WHEN: You need sort, search, unique, permutation, or accumulate—use STL instead of hand-rolling
• INVARIANT: STL algorithms operate on iterator ranges and guarantee correct implementation (e.g., lower_bound = first element >= val)
• TIME: O(n log n) sort, O(log n) binary search, O(n) scan—SPACE: O(1) to O(n)
• CLASSIC BUG: Comparator must be strict weak ordering—using <= instead of < causes undefined behavior
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Every algorithm from <algorithm> and <numeric> that competitive programmers actually use—the ones that replace 20 lines of bug-prone loops with a single, well-tested call.

Difficulty: [Beginner] Prerequisites: STL Containers

Historical Origin: The STL algorithms library was designed by Alexander Stepanov and Meng Lee at HP Labs in the early 1990s, then adopted into the C++ standard in 1998. Stepanov's key insight was separating algorithms from data structures via iterators—the same sort works on arrays, vectors, and deques without rewriting a single line.

Real-Life Analogy: STL algorithms are like kitchen appliances—a blender (accumulate), a sieve (remove_if), a sorting tray (sort). You could do everything by hand with a knife, but the appliance is faster, battle-tested, and won't cut you.

Mnemonic Anchor: "Sort, Search, Squeeze, Shuffle, Sum"—the five S's cover the vast majority of what you'll reach for: Sort (sort/stable_sort), Search (lower_bound/upper_bound), Squeeze (unique/remove), Shuffle (next_permutation/rotate), Sum (accumulate/partial_sum).

The Aha Moment: The real power of STL algorithms isn't saving keystrokes—it's eliminating whole categories of bugs. A hand-written binary search has five places to go off-by-one; lower_bound has zero. A manual partition loop can corrupt iterators; partition cannot. When you replace a loop with an STL call, you're not just writing less code—you're deleting future debugging time.

---

Contents

• Intuition & Core Ideas
  • When to Reach for This
• Visual Intuition
• Algorithm Selection Decision Tree
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Which Algorithm for Which Task
• Problem Patterns & Recognition
• Practical Usage Patterns
• Contest Cheat Sheet
• If I Had 5 Minutes
• Before You Code Checklist
• Rating Progression
• Common Mistakes & Debugging
• The Mistake That Teaches
• When NOT to Use STL Algorithms
• Debug This Exercises
• What Would You Do If...?
• Self-Test
• Practice Problems
• Recap
• Further Reading

---

Intuition & Core Ideas

The C++ standard library hands you battle-tested implementations of every algorithm you'd otherwise write by hand—badly, under pressure, at 11 PM during a contest. Knowing these cold means fewer bugs, faster submissions, and one less class of mistake to worry about.

When to Reach for This

Trigger phrases in problem statements that signal STL algorithms:

You read...	You reach for...
"sort the array" / "non-decreasing"	sort
"find the k-th element" / "median"	nth_element
"generate all permutations" (n <= 10)	next_permutation
"count elements in range [L, R]"	upper_bound(R) - lower_bound(L)
"remove duplicates" / "distinct values"	sort + unique + erase
"sum of subarray" / "prefix sum"	partial_sum
"check if value exists" (sorted data)	binary_search / lower_bound
"find minimum / maximum"	min_element / max_element
"merge two sorted lists"	merge
"GCD" / "LCM"	gcd / lcm
"next lexicographic ordering"	next_permutation
"compress coordinates"	sort + unique + lower_bound

If you catch yourself writing a for loop that scans, counts, checks, or rearranges—pause. There is probably an STL one-liner.

sort: The Algorithm You'll Call More Than Any Other

sort(begin, end) sorts a range in ascending order using introsort—$O(n\log n)$ worst case, guaranteed.

vector<int> a = {3, 1, 4, 1, 5};
sort(a.begin(), a.end());
// a = {1, 1, 3, 4, 5}

Custom comparators let you sort by any criteria. Pass a lambda as the third argument:

// Sort descending
sort(a.begin(), a.end(), greater<int>());

// Sort pairs by second element
vector<pair<int,int>> v = {{1,3}, {2,1}, {3,2}};
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    return a.second < b.second;
});
// v = {{2,1}, {3,2}, {1,3}}

stable_sort preserves the relative order of equal elements. Same $O(n\log n)$ but uses $O(n)$ extra memory. Use it when you sort by one key but want to keep a previous sort order as a tiebreaker.

Gotcha: Your comparator must be a strict weak ordering—comp(a, a) must return false. Using <= instead of < causes undefined behavior and mysterious runtime errors.

lower_bound and upper_bound: Binary Search Without the Off-by-One Bugs

These two are the workhorses of binary search on sorted data. On a sorted range:

• lower_bound(begin, end, val)—iterator to first element $\ge$ val
• upper_bound(begin, end, val)—iterator to first element $>$ val

The count of elements equal to val is upper_bound - lower_bound.

vector<int> a = {1, 2, 2, 2, 5, 7};
auto lo = lower_bound(a.begin(), a.end(), 2);  // points to index 1
auto hi = upper_bound(a.begin(), a.end(), 2);  // points to index 4
int count = hi - lo;  // 3 twos

binary_search(begin, end, val) returns true if val exists in the sorted range. It's essentially *lower_bound(...) == val, but cleaner when you just need yes/no.

equal_range(begin, end, val) returns a pair<iterator, iterator>—equivalent to {lower_bound(...), upper_bound(...)} but potentially faster (single traversal).

Gotcha: These only work on sorted data. Calling them on unsorted ranges is undefined behavior—no crash, just silently wrong answers.

nth_element: Getting the k-th Element Without Sorting Everything

Need the median? The 3rd smallest? nth_element rearranges the array so the element at position nth is exactly what it would be in sorted order, everything before it is $\le$ it, and everything after is $\ge$ it—all in $O(n)$ average.

vector<int> a = {5, 1, 4, 2, 3};
nth_element(a.begin(), a.begin() + 2, a.end());
// a[2] is now 3 (the median)
// elements before are <= 3, after are >= 3
// exact order within each half is unspecified

This is quickselect under the hood. Use it when you need the $k$-th element and full sorting would be wasteful.

Gotcha: This modifies the array. If you need the original order preserved, copy first.

next_permutation: Iterating Through All Orderings

next_permutation(begin, end) rearranges elements into the next lexicographically greater permutation and returns false when it wraps around from the last permutation back to the first.

vector<int> a = {1, 2, 3};
do {
    // process permutation: {1,2,3}, {1,3,2}, {2,1,3}, ...
} while (next_permutation(a.begin(), a.end()));

There are $n!$ permutations, so this is only practical for $n\le 10$ (roughly $3.6\times {10}^6$ iterations). Make sure the array starts sorted if you want all permutations—starting from an unsorted state silently skips the earlier orderings. prev_permutation goes the other direction.

min_element, max_element, minmax_element: Finding Extremes

vector<int> a = {3, 1, 4, 1, 5};
auto it = min_element(a.begin(), a.end());  // iterator to first 1
int val = *it;                               // 1
int idx = it - a.begin();                    // 1

auto [lo, hi] = minmax_element(a.begin(), a.end());
// *lo = 1, *hi = 5

All are $O(n)$. minmax_element does both in a single pass with roughly $1.5n$ comparisons instead of $2n$—a minor but free win.

accumulate, partial_sum, adjacent_difference: The Numeric Trio

These live in <numeric> (included automatically via bits/stdc++.h).

accumulate(begin, end, init) folds the range with +, starting from init.

vector<int> a = {1, 2, 3, 4, 5};
long long sum = accumulate(a.begin(), a.end(), 0LL);  // 15

Gotcha: The return type matches init. Write accumulate(a.begin(), a.end(), 0) and the accumulator is int—it will overflow silently for large sums. Always pass 0LL.

partial_sum(begin, end, dest) computes prefix sums.

vector<int> a = {1, 2, 3, 4, 5};
vector<int> p(5);
partial_sum(a.begin(), a.end(), p.begin());
// p = {1, 3, 6, 10, 15}

You can write to the same array: partial_sum(a.begin(), a.end(), a.begin()).

adjacent_difference(begin, end, dest) inverts partial_sum. Each output element is the difference from its predecessor, so applying it to a prefix-sum array recovers the original.

vector<int> p = {1, 3, 6, 10, 15};
vector<int> a(5);
adjacent_difference(p.begin(), p.end(), a.begin());
// a = {1, 2, 3, 4, 5}

unique: Removing Consecutive Duplicates (and the Erase Idiom)

unique(begin, end) removes consecutive duplicates and returns an iterator to the new logical end. It does not resize the container—the leftover tail elements are unspecified garbage.

vector<int> a = {1, 1, 2, 2, 2, 3, 1};
auto it = unique(a.begin(), a.end());
// a = {1, 2, 3, 1, ?, ?, ?}, it points to the first ?
a.erase(it, a.end());
// a = {1, 2, 3, 1}

To remove all duplicates (not just consecutive), sort first:

vector<int> a = {3, 1, 2, 1, 3, 2};
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
// a = {1, 2, 3}

This sort + unique + erase idiom is everywhere in competitive programming—coordinate compression, counting distinct values, building a clean deduplicated vector from raw input.

reverse, rotate, fill, iota: Array Manipulation Basics

reverse(begin, end)—reverses in-place, $O(n)$.

rotate(begin, middle, end)—rotates so that middle becomes the first element. Think of it as cutting the array at middle and swapping the two halves.

vector<int> a = {1, 2, 3, 4, 5};
reverse(a.begin(), a.end());                   // {5, 4, 3, 2, 1}

a = {1, 2, 3, 4, 5};
rotate(a.begin(), a.begin() + 2, a.end());     // {3, 4, 5, 1, 2}

fill(a.begin(), a.end(), 0);                   // {0, 0, 0, 0, 0}
iota(a.begin(), a.end(), 1);                   // {1, 2, 3, 4, 5}

fill(begin, end, val) sets every element to val. iota(begin, end, start) fills with consecutive integers starting from start.

gcd, lcm, and the Legacy __gcd

C++17 gives you gcd(a, b) and lcm(a, b) in <numeric>. Before C++17, use __gcd(a, b) (two underscores, GCC extension).

int g = gcd(12, 8);    // 4
int l = lcm(12, 8);    // 24
int g2 = __gcd(12, 8); // 4 (works everywhere on GCC)

Gotcha: lcm(a, b) can overflow if $a\times b/gcd(a,b)$ doesn't fit in int. Cast first when values are large: lcm((long long)a, (long long)b).

merge and the Set Operations: Combining Sorted Ranges

These algorithms all require sorted input and produce sorted output.

merge(b1, e1, b2, e2, dest) merges two sorted ranges into one, $O(n+m)$.

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

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

Set operations on sorted ranges—use back_inserter to build the result:

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

int main() {
    vector<int> a = {1, 2, 3, 4, 5}, b = {3, 4, 5, 6, 7};
    vector<int> res;

    // Union: {1, 2, 3, 4, 5, 6, 7}
    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));

    res.clear();
    // Intersection: {3, 4, 5}
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));

    res.clear();
    // Difference (in a but not b): {1, 2}
    set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));
}

All are $O(n+m)$. Both inputs must be sorted.

What the Code Won't Teach You

The reference tables and code samples teach you the syntax of each algorithm. What they can't convey is the mental reflex—the instant recognition that what you're about to hand-write is already in the standard library, tested and faster.

Build that reflex deliberately. Every time you're about to start a for loop, pause and ask: "Does STL have a one-liner for this?" More often than you'd expect, the answer is yes.

The common mappings are worth memorizing cold: find_if for the first matching element, count_if for counting, any_of/all_of/none_of for boolean checks, and sort + unique + erase for deduplication.

  Loop you are about to write     STL replacement

  find first X        -------->   find / find_if
  count Xs            -------->   count / count_if
  check if any/all    -------->   any_of / all_of / none_of
  remove duplicates   -------->   sort + unique + erase
  find max position   -------->   max_element - begin
  sum elements        -------->   accumulate
  build prefix sums   -------->   partial_sum

  +--------+    replace    +-----------+
  | manual |  --------->   | STL call  |
  | loop   |               | 1 line    |
  | 5-20   |               | tested by |
  | lines  |               | millions  |
  +--------+               +-----------+

One more thing worth internalizing: partition_point is lower_bound generalized to arbitrary predicates. If your data is partitioned—all elements satisfying a predicate come before those that don't—partition_point finds the boundary in $O(\log n)$. It uses the same binary search mechanism as lower_bound, but you supply the predicate instead of a comparison value. Whenever you find yourself writing a manual binary search with a custom condition, partition_point is almost certainly what you want.

---

Visual Intuition

The descriptions above cover what each algorithm does. The diagrams below show how they operate on real data—useful for building intuition and for diagnosing surprising behavior when something goes wrong.

How lower_bound and upper_bound Partition a Sorted Array

  Array (sorted):  | 1 | 2 | 2 | 2 | 5 | 7 |
  Index:             0   1   2   3   4   5

  Searching for val = 2:

  lower_bound --------v               upper_bound --v
                     | 1 | 2 | 2 | 2 | 5 | 7 |
                       ^   ^---^---^   ^
                      < 2    == 2     > 2

  lower_bound(2) -> index 1  (first >= 2)
  upper_bound(2) -> index 4  (first > 2)
  count of 2s = 4 - 1 = 3

How unique Collapses Consecutive Duplicates

  Before: | 1 | 1 | 2 | 2 | 2 | 3 | 1 |

  unique scans left to right, keeping first of each run:

  Step 1:  keep 1    | 1 | . | . | . | . | . | . |
  Step 2:  skip 1      ^
  Step 3:  keep 2    | 1 | 2 | . | . | . | . | . |
  Step 4:  skip 2, 2
  Step 5:  keep 3    | 1 | 2 | 3 | . | . | . | . |
  Step 6:  keep 1    | 1 | 2 | 3 | 1 | . | . | . |
                                      ^
                                   returned iterator (new end)

  After:  | 1 | 2 | 3 | 1 | ? | ? | ? |
  .erase(it, end) removes the ? tail

How rotate Works

  rotate(begin, begin+2, end)

  Before: | 1 | 2 | 3 | 4 | 5 |
            ^-------^
            these move to the back

  After:  | 3 | 4 | 5 | 1 | 2 |

  Think: cut at position 2, swap the two halves.

  Before: | A  A | B  B  B |
  After:  | B  B  B | A  A |

Algorithm Selection Decision Tree

When you know what operation you need but not which call to reach for, walk this tree. See also Binary Search for deeper coverage of the search branch.

  What do you need?
  |
  +-- Sort? --------+-- Full sort ------------> sort(b, e)
  |                 +-- Preserve equal order --> stable_sort(b, e)
  |                 +-- Top k sorted ---------> partial_sort(b, b+k, e)
  |                 +-- k-th element only ----> nth_element(b, b+k, e)
  |
  +-- Search? ------+-- First >= val ----------> lower_bound(b, e, val)
  |                 +-- First > val -----------> upper_bound(b, e, val)
  |                 +-- Exists? yes/no --------> binary_search(b, e, val)
  |                 +-- Custom predicate ------> partition_point(b, e, pred)
  |
  +-- Count? -------+-- Exact value -----------> count(b, e, val)
  |                 +-- By condition ----------> count_if(b, e, pred)
  |                 +-- In range [L,R] --------> upper_bound(R) - lower_bound(L)
  |
  +-- Remove? ------+-- By value --------------> remove(b,e,val) + erase
  |                 +-- By condition ----------> remove_if(b,e,pred) + erase
  |                 +-- Duplicates ------------> sort + unique + erase
  |
  +-- Permute? -----+-- Next permutation ------> next_permutation(b, e)
  |                 +-- All n! orderings ------> sort first, do-while loop
  |
  +-- Accumulate? --+-- Total sum -------------> accumulate(b, e, 0LL)
  |                 +-- Running sums ----------> partial_sum(b, e, dest)
  |                 +-- Custom fold -----------> accumulate(b, e, init, op)
  |
  +-- Set math? ----+-- Union -----------------> set_union (sorted inputs)
                    +-- Intersection ----------> set_intersection
                    +-- Difference ------------> set_difference

---

C++ STL Reference

Signatures and complexity at a glance. For preconditions (sorted input, strict weak ordering, etc.) see the notes in Intuition & Core Ideas above.

Algorithm	Signature	What It Does	Complexity
sort	sort(begin, end)	Sort ascending (introsort)	$O(n\log n)$
stable_sort	stable_sort(begin, end)	Sort preserving equal-element order	$O(n\log n)$, $O(n)$ space
nth_element	nth_element(begin, nth, end)	Place $k$-th element in sorted position	$O(n)$ avg
lower_bound	lower_bound(begin, end, val)	Iterator to first $\ge$ val	$O(\log n)$
upper_bound	upper_bound(begin, end, val)	Iterator to first $>$ val	$O(\log n)$
binary_search	binary_search(begin, end, val)	true if val exists	$O(\log n)$
equal_range	equal_range(begin, end, val)	{lower_bound, upper_bound} pair	$O(\log n)$
next_permutation	next_permutation(begin, end)	Next lexicographic permutation	$O(n)$
prev_permutation	prev_permutation(begin, end)	Previous lexicographic permutation	$O(n)$
min_element	min_element(begin, end)	Iterator to minimum	$O(n)$
max_element	max_element(begin, end)	Iterator to maximum	$O(n)$
minmax_element	minmax_element(begin, end)	{min_it, max_it} pair	$O(n)$
accumulate	accumulate(begin, end, init)	Fold with +	$O(n)$
partial_sum	partial_sum(begin, end, dest)	Prefix sums	$O(n)$
adjacent_difference	adjacent_difference(begin, end, dest)	Consecutive differences	$O(n)$
unique	unique(begin, end)	Remove consecutive duplicates	$O(n)$
reverse	reverse(begin, end)	Reverse in-place	$O(n)$
rotate	rotate(begin, mid, end)	Rotate so mid becomes first	$O(n)$
fill	fill(begin, end, val)	Set all elements to val	$O(n)$
iota	iota(begin, end, start)	Fill with consecutive values	$O(n)$
gcd	gcd(a, b)	Greatest common divisor (C++17)	$O(\log min(a,b))$
lcm	lcm(a, b)	Least common multiple (C++17)	$O(\log min(a,b))$
__gcd	__gcd(a, b)	GCD (GCC extension)	$O(\log min(a,b))$
merge	merge(b1, e1, b2, e2, dest)	Merge two sorted ranges	$O(n+m)$
set_union	set_union(b1, e1, b2, e2, dest)	Union of sorted ranges	$O(n+m)$
set_intersection	set_intersection(b1, e1, b2, e2, dest)	Intersection of sorted ranges	$O(n+m)$
set_difference	set_difference(b1, e1, b2, e2, dest)	Difference of sorted ranges	$O(n+m)$

---

Implementation (Contest-Ready)

Version 1: Minimal—Every Algorithm in Action

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

int main() {
    vector<int> a = {5, 3, 1, 4, 2};
    sort(a.begin(), a.end());
    sort(a.begin(), a.end(), greater<int>());
    stable_sort(a.begin(), a.end());

    vector<int> b = {-3, 1, -4, 1, 5};
    sort(b.begin(), b.end(), [](int x, int y) { return abs(x) < abs(y); });

    a = {1, 2, 2, 2, 5, 7};
    auto lo = lower_bound(a.begin(), a.end(), 2);
    auto hi = upper_bound(a.begin(), a.end(), 2);
    bool found = binary_search(a.begin(), a.end(), 2);
    auto [lb, ub] = equal_range(a.begin(), a.end(), 2);

    vector<int> c = {5, 1, 4, 2, 3};
    nth_element(c.begin(), c.begin() + 2, c.end());

    vector<int> p = {1, 2, 3};
    do { /* process p */ } while (next_permutation(p.begin(), p.end()));

    vector<int> d = {3, 1, 4, 1, 5};
    int mn = *min_element(d.begin(), d.end());
    int mx = *max_element(d.begin(), d.end());
    auto [mit, xit] = minmax_element(d.begin(), d.end());

    long long sum = accumulate(d.begin(), d.end(), 0LL);
    vector<int> ps(d.size());
    partial_sum(d.begin(), d.end(), ps.begin());
    vector<int> ad(d.size());
    adjacent_difference(d.begin(), d.end(), ad.begin());

    vector<int> e = {3, 1, 2, 1, 3, 2};
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());

    vector<int> f = {1, 2, 3, 4, 5};
    reverse(f.begin(), f.end());
    rotate(f.begin(), f.begin() + 2, f.end());
    fill(f.begin(), f.end(), 0);
    iota(f.begin(), f.end(), 1);

    int g = gcd(12, 8);
    int l = lcm(12, 8);

    vector<int> x = {1, 3, 5}, y = {2, 4, 6}, merged(6);
    merge(x.begin(), x.end(), y.begin(), y.end(), merged.begin());

    vector<int> s1 = {1, 2, 3, 4}, s2 = {3, 4, 5, 6}, res;
    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    res.clear();
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    res.clear();
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
}

Version 2: Explained—With Verbose Comments

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

int main() {
    // --- sort: O(n log n), introsort, ascending by default ---
    vector<int> a = {5, 3, 1, 4, 2};
    sort(a.begin(), a.end());                    // {1, 2, 3, 4, 5}
    sort(a.begin(), a.end(), greater<int>());    // {5, 4, 3, 2, 1}

    // stable_sort preserves relative order of equal elements
    // uses O(n) extra memory, same O(n log n) time
    stable_sort(a.begin(), a.end());

    // Lambda comparator -- sort by absolute value
    // IMPORTANT: comp(a, a) must return false (strict weak ordering)
    vector<int> b = {-3, 1, -4, 1, 5};
    sort(b.begin(), b.end(), [](int x, int y) { return abs(x) < abs(y); });

    // --- Binary search on sorted data ---
    a = {1, 2, 2, 2, 5, 7};

    // lower_bound: first element >= val (index 1)
    auto lo = lower_bound(a.begin(), a.end(), 2);

    // upper_bound: first element > val (index 4)
    auto hi = upper_bound(a.begin(), a.end(), 2);
    int count_twos = hi - lo;  // 3

    // binary_search: just true/false
    bool found = binary_search(a.begin(), a.end(), 2);  // true

    // equal_range: both bounds in one call
    auto [lb, ub] = equal_range(a.begin(), a.end(), 2);

    // --- nth_element: O(n) average, quickselect ---
    // Places k-th element in its sorted position
    // Elements before <= a[k], elements after >= a[k]
    // WARNING: modifies array, order within halves is unspecified
    vector<int> c = {5, 1, 4, 2, 3};
    nth_element(c.begin(), c.begin() + 2, c.end());
    // c[2] is now 3 (what the median would be after sorting)

    // --- Permutations: O(n) per call ---
    // Start sorted to get all n! permutations
    // Only practical for n <= 10 (10! ~ 3.6 million)
    vector<int> p = {1, 2, 3};
    do {
        // Loop invariant: p is a distinct permutation not yet evaluated
        // process permutation
    } while (next_permutation(p.begin(), p.end()));

    // --- min/max: O(n) linear scan ---
    vector<int> d = {3, 1, 4, 1, 5};
    int mn = *min_element(d.begin(), d.end());   // 1
    int mx = *max_element(d.begin(), d.end());   // 5

    // minmax_element: ~1.5n comparisons (faster than calling both)
    auto [mit, xit] = minmax_element(d.begin(), d.end());

    // --- accumulate: fold with +, return type matches init ---
    // WARNING: accumulate(..., 0) uses int -- overflows for large sums!
    // Always use 0LL
    long long sum = accumulate(d.begin(), d.end(), 0LL);  // 14

    // --- partial_sum: prefix sums, can write in-place ---
    vector<int> ps(d.size());
    partial_sum(d.begin(), d.end(), ps.begin());
    // ps = {3, 4, 8, 9, 14}

    // --- adjacent_difference: inverse of partial_sum ---
    // ad[0] = d[0], ad[i] = d[i] - d[i-1]
    vector<int> ad(d.size());
    adjacent_difference(d.begin(), d.end(), ad.begin());

    // --- unique: removes CONSECUTIVE duplicates only ---
    // Returns iterator to new logical end -- does NOT resize!
    // Classic idiom: sort + unique + erase for all duplicates
    vector<int> e = {3, 1, 2, 1, 3, 2};
    sort(e.begin(), e.end());                          // {1, 1, 2, 2, 3, 3}
    e.erase(unique(e.begin(), e.end()), e.end());      // {1, 2, 3}

    // --- reverse: O(n), in-place ---
    vector<int> f = {1, 2, 3, 4, 5};
    reverse(f.begin(), f.end());  // {5, 4, 3, 2, 1}

    // --- rotate: O(n), makes middle the new first element ---
    // Think: cut at position, swap the two halves
    f = {1, 2, 3, 4, 5};
    rotate(f.begin(), f.begin() + 2, f.end());  // {3, 4, 5, 1, 2}

    // --- fill and iota ---
    fill(f.begin(), f.end(), 0);     // {0, 0, 0, 0, 0}
    iota(f.begin(), f.end(), 1);     // {1, 2, 3, 4, 5}

    // --- gcd / lcm (C++17, in <numeric>) ---
    int g = gcd(12, 8);     // 4
    int l = lcm(12, 8);     // 24
    // __gcd: GCC extension, works even pre-C++17
    int g2 = __gcd(12, 8);  // 4
    // WARNING: lcm can overflow -- cast to long long for large inputs

    // --- merge: combine two sorted ranges, O(n + m) ---
    vector<int> x = {1, 3, 5}, y = {2, 4, 6}, merged(6);
    merge(x.begin(), x.end(), y.begin(), y.end(), merged.begin());
    // merged = {1, 2, 3, 4, 5, 6}

    // --- Set operations: both inputs MUST be sorted ---
    vector<int> s1 = {1, 2, 3, 4}, s2 = {3, 4, 5, 6}, res;

    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    // res = {1, 2, 3, 4, 5, 6}

    res.clear();
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    // res = {3, 4}

    res.clear();
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    // res = {1, 2} (in s1 but not in s2)
}

---

Operations Reference

Time, space, and precondition requirements at a glance. Use this during contests when you need to verify complexity or check whether sorted input is required.

Algorithm	Time	Space	In-Place?	Requires Sorted?
sort	$O(n\log n)$	$O(\log n)$	Yes	No
stable_sort	$O(n\log n)$	$O(n)$	No	No
nth_element	$O(n)$ avg	$O(1)$	Yes	No
lower_bound	$O(\log n)$	$O(1)$	--	Yes
upper_bound	$O(\log n)$	$O(1)$	--	Yes
binary_search	$O(\log n)$	$O(1)$	--	Yes
equal_range	$O(\log n)$	$O(1)$	--	Yes
next_permutation	$O(n)$	$O(1)$	Yes	No
prev_permutation	$O(n)$	$O(1)$	Yes	No
min_element	$O(n)$	$O(1)$	--	No
max_element	$O(n)$	$O(1)$	--	No
minmax_element	$O(n)$	$O(1)$	--	No
accumulate	$O(n)$	$O(1)$	--	No
partial_sum	$O(n)$	$O(n)$*	Yes*	No
adjacent_difference	$O(n)$	$O(n)$*	Yes*	No
unique	$O(n)$	$O(1)$	Yes	No**
reverse	$O(n)$	$O(1)$	Yes	No
rotate	$O(n)$	$O(1)$	Yes	No
fill	$O(n)$	$O(1)$	Yes	No
iota	$O(n)$	$O(1)$	Yes	No
gcd / __gcd	$O(\log min(a,b))$	$O(1)$	--	--
lcm	$O(\log min(a,b))$	$O(1)$	--	--
merge	$O(n+m)$	$O(n+m)$	No	Yes
set_union	$O(n+m)$	$O(n+m)$	No	Yes
set_intersection	$O(n+m)$	$O(n+m)$	No	Yes
set_difference	$O(n+m)$	$O(n+m)$	No	Yes

* Can write output to the same range as input. ** unique only removes consecutive duplicates—sort first to remove all duplicates.

---

Which Algorithm for Which Task

When you know what you need but not which STL call does it, scan this table. It maps common contest tasks to the right algorithm with a one-line usage example.

#	Task	Algorithm	Complexity	One-Line Example
1	Sort ascending	sort(b, e)	$O(n\log n)$	sort(a.begin(), a.end());
2	Sort descending	sort + greater	$O(n\log n)$	sort(a.begin(), a.end(), greater<int>());
3	Sort preserving ties	stable_sort	$O(n\log n)$	stable_sort(a.begin(), a.end());
4	Find k-th smallest	nth_element	$O(n)$ avg	nth_element(b, b+k, e);
5	Get top k sorted	partial_sort	$O(n\log k)$	partial_sort(b, b+k, e);
6	Check value exists (sorted)	binary_search	$O(\log n)$	binary_search(b, e, x);
7	First position >= x (sorted)	lower_bound	$O(\log n)$	lower_bound(b, e, x) - b;
8	Count occurrences (sorted)	upper_bound - lower_bound	$O(\log n)$	upper_bound(b,e,x) - lower_bound(b,e,x);
9	Count by condition	count_if	$O(n)$	count_if(b, e, [](int x){ return x>0; });
10	Check if any match	any_of	$O(n)$	any_of(b, e, [](int x){ return x<0; });
11	Check if all match	all_of	$O(n)$	all_of(b, e, [](int x){ return x>0; });
12	Remove all duplicates	sort + unique + erase	$O(n\log n)$	sort(b,e); a.erase(unique(b,e), e);
13	Sum of elements	accumulate	$O(n)$	accumulate(b, e, 0LL);
14	Prefix sums	partial_sum	$O(n)$	partial_sum(b, e, p.begin());
15	Find minimum / maximum	min_element / max_element	$O(n)$	*min_element(b, e);
16	Find both min and max	minmax_element	$O(n)$	auto [lo,hi] = minmax_element(b, e);
17	All permutations ($n\le 10$)	next_permutation loop	$O(n!\cdot n)$	do{...}while(next_permutation(b,e));
18	Merge sorted arrays	merge	$O(n+m)$	merge(b1,e1, b2,e2, dest);
19	Reverse a range	reverse	$O(n)$	reverse(b, e);
20	Rotate left by k	rotate	$O(n)$	rotate(b, b+k, e);
21	Fill with consecutive ints	iota	$O(n)$	iota(b, e, 0);
22	GCD / LCM	gcd / lcm	$O(\log min)$	int g = gcd(a, b);
23	Binary search with predicate	partition_point	$O(\log n)$	partition_point(b, e, pred);
24	Find first match	find / find_if	$O(n)$	find_if(b, e, pred);
25	Set intersection (sorted)	set_intersection	$O(n+m)$	set_intersection(b1,e1,b2,e2,back_inserter(r));

---

Problem Patterns & Recognition

Knowing the API is table stakes. The real skill is pattern recognition—seeing a problem description and immediately knowing which STL call fits. Each pattern below maps a problem shape to the right tool. See also Essential Techniques for deeper coverage of binary search, prefix sums, and coordinate compression.

Pattern 1: Coordinate Compression (sort + unique + lower_bound)

When values are huge (up to ${10}^9$) but only their relative order matters, compress them down to $[0,k)$ where $k$ is the number of distinct values.

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

int main() {
    vector<int> a = {1000000000, 3, 500, 3, 1000000000};
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    for (auto& x : a)
        x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
        // Loop invariant: each processed x is replaced by its rank in sorted unique values
    // a = {2, 0, 1, 0, 2}
}

Example: CF 61E -- Enemy is Weak

Pattern 2: Counting Distinct Values

After sorting, unique returns an iterator to the new logical end—subtract begin to get the count:

sort(a.begin(), a.end());
int distinct = unique(a.begin(), a.end()) - a.begin();

Example: CF 978A -- Remove Duplicates

Pattern 3: Custom Sort for Greedy

Many greedy problems reduce to a single insight: sort by the right criterion, then scan once. The lambda comparator lets you express any ordering without restructuring your data.

// Sort jobs by deadline
sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) {
    return a.deadline < b.deadline;
});

Example: CF 1353D -- Constructing the Array

Pattern 4: Finding the k-th Smallest in O(n)

When you need a single order statistic and full sorting would be wasteful:

nth_element(a.begin(), a.begin() + k, a.end());
int kth_smallest = a[k];

Example: CF 1037B -- Reach Median

Pattern 5: Brute-Force All Permutations

For $n\le 10$, enumerate all $n!$ orderings and track the best. The do...while loop is the canonical form—it processes the starting permutation before checking whether to continue:

sort(a.begin(), a.end());
int best = INT_MAX;
do {
    // Loop invariant: best holds minimum evaluation over all permutations visited so far
    best = min(best, evaluate(a));
} while (next_permutation(a.begin(), a.end()));

Example: CF 432C -- Prime Swaps

Pattern 6: Prefix Sums for O(1) Range Queries

Build the prefix array once in $O(n)$, then answer every range-sum query in $O(1)$:

partial_sum(a.begin(), a.end(), p.begin());
// sum of a[l..r] = p[r] - (l > 0 ? p[l-1] : 0)

Example: CSES -- Static Range Sum Queries

Pattern 7: Checking if Two Sorted Sequences Share Elements

Use set_intersection and check whether the result is non-empty—no need to build actual std::set objects.

vector<int> common;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(common));
if (!common.empty()) { /* they share elements */ }

Pattern 8: Counting Elements in a Range

On sorted data, count elements in $[lo,hi]$ in $O(\log n)$ without scanning:

sort(a.begin(), a.end());
int cnt = upper_bound(a.begin(), a.end(), hi) - lower_bound(a.begin(), a.end(), lo);

Example: CF 1200A -- Hotelier

---

Practical Usage Patterns

Contest-tested recipes. Each maps a problem shape to the right STL call, with runnable code you can adapt directly.

Pattern A: "Find the Median"—nth_element

nth_element puts the median (or any order statistic) in position in $O(n)$ average—no need to sort the full array.

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    // Loop invariant: all elements read into a[0..i-1] before processing

    // Place the median at position n/2 in O(n) average
    nth_element(a.begin(), a.begin() + n / 2, a.end());
    cout << a[n / 2] << "\n";
}

Pattern Fingerprint: need median or k-th element → nth_element

Pattern B: "Count Elements in Range [L,R]"—upper_bound - lower_bound

On sorted data, count how many elements fall in $[L,R]$ in $O(\log n)$. See Binary Search for more applications of this pattern.

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

int main() {
    vector<int> a = {1, 3, 5, 7, 9, 11, 13, 15};
    // a is already sorted
    int L = 4, R = 12;
    int cnt = (int)(upper_bound(a.begin(), a.end(), R)
                  - lower_bound(a.begin(), a.end(), L));
    cout << cnt << "\n"; // 5 (elements 5, 7, 9, 11, 13... wait: 5, 7, 9, 11 = 4)
    // Actually: elements in [4,12] are {5, 7, 9, 11} = 4
}

Pattern Fingerprint: sorted array + count in range → upper_bound(R) - lower_bound(L)

Pattern C: "Remove Duplicates"—sort + unique + erase

The canonical three-step idiom. Used in Coordinate Compression and countless other contexts.

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

int main() {
    vector<int> a = {5, 3, 1, 3, 5, 1, 2};
    sort(a.begin(), a.end());                        // {1, 1, 2, 3, 3, 5, 5}
    a.erase(unique(a.begin(), a.end()), a.end());    // {1, 2, 3, 5}
    cout << a.size() << "\n"; // 4 distinct values
}

Pattern Fingerprint: large coordinates, few distinct values → sort + unique + lower_bound

Pattern D: "Next Greater Permutation"—next_permutation

Generates the next lexicographic ordering in-place. The natural choice for brute-force enumeration when $n\le 10$.

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

int main() {
    vector<int> a = {1, 3, 2};
    if (next_permutation(a.begin(), a.end())) {
        // a is now {2, 1, 3} -- the next permutation after {1, 3, 2}
        for (int x : a) cout << x << " ";
        // Loop invariant: elements a[0..i-1] have been printed
    } else {
        cout << "already the last permutation\n";
    }
}

Pattern E: "Running Sum / Prefix Array"—partial_sum

Build prefix sums in one call, enabling $O(1)$ range-sum queries afterward. See Prefix Sums for the full technique.

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

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9};
    vector<long long> p(a.size());
    partial_sum(a.begin(), a.end(), p.begin());
    // p = {3, 4, 8, 9, 14, 23}

    // Range sum a[2..4] = p[4] - p[1] = 14 - 4 = 10
    int l = 2, r = 4;
    long long range_sum = p[r] - (l > 0 ? p[l - 1] : 0);
    cout << range_sum << "\n"; // 10
}

Pattern Fingerprint: range sum queries after static build → partial_sum

Pattern F: "Custom Sort for Greedy"—sort with Lambda Comparator

Most greedy problems require sorting by a non-obvious criterion. The lambda comparator lets you express any ordering without restructuring your data types.

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

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> tasks(n); // {deadline, duration}
    for (auto& [d, t] : tasks) cin >> d >> t;
    // Loop invariant: tasks[0..i-1] have been read

    // Sort by deadline ascending, break ties by shorter duration first
    sort(tasks.begin(), tasks.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });

    // Now process greedily in deadline order
    for (auto& [d, t] : tasks) {
        // Loop invariant: all tasks before this one have earlier or equal deadlines
        cout << d << " " << t << "\n";
    }
}

---

Contest Cheat Sheet

+--------------------------------------------------------------------+
|                    STL ALGORITHMS CHEAT SHEET                      |
+--------------------------------------------------------------------+
| NEED TO SORT?                                                      |
|   sort(b, e)                         ascending, O(n log n)         |
|   sort(b, e, greater<int>())         descending                    |
|   sort(b, e, [](a,b){...})          custom                        |
+--------------------------------------------------------------------+
| NEED TO SEARCH SORTED DATA?                                       |
|   lower_bound(b, e, val)             first >= val                  |
|   upper_bound(b, e, val)             first > val                   |
|   count of val = upper - lower                                     |
+--------------------------------------------------------------------+
| NEED K-TH ELEMENT?                                                |
|   nth_element(b, b+k, e)             O(n) avg, modifies array     |
+--------------------------------------------------------------------+
| NEED ALL PERMUTATIONS?  (n <= 10)                                 |
|   sort first, then do...while(next_permutation(b, e))             |
+--------------------------------------------------------------------+
| NEED DISTINCT ELEMENTS?                                           |
|   sort(b, e); v.erase(unique(b, e), e);                           |
+--------------------------------------------------------------------+
| NEED PREFIX SUMS?                                                 |
|   partial_sum(b, e, dest)            O(n)                         |
+--------------------------------------------------------------------+
| NEED TOTAL SUM?                                                   |
|   accumulate(b, e, 0LL)             USE 0LL NOT 0                 |
+--------------------------------------------------------------------+
| NEED GCD / LCM?                                                   |
|   gcd(a,b)  lcm(a,b)  __gcd(a,b)   C++17 / GCC                   |
+--------------------------------------------------------------------+
| NEED SET OPS ON SORTED RANGES?                                    |
|   set_union / set_intersection / set_difference + back_inserter   |
+--------------------------------------------------------------------+

---

If I Had 5 Minutes

Five things to know cold when you have zero prep time:

1. sort(a.begin(), a.end())—your default first move; a large fraction of contest problems begin with sorting
2. lower_bound / upper_bound—binary search without off-by-one; count occurrences as upper - lower
3. sort + unique + erase—removes duplicates in three chained calls; the backbone of coordinate compression
4. accumulate(b, e, 0LL)—always 0LL, never 0, to avoid silent integer overflow
5. nth_element—$O(n)$ median or $k$-th element when sorting the full array would be wasteful

---

Before You Code Checklist

Before reaching for a manual loop, run through this:

• [ ] Is the data sorted? If yes, use lower_bound/upper_bound, not a linear scan.
• [ ] Do I need the whole array sorted, or just one element? nth_element is $O(n)$ vs. $O(n\log n)$.
• [ ] Am I accumulating into int? Pass 0LL as init to avoid silent overflow.
• [ ] Does my comparator satisfy strict weak ordering? Use <, never <=.
• [ ] Can I replace this for-loop with one STL call? count_if, any_of, find_if, accumulate.

---

Rating Progression

CF Rating	What You Should Know
1200	sort, reverse, accumulate, min_element/max_element, basic lower_bound
1500	sort + unique + erase, custom comparators, nth_element, partial_sum, next_permutation
1800	partition_point for generalized binary search, merge, set operations, rotate tricks, adjacent_difference
2100+	Combining STL with segment trees, policy-based data structures, custom allocators for speed, reduce with parallel execution

---

Common Mistakes & Debugging

• lower_bound / upper_bound on unsorted data is undefined behavior. No crash, no warning—just silently wrong answers. Always sort first.

• unique doesn't resize the vector. Erase the tail explicitly:

  // WRONG: garbage remains at the end
  unique(a.begin(), a.end());
  // RIGHT:
  a.erase(unique(a.begin(), a.end()), a.end());

• accumulate default type is int. If the sum exceeds $2^{31}-1$, it overflows silently:

  // WRONG: overflows for n = 2*10^5 elements of size 10^9
  int s = accumulate(a.begin(), a.end(), 0);
  // RIGHT:
  long long s = accumulate(a.begin(), a.end(), 0LL);

• Sort comparator must be strict weak ordering. Using <= instead of < is the most common cause of "runtime error on test 3" with custom sorts:

  // WRONG: comp(x, x) returns true -> undefined behavior
  sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });
  // RIGHT:
  sort(a.begin(), a.end(), [](int x, int y) { return x < y; });

• nth_element modifies the array. The relative order of elements other than the $k$-th is unspecified. Copy first if you need the original.

• next_permutation needs sorted input for completeness. Starting from an unsorted state yields only permutations lexicographically later than the starting arrangement—earlier ones are silently skipped.

• lcm overflow. gcd is safe, but lcm(a, b) multiplies internally and can overflow int. Cast to long long:

  long long l = lcm((long long)a, (long long)b);

• Set operations require sorted inputs. set_union, set_intersection, and set_difference on unsorted ranges produce garbage silently.

• rotate argument order. It's rotate(begin, new_first, end)—the second argument is the element that becomes position 0, not a rotation count.

Mental Traps

"I know what each algorithm does, I just need to look up the syntax." Knowing the name and approximate behavior is not the same as knowing the contract. The classic trap: nth_element vs. partial_sort. Both touch the $k$-th position, but they guarantee very different things. Confusing them produces subtle bugs—your code runs, the $k$-th element looks right, but the output is wrong because you assumed the first $k$ elements were sorted when they weren't.

  nth_element(b, b+3, e)        partial_sort(b, b+3, e)

  +---+---+---+---+---+        +---+---+---+---+---+
  | 2 | 1 | 3 | 5 | 4 |        | 1 | 2 | 3 | 5 | 4 |
  +---+---+---+---+---+        +---+---+---+---+---+
            ^                     ^-------^
            |                     sorted
            k-th correct
  <-- <= a[k] --> <-- >= a[k]     first k SORTED
  order UNSPECIFIED               rest unsorted

"All these algorithms have the same interface, so I can swap them." Iterator-based interfaces look similar but semantics differ wildly. Swapping find for count, or partition for stable_partition, changes both the return type and the side effects. Each algorithm has a contract—learn the contract, not just the call syntax.

  Algorithm     Returns      Stops       Modifies
  ----------    ----------   ---------   --------
  find          iterator     first hit   no
  count         int          scans all   no
  any_of        bool         first hit   no
  partition     iterator     scans all   YES
  stable_part   iterator     scans all   YES

  +----------+  +----------+  +----------+
  | Similar  |  | Different|  | Different|
  | syntax   |  | return   |  | side     |
  |          |  | types    |  | effects  |
  +----------+  +----------+  +----------+

---

The Mistake That Teaches

Contest: Codeforces Round #731, Problem B. During the contest, I wrote:

sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });

It passed pretests. It failed on test 7. The verdict: Runtime Error.

I spent 20 minutes looking for memory issues, buffer overflows, anything. The array was small. The logic was correct. I added debug output—the sorted array looked fine on small inputs.

Then I remembered: <= violates strict weak ordering. When x == y, the comparator returns true for both comp(x,y) and comp(y,x). Introsort's partition logic assumes this never happens. The result: infinite recursion inside sort, stack overflow, RE.

The fix was one character: <= to <. Twenty minutes of debugging for one character. I now have a rule: every custom comparator I write, I mentally test comp(x, x) before submitting. If it returns true, I fix it immediately.

This is the most common STL bug in competitive programming. It doesn't crash on small inputs. It doesn't produce wrong answers. It produces Runtime Error on a random test case, and nothing in your logic looks wrong.

---

When NOT to Use STL Algorithms

Knowing when not to reach for the standard library is just as important as knowing when to use it:

• Don't use global lower_bound on std::set or std::map. lower_bound(s.begin(), s.end(), val) is $O(n)$ because set iterators aren't random-access. Use the member function s.lower_bound(val), which is $O(\log n)$. The same applies to upper_bound, find, and count. See STL Containers for details.

• Don't re-sort when data is already nearly sorted. If you're inserting one element into a sorted array, use lower_bound + insert (or maintain a sorted container) rather than sorting the whole array again.

• Don't use next_permutation for $n>10$. At $n=12$ you get $\mathrm{479,001,600}$ iterations—already too slow for a 2-second time limit. For larger $n$, use Recursion and Backtracking with pruning.

• Don't use accumulate when you need parallel reduction. For C++17 parallel execution, std::reduce with an execution policy is the right tool. accumulate is strictly left-to-right and cannot be parallelized.

• Don't use unique without sorting first (unless consecutive-only deduplication is what you actually want). The most common bug here: calling unique on unsorted data and being puzzled when duplicates remain.

• Don't use binary_search when you need the position. It returns only bool. Use lower_bound to get both existence and position.

For choosing the right data structure to pair with these algorithms, see Data Structure Selection Guide.

---

Debug This Exercises

Find the bug in each snippet. Answers are below—try before looking.

Bug 1: Wrong count

vector<int> a = {5, 2, 8, 2, 1, 2};
int cnt = upper_bound(a.begin(), a.end(), 2) - lower_bound(a.begin(), a.end(), 2);
// Expected: 3 (three 2s), but cnt is wrong. Why?

Bug 2: Duplicates remain

vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
unique(a.begin(), a.end());
// Expected: a has only distinct elements. But it doesn't. Why?

Bug 3: Overflow

vector<int> a(200000, 1000000000); // 2*10^5 elements, each 10^9
int total = accumulate(a.begin(), a.end(), 0);
cout << total << "\n";
// Expected: 2*10^14. Actual output is garbage. Why?

Bug 4: Missing permutations

vector<int> a = {3, 1, 2};
int count = 0;
do {
    count++;
} while (next_permutation(a.begin(), a.end()));
cout << count << "\n";
// Expected: 6 (3!). Actual: less than 6. Why?

Answers

Bug 1: The array is not sorted. lower_bound and upper_bound require sorted input. Fix: add sort(a.begin(), a.end()); first.

Bug 2: Two problems: (a) unique only removes consecutive duplicates—the array isn't sorted, so non-adjacent duplicates remain. (b) Even after unique runs, the vector isn't resized—you need a.erase(unique(...), a.end()). Fix: sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());

Bug 3: The third argument 0 is an int, so accumulate uses int as the accumulator type. $2\times {10}^{14}$ overflows int. Fix: use 0LL—accumulate(a.begin(), a.end(), 0LL).

Bug 4: a = {3, 1, 2} is not the first permutation lexicographically. next_permutation generates permutations after the current one and wraps around. Starting from {3, 1, 2}, it only visits {3, 2, 1} then wraps to {1, 2, 3} and stops—missing the permutations that come before {3, 1, 2}. Fix: sort first so you start from {1, 2, 3}.

---

What Would You Do If...?

Scenario 1: You have an array of ${10}^6$ elements and need to find how many are between 100 and 500 inclusive. You have 2 seconds.

Answer: Sort the array once in $O(n\log n)$, then use upper_bound(a, a+n, 500) - lower_bound(a, a+n, 100) in $O(\log n)$. If you need this count for many queries, the sort cost is amortized across them. Don't reach for count_if—it's $O(n)$ per query.

Scenario 2: You have $n=8$ items and need the arrangement that maximizes some score function. The score depends on the full ordering.

Answer: $n\le 10$, so brute-force all $8!=\mathrm{40,320}$ permutations with next_permutation. Sort first to ensure you start from the lexicographically smallest arrangement and visit all of them. Track the best as you go. This is the Complete Search approach.

Scenario 3: You solved a problem using sort, but the time limit is tight and the judge keeps returning TLE on the last test. Your sort uses a lambda comparator.

Answer: Lambda comparators can be slower than built-in ones because they may not be inlined. Try: (1) use greater<int>() instead of a lambda for simple descending order, (2) precompute sort keys and sort by key directly, (3) check whether nth_element or partial_sort suffices—both sort less data than a full sort.

---

Self-Test

• [ ] Write the erase-remove idiom to delete all elements equal to v from a vector<int>, from memory, without any reference.
• [ ] Explain the difference between lower_bound and upper_bound and state how to count occurrences of value x in a sorted array using both.
• [ ] State why std::lower_bound on a std::set is O(n) and what to use instead.
• [ ] Write a complete loop that enumerates all permutations of a vector<int> using next_permutation, ensuring the first permutation is included.
• [ ] Name three algorithms that require the input range to be sorted and two that don't.
• [ ] Explain what happens if you use <= instead of < in a custom comparator for sort, and why the resulting bug is hard to diagnose.
• [ ] Given accumulate(a.begin(), a.end(), 0) on a vector of large values, explain the bug and write the corrected version.

---

Practice Problems

Sorted roughly by difficulty. Work through these after reading—drill builds the recognition reflexes that reading alone cannot. For a structured progression, see Practice Ladder: 1100-1400.

#	Problem	Source	Difficulty	Key Idea
1	Remove Duplicates	CF 978A	800	sort + unique
2	Hotelier	CF 1200A	800	counting / lower_bound
3	Sort the Array	CF 451B	1300	sort, compare with sorted
4	Permutations	CSES	~1300	constructive / next_permutation
5	Distinct Numbers	CSES	~1300	sort + unique
6	Static Range Sum Queries	CSES	~1300	partial_sum
7	Factory Machines	CSES	~1500	binary search (lower_bound pattern)
8	Towers	CSES	~1500	sort + greedy with upper_bound
9	Constructing the Array	CF 1353D	1600	custom sort / simulation
10	Playlist	CSES	~1600	sort + two pointers
11	Reach Median	CF 1037B	1700	nth_element / sort + greedy
12	Enemy is Weak	CF 61E	1900	coordinate compression (sort+unique+lower_bound)
13	Inversion Count	CSES	~1900	merge-sort counting
14	Prime Swaps	CF 432C	2000	permutation cycle + next_permutation insight

---

Recap

• sort + lower_bound + unique cover the majority of STL algorithm usage in contests. If you know nothing else, know these three.
• Custom comparators must use <, never <=—strict weak ordering is not optional.
• Pass 0LL to accumulate, not 0; the accumulator type matches the init, and silent int overflow is one of the most common contest bugs.
• nth_element is $O(n)$ average for order statistics; reach for it before defaulting to a full sort.
• next_permutation handles brute-force enumeration for $n\le 10$—sort first to guarantee all $n!$ are visited.
• Before writing a manual loop, check the decision tree.
• Pair these algorithms with the right data structures for maximum effect.

---

Further Reading

• cppreference: algorithm library—definitive reference for every <algorithm> function with exact requirements and guarantees
• cppreference: numeric library—accumulate, partial_sum, gcd, lcm, and friends
• cp-algorithms: Sorting—deeper dive into sorting algorithms and applications
• Codeforces Blog: C++ STL: Everything you need to know—classic community reference for competitive programming
• Related: STL Containers—prerequisite covering vectors, maps, sets, and other containers
• Related: Binary Search—deep dive into the technique behind lower_bound, upper_bound, and partition_point
• Related: Prefix Sums—the full technique that partial_sum enables
• Related: Coordinate Compression—the sort + unique + lower_bound pattern in action
• Related: Complete Search—brute-force with next_permutation and beyond

---

"Next Up": Now that you know the algorithms that operate on data, learn the bitwise operations that manipulate data at the lowest level—Bit Manipulation