Home

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);
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;
    }
};