Practice: Standard Library Algorithms

Eleven problems for the toolbox. Before writing a loop, ask which function already does it — and which ones need the data sorted first.

• Count Occurrences: count over 10⁷ numbers; read into a vector<int>.
• Extremes with Indices and Minimum and Position: min_element and max_element give the position of the first smallest and largest, which is what both ask for. Values reach 10¹⁸ in the second one.
• All Maximum Positions: *max_element for the value, then one pass to collect every index that holds it.
• Distinct Sorted Values: sort, unique, erase, print.
• Frequency Table and Equal Coordinates: sort, then walk the runs of equal values — or equal pairs, which compare with == like anything else.
• Coordinate Compression: the sorted distinct values are a dictionary; the rank of a[i] is lower_bound(v.begin(), v.end(), a[i]) - v.begin().
• Funky Numbers: list the triangular numbers up to n (about 45 000 of them), and for each one binary_search for n minus it.
• Anagram Groups: pair each word with its sorted letters, {key, word}; sorting the pairs puts every group together, in alphabetical order inside the group. Then walk the runs of equal keys.
• Count Valid Triangles: sort the lengths; for each pair i < j, the valid third sides are the a[k] with k > j and a[k] < a[i] + a[j] — one lower_bound on the part after j counts them. n ≤ 2000, so n² searches fit.