1 Sort
use case
void printArray(std::vector<int>& arr)
{
for (auto& item : arr) cout << item << " ";
cout << std::endl;
}
int main()int main()
{{
std::vector<int> arr = {4, 6, 2, 8, 3, 1, 3, 9, 8, 6, 3, 4}; std::vector<int> arr = {4, 6, 2, 8, 3, 1, 3, 9, 8, 6, 3, 4};
printArray(arr); printArray(arr);
quickSort(arr, 0, arr.size() - 1);quickSort(arr, 0, arr.size() - 1);
printArray(arr);
}
Merge sort
void merge(std::vector<int>& arr, int lo, int mid, int hi)
{
int num1 = mid - lo + 1;
int num2 = hi - mid;
std::vector<int> leftArr(arr.begin() + lo, arr.begin() + mid + 1);
std::vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + hi + 1);
int i = 0;
int j = 0;
int k = lo;
while (i < num1 && j < num2)
{
if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
else arr[k++] = rightArr[j++];
}
while (i < num1)
{
arr[k++] = leftArr[i++];
}
while (i < num2)
{
arr[k++] = rightArr[j++];
}
}
void mergeSort(std::vector<int>& arr, int lo, int hi)void mergeSort(std::vector<int>& arr, int lo, int hi)
{{
if (lo < hi) { if (lo < hi) {
int mid = lo + (hi - lo) / 2; int mid = lo + (hi - lo) / 2;
mergeSort(arr, lo, mid);mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);mid + 1, hi);
merge(arr, lo, mid, hi);(arr, lo, mid, hi);
}}
}
private static void merge(int[] arr, int lo, int mid, int hi) {
int[] help = new int[hi - lo + 1];
int i = 0;
int p1 = lo;
int p2 = mid + 1;
while (p1 <= mid && p2 <= hi) help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
while (p1 <= mid) help[i++] = arr[p1++];
while (p2 <= hi) help[i++] = arr[p2++];
for (i = 0; i < help.length; i++) arr[lo + i] = help[i];
}
private static void mergesort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergesort(arr, lo, mid);
mergesort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
Quick sort
- 75. Sort Colors
int partition(std::vector<int>& arr, int lo, int hi)
{
int ridx = std::rand() % (hi - lo + 1) + lo;
int pivot = arr[ridx];
int i = lo - 1;
int j = hi + 1;
while (true) {
// Move the left index to the right at least once and while the element at the left index is less than the pivot
do {
i++;
} while (arr[i] < pivot);
// Move the right index to the left at least once and while the element at the right index is greater than the pivot
do {
j--;
} while (arr[j] > pivot);
// If the indices crossed, return
if (i >= j) return j;
// Swap the elements at the left and right indices
std::swap(arr[i], arr[j]);
}
}
void quickSort(std::vector<int>& arr, int lo, int hi)void quickSort(std::vector<int>& arr, int lo, int hi)
{{
if (lo < hi) { if (lo < hi) {
int p = partition(arr, lo, hi); int p = partition(arr, lo, hi);
quickSort(arr, lo, p);quickSort(arr, lo, p);
quickSort(arr, p + 1, hi);p + 1, hi);
}}
}
Heap sort
Heap structure
In many computer science applications, we only need to access the largest or smallest element in the dataset.
A priority queue is an abstract data type, while a Heap is a data structure. Therefore, a Heap is not a Priority Queue, but a way to implement a Priority Queue. There are multiple ways to implement a Priority Queue, such as array and linked list. However, operations except for insertion or deletion will have O(N).
A Heap is a special type of binary tree.
- Is a complete binary tree;
- The value of each node must be no greater than (or no less than) the value of its child nodes.
class MinHeap
{
public:
MinHeap(int heapSize)
: heapSize(heapSize)
{
data.resize(heapSize + 1);
data[0] = 0;
}
int peek() { return data[1]; }
int size() { return realSize; }
void add(int element) {
realSize++;
if (realSize > heapSize)
{
cout << "too many elements!" << endl;
realSize--;
return;
}
data[realSize] = element;
int curr = realSize;
// Note if we use an array to represent the complete binary tree
// and store the root node at index 1
// index of the parent node of any node is [index of the node / 2]
// index of the left child node is [index of the node * 2]
// index of the right child node is [index of the node * 2 + 1]
int parent = curr / 2;
// If the newly added element is smaller than its parent node,
// its value will be exchanged with that of the parent node
while (data[curr] < data[parent] && curr > 1)
{
std::swap(data[curr], data[parent]);
curr = parent;
parent = curr / 2;
}
}
int pop()
{
if (realSize < 1)
{
cout << "empty!" << endl;
return INT_MAX;
}
int removeElement = data[1];
// Put the last element in the Heap to the top of Heap
data[1] = data[realSize];
realSize--;
int curr = 1;
// When the element is not a leaf node
while (curr <= realSize / 2)
{
int left = curr * 2;
int right = curr * 2 + 1;
// If the element is larger than the left or right child
// its value needs to be exchanged with the smaller value
// of the left and right child
if (data[curr] <= data[left] && data[curr] <= data[right]) break;
int minChild = data[left] < data[right] ? left : right;
std::swap(data[curr], data[minChild]);
curr = minChild;
}
return removeElement;
}
void print()
{
if (realSize == 0) cout << "no element!" << endl;
std::string info = "[";
for (int i = 1; i < realSize; ++i)
{
info = info + std::to_string(data[i]) + ",";
}
info += std::to_string(data[realSize]) + "]";
cout << info << endl;
}
private:
std::vector<int> data;
int heapSize;
int realSize = 0;
};
int main()int main()
{{
// Test case // Test case
MinHeap minHeap(3);MinHeap minHeap(3);
minHeap.add(3);minHeap.add(3);
minHeap.add(1);1);
minHeap.add(2);2);
minHeap.print(); // [1,3,2]print(); // [1,3,2]
cout << minHeap.peek() << endl; // 1cout << minHeap.peek() << endl; // 1
cout << minHeap.pop() << endl; // 1op() << endl; // 1
minHeap.print(); // [2,3]minHeap.print(); // [2,3]
minHeap.add(4);add(4);
minHeap.add(5); // Add too many elements5); // Add too many elements
minHeap.print(); // [2,3,4]print(); // [2,3,4]
}
sort:
void heapSort(std::vector<int>& arr, int lo, int hi)
{
MinHeap minHeap(arr.size());
for (auto& item : arr) minHeap.add(item);
int curr = 0;
while (minHeap.size() != 0)
{
arr[curr++] = minHeap.pop();
}
}
2 Search
2.1 Binary search
3 Tree
Binary Tree
Traversal
- preorder
- use one stack(add root)
- algo
- do something
- push right
- push left
- LC144
- postorder
- two stacks(add root)
- algo
- push curr to stack2
- push left to stack1
- push right to stack2
- use stack2 to do something
- LC145
- inorder
- use one stack, don’t push root to the stack
- algo
- if stack is not empty or root is not empty, keep going
- if root/curr is not null, keep push to the stack, root updated to its left(idea: keep push left to the stack)
- if root/curr is null, then do other logic:
- take item from the stack
- do something
- root updated to the item’s right.
- LC94
- BFS
- use one queue(add root)
- algo
- pop, do something
- push left if not null
- push right if not null
- if you need level information, just create a hash map to record!
- LC102, LC104
recursive(there are 3 places to do something):
void f(Node* node)
{
// 1
if (node == nullptr) return;
// 1
f(node->left);
// 2
// 2
f(node->right);
// 3
// 3
}
preorder:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (nullptr == root) return res;
std::stack<TreeNode*> stack;
stack.push(root);
while (!stack.empty())
{
TreeNode* curr = stack.top();
stack.pop();
res.push_back(curr->val);
if (curr->right != nullptr) stack.push(curr->right); // be careful
if (curr->left != nullptr) stack.push(curr->left); if (curr->left != nullptr) stack.push(curr->left);
}}
return res; return res;
}
postorder:
vector<int> postorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
vector<int> res;
std::stack<TreeNode*> stack1;
std::stack<TreeNode*> stack2;
stack1.push(root);
while (!stack1.empty())
{
TreeNode* curr = stack1.top();
stack1.pop();
stack2.push(curr);
if (curr->left != nullptr) stack1.push(curr->left);
if (curr->right != nullptr) stack1.push(curr->right);
}
while (!stack2.empty())
{
TreeNode* curr = stack2.top();
stack2.pop();
res.push_back(curr->val);
}
return res;
}
inorder:
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
std::vector<int> result;
std::stack<TreeNode*> stack;
while (!stack.empty() || root != nullptr)
{
if (root != nullptr)
{
stack.push(root);
root = root->left;
} else
{
TreeNode* curr = stack.top();
stack.pop();
result.push_back(curr->val);
root = curr->right;
}
}
return result;
}
BFS:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) return {};
std::vector<std::vector<int>> res;
std::queue<TreeNode*> queue;
std::unordered_map<TreeNode*, int> levels;
queue.push(root);
levels.insert({root, 0});
while (!queue.empty())
{
TreeNode* curr = queue.front();
queue.pop();
int level = levels[curr];
if (res.size() < level + 1) res.resize(level + 1);
res[level].push_back(curr->val);
if (curr->left != nullptr) if (curr->left != nullptr)
{{
queue.push(curr->left); queue.push(curr->left);
levels[curr->left] = level + 1;levels[curr->left] = level + 1;
}}
if (curr->right != nullptr)if (curr->right != nullptr)
{ {
queue.push(curr->right); queue.push(curr->right);
levels[curr->right] = level + 1; levels[curr->right] = level + 1;
}}
}}
return res;return res;
}
Red-black tree
- It is a self-balanced BST. (Binary Search Tree)
- Every node has a color (black or red)
- Root is black
- When Parent’s color is red then the child MUST be black
- From the current node to the leaf, the “black nodes on each path” is the same
- On every leaf, there are 2 “None” nodes, color is black
What you need to take note of are Rules #4 and #5. They are the 2 important ones contributing to “self-balancing”.
4 Graph
General structure
struct Edge;
struct Node {
int id;
int in = 0;
int out = 0;
std::vector<Edge*> edges;
std::vector<Node*> nexts;
Node(int id) : id(id) {}
};
struct Edge {
int weight;
Node* from;
Node* to;
Edge(Node* from, Node* to) : from(from), to(to) {}
};
struct Graph
{
std::unordered_map<int, Node*> nodes;
std::unordered_set<Edge*> edges;
~Graph() {
for (auto edge : edges) delete edge;
for (auto node : nodes) delete node.second;
}
void Load(const vector<vector<int>>& flights)
{
for (auto& flight : flights)
{
int from = flight[0];
int to = flight[1];
int weight = flight[2];
// new nodes
if (nodes.find(from) == nodes.end())
{
nodes.insert({from, new Node(from) });
}
if (nodes.find(to) == nodes.end())
{
nodes.insert({ to, new Node(to) });
}
// new edges
Node* fromNode = nodes[from];
Node* toNode = nodes[to];
Edge* newEdge = new Edge(weight, fromNode, toNode);
fromNode->nexts.emplace_back(toNode);
fromNode->out++;
fromNode->edges.emplace_back(newEdge);
toNode->in++;
edges.insert(newEdge);
}
}
};
std::vector<std::vector<int>> adj_list(n);
for (auto& edge : edges)
{
adj_list[edge[0]].push_back(edge[1]);
adj_list[edge[1]].push_back(edge[0]);
}
Disjoint Set
Breadth-First Search(BFS)
- use queue and set
- 1971. Find if Path Exists in Graph
- 797. All Paths From Source to Target
void bfs(Node* node)
{
if (node == nullptr) return;
std::queue<Node*> queue;
std::unordered_set<Node*> set;
queue.push(node);
set.insert(node);
while (!queue.empty()) {
auto curr = queue.front();
queue.pop();
for (auto next : curr->nexts)
{
if (set.find(next) == set.end()) {
set.insert(node);
queue.push(node);
}
}
}
}
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> paths;
if (graph.size() == 0) {
return paths;
}
vector<int> path;
queue<vector<int>> q;
path.push_back(0);
q.push(path);
while (!q.empty()) {
vector<int> currentPath = q.front();
q.pop();
int node = currentPath.back();
for (int nextNode : graph[node]) {
vector<int> tmpPath(currentPath.begin(), currentPath.end());
tmpPath.push_back(nextNode);
if (nextNode == graph.size() - 1) {
paths.push_back(tmpPath);
} else {
q.push(tmpPath);
}
}
}
return paths;
}
};
or
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> res;
int n = graph.size();
queue<vector<int>> q;
vector<int> path;
path.push_back(0);
q.push(path);
while (!q.empty())
{
auto currentPath = q.front();
q.pop();
int curr = currentPath.back();
if (curr == n - 1) res.push_back(currentPath);
for (auto& adj : graph[curr])
{
vector<int> newPath = currentPath;
newPath.push_back(adj);
q.push(newPath);
}
}
return res;
}
};
Depth-First Search(DFS)
void dfs(Node* node)
{
if (node == nullptr) return;
std::stack<Node*> stack;
std::unordered_set<Node*> set;
stack.push(node);
set.insert(node);
// do something
while (!stack.empty())
{
auto curr = stack.top();
stack.pop();
for (auto next : curr->nexts)
{
if (set.find(node) == set.end())
{
// stack.push(curr)
stack.push(next);
set.insert(next);
// do something
//break;
}
}
}
}
Backtracking
- 797. All Paths From Source to Target
class Solution {
public:
int n;
std::vector<int> path;
void backtracking(std::vector<std::vector<int>>& paths, std::vector<std::vector<int>>& graph, int curr)
{
if (curr == n - 1)
{
paths.emplace_back(path);
return;
}
for (const auto& next : graph[curr])
{
path.emplace_back(next);
backtracking(paths, graph, next);
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
n = graph.size();
std::vector<std::vector<int>> paths;
path = { 0 };
backtracking(paths, graph, 0);
return paths;
}
};
Single Source Shortest Path Algorithm
- BFS can only solve the shortest path problem in unweighted graphs.
- edge relaxation operation(ie. updating the label) is a key element in solving the single source shortest path problem.
- Dijkstra’s algorithm can only be used to solve the “single source shortest path” problem in a graph with non-negative weights.
- greedy approach
- Each step selects the “minimum weight” from the currently reached vertices to find the “shortest path” to other vertices.
- Bellman-Ford algorithm, on the other hand, can solve the “single-source shortest path” in a weighted directed graph with any weights, including, of course, negative weights.
Dijkstra’s Algorithm
- LC743
- LC787
// Dijkstra's algorithm to find the shortest path from the source to all other nodes
void dijsktra(std::vector<std::pair<int, int>>* adj, std::vector<int>& tree, int source, int n) {
// Min-heap priority queue to get the node with the smallest distance/time
using WeightSumNodePair = std::pair<int, int>;
std::priority_queue<WeightSumNodePair, std::vector<WeightSumNodePair>, std::greater<WeightSumNodePair>> pq;
pq.push({ 0, source });
// Weight for the starting node is 0
tree[source] = 0;
while (!pq.empty())
{
// Get the current node and the weight
int currWeight = pq.top().first;
int currNode = pq.top().second;
pq.pop();
// In case other nodes updated the tree
if (currWeight > tree[currNode]) continue;
// Broadcast the signal to adjacent nodes
for (auto edge : adj[currNode])
{
int weightToAdd = edge.first;
int neighborNode = edge.second;
// if new weight less than the last weight, then update it
if (currWeight + weightToAdd < tree[neighborNode])
{
tree[neighborNode] = currWeight + weightToAdd; // update
// Push the neighbor node into the priority queue for further processing
pq.push({ tree[neighborNode], neighborNode });
}
}
}
}
using WeightDst = std::pair<int, int>;
int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
// Adjacency list, defined it as per the maximum number of nodes
// But can be defined with the input size as well
std::vector<WeightDst> adj[101];
// build the adj list
for (auto& time : times) {
int src = time[0];
int dst = time[1];
int weight = time[2];
adj[src].push_back({ weight, dst});
}
std::vector<int> tree(n + 1, INT_MAX);
dijsktra(adj, tree, k, n);
int answer = INT_MIN;
for (int i = 1; i <= n; ++i)
{
answer = std::max(answer, tree[i]);
}
return answer == INT_MAX ? -1 : answer;
}
int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
using WeightDstPair = std::pair<int, int>;
using Next = std::vector<WeightDstPair>;
std::vector<Next> adj(n);
for (auto e : flights) {
adj[e[0]].push_back({ e[1], e[2] });
}
std::vector<int> stops(n, INT_MAX);
std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, std::greater<std::vector<int>>> pq;
// {dist_from_src_node, node, number_of_stops_from_src_node}
pq.push({0, src, 0});
while (!pq.empty())
{
auto temp = pq.top();
pq.pop();
int dist = temp[0];
int node = temp[1];
int steps = temp[2];
// We have already encountered a path with a lower cost and fewer stops,
// or the number of stops exceeds the limit.
if (steps > stops[node] || steps > k + 1) continue;
stops[node] = steps;
if (node == dst) return dist;
for (auto& [neighbor, price] : adj[node]) {
pq.push({ dist + price, neighbor, steps + 1 });
}
}
return -1;
}
