# Gao's LeetCode 101: Sorting
## 0. Post Details
- Reference: [Gao et al., LeetCode 101 - A Grinding Guide, 2001.](https://noworneverev.github.io/leetcode_101/category/4-%E5%8D%83%E5%A5%87%E7%99%BE%E6%80%AA%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95)
- Post by: Jedd Yang
- Date: 2025-09-10
- Keywords: Sort
## 1. Problems
### <font color="#FFA500"> 215. Kth Largest Element in an Array </font>
> Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting?
:::success
- Approach： `nth_element()` (one pass of Quickselect), [use STL.](https://leetcode.com/problems/kth-largest-element-in-an-array/solutions/60309/c-stl-partition-and-heapsort)
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp=
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
nth_element(nums.begin(), nums.begin() + k - 1,
nums.end(), greater<int>());
// or
// partial_sort(nums.begin(), nums.begin() + k,
// nums.end(), greater<int>());
// but Time = O(n log k), k is the heap size
return nums[k - 1];
}
};
```
:::warning
- Approach： Three-way Quickselect.
- Complexity: Time $O(n^2)$; Space $O(1)$.
:::
```cpp=
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int pivotIndex = rand() % nums.size();
int pivot = nums[pivotIndex];
vector<int> larger, equal, smaller;
for(int num : nums){
if (num > pivot){
larger.push_back(num);
}else if(num < pivot){
smaller.push_back(num);
}else{
equal.push_back(num);
}
}
if(k <= larger.size()){
return findKthLargest(larger, k);
}
if(k > larger.size() + equal.size()){
return findKthLargest(smaller, k - larger.size() - equal.size());
}
return pivot;
}
};
```
:::danger
- Approach： Quicksort. The slowest for this problem.
- Complexity: Time $O(n^2)$; Space $O(1)$
:::
```cpp=
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
quickSort(nums, 0, nums.size() - 1);
// after full ascending sort, k-th largest is at size - k
return nums[nums.size() - k];
}
private:
void quickSort(vector<int>& a, int left, int right) {
if (left >= right) return;
int pivotIndex = left + rand() % (right - left + 1);
int pivot = a[pivotIndex];
int i = left, j = right;
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
// Recurse into both halves
if (left < j) quickSort(a, left, j);
if (i < right) quickSort(a, i, right);
}
};
```
### <font color="#FFA500"> 347. Top K Frequent Elements </font>
> Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order.
:::warning
- Approach： Hash table without sort, hash from larger number to small.
- Complexity: Time $O(n)$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// create a hash_table, number : frequency
unordered_map<int, int> numFrequency;
for (int num : nums) {
++numFrequency[num];
}
// create a hash_table, frequency : [number1, number2, ...]
unordered_map<int, vector<int>> buckets;
for (auto [num, freq] : numFrequency) {
// bcs different num can appear in same frequency
buckets[freq].push_back(num);
}
// create a return vector, keep adding numbers til k is met
vector<int> top_k;
for (int count = nums.size(); count >= 0; --count) {
if (buckets.find(count) != buckets.end()) {
for (int num : buckets[count]) {
top_k.push_back(num);
if (top_k.size() == k) return top_k;
}
}
}
// corner case, if nums.size() < k
return top_k;
}
};
```
### <font color="#FFA500"> 451. Sort Characters By Frequency </font>
> Given a string `s`, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
>
> Return the sorted string. If there are multiple answers, return any of them.
:::danger
- Approach：Priority queue. Use BST (`map`) and queue (`priority_queue`).
- Complexity: Time $O(n log n)$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
string frequencySort(string s) {
priority_queue<pair<int, char>> pq;
map<char, int> m;
for (auto i:s){
++m[i];
}
for (auto i:s){
pq.push({m[i], i});
}
string ans;
while(!pq.empty()){
ans.push_back(pq.top().second); // second value of the pair
pq.pop();
}
return ans;
}
};
```
:::warning
- Approach：Bucket sort.
- Complexity: Time $O(n log n)$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
string frequencySort(string s) {
// 1. Count frequencies
unordered_map<char, int> freq;
for (char c : s){
++freq[c];
}
// 2. Buckets: index = frequency
unordered_map<int, vector<char>> buckets;
int maxFreq = 0; // to track the maximum frequency
for (auto &[c, f] : freq) {
buckets[f].push_back(c);
if (f > maxFreq) maxFreq = f;
}
// 3. Build answer from high frequency to low
string ans;
for (int f = s.size(); f >= 0; --f){
if (buckets.find(f) != buckets.end()) {
for (char c : buckets[f]) {
ans.append(f, c);
}
}
}
return ans;
}
};
```
:::success
- Approach：Multimap (BST).
- Complexity: Time $O(n log n)$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
string frequencySort(string s) {
unordered_map<char,int> mp;
multimap<int,char> r; // allows duplicate keys.
string ans = "";
for(auto a : s)
mp[a]++;
// the multimap will sort the key from small to large automatically
for(auto a : mp)
r.insert({a.second, a.first});
// rbegin and rend, the reverse iterators
for(auto it = r.rbegin(); it != r.rend(); ++it)
ans += string(it->first, it->second); // string(count, char)
return ans;
}
};
```
>[!Tip] Why multimap instead of unordered_multimap
> `multimap` is a BST ordered by key (frequency). Iterating in reverse gives highest frequency first automatically. No extra sorting needed. `unordered_multimap` is a hash table. Keys are unordered. If we used it, we would need an extra sort step to process the frequencies in descending order.
### <font color="#FFA500"> 75. Sort Colors </font>
> Given an array `nums` with `n` objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.
:::warning
- Approach：Bucket sort.
- Complexity: Time $O(n)$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
void sortColors(vector<int>& nums) {
// bucket sort
// use map bcs i want it in order
map<int, vector<int>> loc;
for (int i = 0; i < nums.size(); ++i) {
loc[nums[i]].push_back(i);
}
int writePos = 0;
for (auto &kv : loc) {
// debug
// -----
// std::cout << "key: " << kv.first << " -> [";
// for (size_t i = 0; i < kv.second.size() ; ++i){
// std::cout << kv.second[i];
// if (i + 1 < kv.second.size()) std::cout << ", ";
// }
// std::cout << "]\n";
// -----
int key = kv.first;
auto& vec = kv.second;
for (size_t s = 0; s < vec.size(); ++s){
nums[writePos++] = key;
}
}
}
};
```
>[!Tip] Is storing index necessary?
> The problem requires us to print out `0, 1, 2` in ascending order, so no need to store the indices!
:::success
- Approach：Countinf sort.
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp=
class Solution {
public:
void sortColors(vector<int>& nums) {
int count[3] = {0, 0, 0};
for (int n : nums){
++count[n];
}
int writePos = 0;
for (int color = 0; color < 3; ++color) {
for (int k = 0; k < count[color]; ++k){
nums[writePos++] = color;
}
}
}
};
```
Sign in with Wallet
Connect another wallet