Chapter 10 of 30
Sorting & Frequency Arrays
Master std::sort, binary search in STL, permutation generation, and frequency counting techniques.
std::sort — The Workhorselower_bound & upper_bound — Binary Search in STLbinary_search — Boolean Existence Checkunique — Removing Consecutive Duplicatesnext_permutation — Generating PermutationsSorting ApplicationsFrequency Counting
Share:
Sorting & Frequency Arrays
Sorting transforms a problem. Many hard problems become easy once you sort the input. This chapter covers STL sorting, binary search on sorted ranges, and the frequency counting patterns that appear everywhere.
std::sort — The Workhorse
hljs cpp
vector<int> v = {3, 1, 4, 1, 5, 9};
// Ascending (default)
sort(v.begin(), v.end()); // {1, 1, 3, 4, 5, 9}
// Descending
sort(v.begin(), v.end(), greater<int>()); // {9, 5, 4, 3, 1, 1}
Custom Comparators
hljs cpp
// 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;
});
// Sort strings by length
vector<string> words = {"hi", "hello", "hey"};
sort(words.begin(), words.end(), [](const auto &a, const auto &b) {
return a.size() < b.size();
});
Partial Sort
hljs cpp
// Only sort the first k elements
partial_sort(v.begin(), v.begin() + k, v.end());
// Find k smallest elements (unsorted)
nth_element(v.begin(), v.begin() + k, v.end());
lower_bound & upper_bound — Binary Search in STL
These require a sorted range and run in O(log n):
hljs cpp
vector<int> v = {1, 3, 3, 3, 5, 7, 9};
// lower_bound: first element >= x
auto lb = lower_bound(v.begin(), v.end(), 3); // iterator to first 3
int idx = lb - v.begin(); // index 1
// upper_bound: first element > x
auto ub = upper_bound(v.begin(), v.end(), 3); // iterator to 5
int idx = ub - v.begin(); // index 4
// Count of elements equal to x
int count = ub - lb; // 3
Binary Search on Answer
Many problems ask "what is the minimum/maximum X such that condition P(X) holds?" Binary search on the answer space:
hljs cpp
// Find minimum x such that f(x) is true
int lo = 0, hi = 1e9;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (f(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
// lo is the answer
binary_search — Boolean Existence Check
hljs cpp
vector<int> v = {1, 3, 5, 7, 9};
bool exists = binary_search(v.begin(), v.end(), 5); // true
bool exists = binary_search(v.begin(), v.end(), 4); // false
unique — Removing Consecutive Duplicates
unique moves duplicates to the end and returns an iterator to the new "end". You must sort first if you want to remove ALL duplicates:
hljs cpp
vector<int> v = {3, 1, 3, 1, 3};
// Remove consecutive duplicates (must sort first for all)
sort(v.begin(), v.end()); // {1, 1, 3, 3, 3}
auto last = unique(v.begin(), v.end()); // {1, 3, ?, ?, ?}
v.erase(last, v.end()); // {1, 3}
next_permutation — Generating Permutations
Generates the next lexicographically greater permutation:
hljs cpp
vector<int> v = {1, 2, 3};
// Generate all permutations
do {
for (int x : v) cout << x << " ";
cout << "\n";
} while (next_permutation(v.begin(), v.end()));
// Start from the smallest permutation
sort(v.begin(), v.end());
do {
// process permutation
} while (next_permutation(v.begin(), v.end()));
Sorting Applications
Coordinate Compression
Map large values to a compact range:
hljs cpp
vector<int> v = {1000000, 50, 1000000, 42};
vector<int> sorted_v = v;
sort(sorted_v.begin(), sorted_v.end());
sorted_v.erase(unique(sorted_v.begin(), sorted_v.end()), sorted_v.end());
// Map original values to compressed indices
for (int &x : v) {
x = lower_bound(sorted_v.begin(), sorted_v.end(), x) - sorted_v.begin();
}
// v = {2, 1, 2, 0}
Greedy Sorting
Many greedy problems become trivial after sorting:
hljs cpp
// Activity selection: maximize non-overlapping intervals
vector<pair<int,int>> intervals = {{1,3}, {2,5}, {4,7}, {6,8}};
sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b) {
return a.second < b.second; // sort by end time
});
int count = 0, last_end = -1;
for (const auto &[start, end] : intervals) {
if (start >= last_end) {
count++;
last_end = end;
}
}
Frequency Counting
Array of Values
hljs cpp
// Count frequency of each value (values in range [0, MAX])
const int MAX = 100001;
int freq[MAX] = {};
for (int x : v) freq[x]++;
// Find values that appear more than k times
for (int i = 0; i < MAX; i++) {
if (freq[i] > k) cout << i << " ";
}
Using Maps (Unbounded Values)
hljs cpp
map<int, int> freq;
for (int x : v) freq[x]++;
// Sort by frequency
vector<pair<int,int>> sorted_freq(freq.begin(), freq.end());
sort(sorted_freq.begin(), sorted_freq.end(), [](const auto &a, const auto &b) {
return a.second > b.second;
});
Summary
sortwith custom comparators is the most versatile tool in your arsenallower_bound/upper_boundgive O(log n) binary search on sorted rangesuniqueonly removes consecutive duplicates — sort first for full deduplicationnext_permutationgenerates permutations in lexicographic order- Frequency arrays are O(n + MAX); maps are O(n log n) but handle unbounded values
Prefer reading offline? Download the full book as a PDF.
Download Free Book