Everything you need to know about C++ for LeetCode.
Siva
Arrays / Vector
1D Vector
vector<int> vec(3, 0); // vector of size 3 with all elements initialized to 0
2D Vector
vector<vector<int>> vec(3, vector<int>(3, 0));
Insert element at the end of the vector
vec.push_back(1);
Peek element at the end of the vector
vec.back();
Remove element from the end of the vector
vec.pop_back();
Remove element from the vector
vec.erase(vec.begin() + 1); // remove element at index 1
Different ways of iterating over a vector
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << endl;
}
for (auto i : vec) {
cout << i << endl;
}
for (auto it = vec.begin(); it != vec.end(); it++) {
cout << *it << endl;
}
for_each(vec.begin(), vec.end(), [](int i) { cout << i << endl; });
Sort a vector
sort(vec.begin(), vec.end());
// Custom comparator - sort in descending order
sort(vec.begin(), vec.end(), [](int &a, int &b) { return a > b; });
Accumulate
int sum = accumulate(vec.begin(), vec.end(), 0);
Reverse
reverse(vec.begin(), vec.end());
Find
auto it = find(vec.begin(), vec.end(), 1);
Binary search
bool found = binary_search(vec.begin(), vec.end(), 1);
Lower bound - returns the first element that is not less than the given value
auto it = lower_bound(vec.begin(), vec.end(), 1);
Upper bound - returns the first element that is greater than the given value
auto it = upper_bound(vec.begin(), vec.end(), 1);
Map
vector<int> vec = {1, 2, 3, 4, 5};
transform(vec.begin(), vec.end(), vec.begin(), [](int &i) { return i * 2; }); // [2, 4, 6, 8, 10]
Hashmaps
map
Note that the map is implemented as a red-black tree, so the time complexity of the operations is O(log(n))
.
map<int, int> map;
unordered_map
Note that the unordered_map is implemented as a hash table, so the optimal time complexity of the operations is O(1)
.
unordered_map<int, int> map;
Insert element into the map
map.insert({1, 2});
map[1] = 2;
Remove element from the map
map.erase(1);
Check if element exists in the map
if (map.find(1) != map.end()) {
cout << "Element exists" << endl;
}
if (map.count(1)) {
cout << "Element exists" << endl;
}
Sets
set
Note that the set is implemented as a red-black tree, so the time complexity of the operations is O(log(n))
.
set<int> set;
unordered_set
Note that the unordered_set is implemented as a hash table, so the optimal time complexity of the operations is O(1)
.
unordered_set<int> set;
Insert element into the set
set.insert(1);
Remove element from the set
set.erase(1);
Check if element exists in the set
if (set.find(1) != set.end()) {
cout << "Element exists" << endl;
}
if (set.count(1)) {
cout << "Element exists" << endl;
}
Deque
deque
Note that there is also a queue and stacks in C++, but a deque is a combination of both and can be used as a queue or a stack. The time complexity of the operations is O(1)
.
deque<int> deque;
Insert element at the beginning of the deque
deque.push_front(1);
Insert element at the end of the deque
deque.push_back(1);
Peek element at the beginning of the deque
deque.front();
Peek element at the end of the deque
deque.back();
Remove element from the beginning of the deque
deque.pop_front();
Remove element from the end of the deque
deque.pop_back();
Different ways of iterating over a deque
for (int i = 0; i < deque.size(); i++) {
cout << deque[i] << endl;
}
for (auto i : deque) {
cout << i << endl;
}
for (auto it = deque.begin(); it != deque.end(); it++) {
cout << *it << endl;
}
Priority Queue
priority_queue
Note that the priority queue is implemented as a heap, so the time complexity of the operations is O(log(n))
. By default, the priority queue is a max heap, but it can be changed to a min heap by passing a custom comparator.
priority_queue<int> pq;
Insert element into the priority queue
pq.push(1);
Remove element from the priority queue
pq.pop();
Peek element at the top of the priority queue
pq.top();
Min heap
priority_queue<int, std::vector<int>, std::greater<int>> pq;
Custom comparator
class Foo {
// left empty
};
class Compare {
public:
bool operator() (Foo, Foo) {
return true;
}
};
int main() {
priority_queue<Foo, std::vector<Foo>, Compare> pq;
return 0;
}
Strings
string
string str = "Hello World";
Get substring
str.substr(0, 5); // returns "Hello", first argument is the starting index, second argument is the length of the substring
Check if string is empty
str.empty();
Building a string
string str = "Hello";
str += " World"; // str is now "Hello World"
The above operation is amortized O(1)
. It can be O(n)
if the string needs to be reallocated. Source
Custom Implementation of Doubly Linked List
Simple double linked list implementation.
class LinkedListNode {
public:
int key, val;
LinkedListNode *next, *prev;
LinkedListNode(int key, int val) {
this->key = key;
this->val = val;
}
};
class DLinkedList {
public:
LinkedListNode *head, *tail;
DLinkedList() {
this->head = new LinkedListNode(0, 0);
this->tail = new LinkedListNode(0, 0);
this->head->next = this->tail;
this->tail->prev = this->head;
}
void add(LinkedListNode *node) {
auto head_next = this->head->next;
head_next->prev = node;
head->next = node;
node->prev = head;
node->next = head_next;
}
void remove(LinkedListNode *node) {
auto node_prev = node->prev;
auto node_next = node->next;
node_prev->next = node_next;
node_next->prev = node_prev;
}
};
Quickselect algo in C++
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return findKthLargest(nums, 0, nums.size() - 1, nums.size() - k);
}
int findKthLargest(vector<int> &nums, int start, int end, int smallest_index) {
if (start == end) return nums[start];
int pivot = rand() % (end - start + 1) + start;
int i = partition(nums, start, end, smallest_index);
if (i == smallest_index) {
return nums[i];
} else if (i > smallest_index) {
return findKthLargest(nums, start, i - 1, smallest_index);
} else {
return findKthLargest(nums, i + 1, end, smallest_index);
}
}
int partition(vector<int> &nums, int start, int end, int index) {
swap(nums[index], nums[end]);
int current = start;
for (int i = start; i < end; i++) {
if (nums[i] < nums[end]) {
swap(nums[i], nums[current]);
current++;
}
}
swap(nums[current], nums[end]);
return current;
}
};