Leetcode in C++

Unordered_Map

Instantiating a unordered_map

1std::unordered_map<std::string, std::string> map = {{"ken", "sim"}, {"jack", "neo"}, {"tom", "cruise"}};
2if(map.find("tom") != map.end()) {
3  std::cout << "tom cruise exist in the map" << std::endl;
4} else {
5  std::cout << "tom cruise does not exist in the map" << std::endl;
6}

Iterating through map

1std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
2std::unordered_map<string, vector<string>> map;
3for (const auto& str : strs) {
4    string sortedStr = str;
5    std::sort(sortedStr.begin(), sortedStr.end());
6    map[sortedStr].push_back(str);
7}
8vector<vector<string>> res;
9for (const auto& pair : map) {
10    res.push_back(pair.second);
11}
12
13unordered_map<int, TreeNode*> map;
14unordered_set<TreeNode*> child;
15for(const auto& [val, node]: map) {
16    if(child.count(node) > 0) {
17        continue;
18    } else {
19        res = node;
20    }
21}

Difference Between map.emplace and map[key] = value

map.emplace(key, args...)
This method constructs the element in-place within the map, using the arguments provided to directly initialize the value. Internally, it constructs a std::pair<const Key, Value> without creating a temporary object. This makes emplace especially efficient for complex or non-trivially copyable types.

- Performs in-place construction, avoiding unnecessary copies or moves.
- Does not overwrite an existing value if the key already exists—no assignment is performed.
- Useful when constructing expensive objects directly in the map.

map[key] = value
This operator first checks if the key exists in the map. If it does, it assigns the provided value to the existing entry. If it does not, it default-constructs a new Value object at that key and then assigns the given value.

- Requires the Value type to be default-constructible.
- May involve two operations: default construction followed by assignment, which could be less efficient.
- Overwrites the value if the key already exists in the map.

Searching for element in map

1int main() {
2    unordered_map<int, int> freq;
3    freq[5] = 3;    
4    freq[10] = 2;   
5    int keyToFind = 5;
6
7    // Method 1: Using find()
8    if (freq.find(keyToFind) != freq.end()) {
9        cout << "Key " << keyToFind << " exists with value " << freq[keyToFind] << "
10";
11    } else {
12        cout << "Key " << keyToFind << " does not exist
13";
14    }
15
16    // Method 2: Using count()
17    if (freq.count(10) > 0) {
18        cout << "Key 10 exists
19";
20    }
21
22    if (freq.count(8) == 0) {
23        cout << "Key 8 does not exist
24";
25    }
26}

In this example, we show two common ways to check whether a key exists in anunordered_map in C++.

Method 1 – Using find():The find() method returns an iterator to the key if it exists, otherwise it returns end(). This is useful when you want to both check for existence and directly work with the element's iterator.

Method 2 – Using count():The count() method returns 1 if the key exists and0 otherwise. This is a quick way to check presence when you don’t need the iterator or value immediately.

String

Converting Between String and Integer Types

1std::string encode(std::vector<std::string>& strs) {
2    std::string res = "";
3    std::string delimiter = ";";
4    for (const auto& str : strs) {
5        int len = static_cast<int>(str.length());
6        std::string lenStr = std::to_string(len); // convert int to string
7        res += lenStr + delimiter + str;
8    }
9    return res;
10}
11
12std::vector<std::string> decode(std::string s) {
13    std::vector<std::string> res;
14    if (s.empty()) { // empty input
15        return res;
16    }
17    int index = 0;
18    while (index < static_cast<int>(s.length())) {
19        std::string len = "";
20        while (std::isdigit(s[index])) { // check if char is a digit
21            len += s[index];
22            index++;
23        }
24        // s[index] should be the delimiter
25        index++;
26        int lenInt = std::stoi(len); // convert string to int
27        std::string str = s.substr(index, lenInt); // extract substring
28        index += lenInt;
29        res.push_back(str);
30    }
31    return res;
32}

In C++, std::to_string(int) converts an integer to its string representation, while std::stoi(std::string) converts a string containing digits into an integer. The std::isdigit(char)function checks whether a given character is a numeric digit. For extracting parts of a string, substr(startIndex, length) returns a substring starting at the specified index and spanning the given number of characters. In this example, the encode function stores each string with its length followed by a delimiter, and the decode function parses this format back into the original list of strings.

Checking if String is emtpy

1std::string str1 = ""; 
2std::string str2 = "Hello"; 
3if (str1.empty()) {
4    std::cout << "str1 is empty." << std::endl;
5} else {
6    std::cout << "str1 is not empty." << std::endl;
7}

Detecting whitespace

1#include <iostream>
2#include <string>
3#include <cctype> // For std::isspace
4
5int main() {
6    std::string text = "Hello World!";
7    int whitespaceCount = 0;
8
9    for (char c : text) {
10        if (std::isspace(static_cast<unsigned char>(c))) {
11            whitespaceCount++;
12        }
13    }
14
15    std::cout << "The string contains " << whitespaceCount << " whitespace characters." << std::endl;
16
17    return 0;
18}

Checking if character is digit

1#include <iostream>
2#include <cctype> // Required for isdigit()
3
4int main() {
5    char ch1 = '7';
6    char ch2 = 'a';
7
8    if (isdigit(ch1)) {
9        std::cout << "'" << ch1 << "' is a digit." << std::endl;
10    } else {
11        std::cout << "'" << ch1 << "' is not a digit." << std::endl;
12    }
13
14    return 0;
15}

Extracting substring from string

1#include <iostream>
2#include <string>
3
4int main() {
5    std::string originalString = "Hello, C++ Substring!";
6
7    // Extract from index 7 with a length of 3
8    std::string sub1 = originalString.substr(7, 3); 
9    std::cout << "Substring 1: " << sub1 << std::endl; // Output: C++
10
11    // Extract from index 0 until the end
12    std::string sub2 = originalString.substr(0); 
13    std::cout << "Substring 2: " << sub2 << std::endl; // Output: Hello, C++ Substring!
14
15    // Extract from index 7 until the end
16    std::string sub3 = originalString.substr(7); 
17    std::cout << "Substring 3: " << sub3 << std::endl; // Output: C++ Substring!
18
19    return 0;
20}

Splitting a string

1#include <iostream>
2#include <string>
3
4int main() {
5    queue<string> q;
6    int start = 0;
7    int curr = data.find(",");
8    while(curr != string::npos) {
9        // delimeter is found, index at curr, we want start to curr - 1, so length is (curr - 1 - start + 1)
10        string currNode = data.substr(start, curr - start);
11        start = curr + 1;
12        curr = data.find(",", start);
13        q.push(currNode);
14    }
15}

The std::string::find() method is used to locate the first occurrence of a substring or a character within a given string. It searches for the specified substring or character within the string on which it is called. If the substring or character is found, find() returns the starting index (position) of its first occurrence within the string. The index is a size_t type, representing an unsigned integer. If the substring or character is not found, find() returns std::string::npos. This is a static member constant of std::string that represents the largest possible value for size_t.

Splitting a string part 2

1std::vector<std::string> splitByDelimiter(const std::string& str, char delimiter) {
2    std::vector<std::string> tokens;
3    std::stringstream ss(str);
4    std::string token;
5
6    while (std::getline(ss, token, delimiter)) {
7        tokens.push_back(token);
8    }
9
10    return tokens;
11}

std::istringstream

std::istringstream allows a string to be treated as an input stream, making it possible to extract formatted data using the same >> operator used with standard input streams. It is commonly used for parsing structured text, tokenizing input by whitespace, and converting substrings into numeric types in a safe and readable way.

1#include <iostream>
2#include <sstream>
3#include <string>
4
5int main() {
6    std::string data_line = "ID: 101 Name: John 3.14";
7    std::istringstream iss(data_line); // Initialize istringstream with the string
8
9    std::string label1, label2, name;
10    int id;
11    float value;
12
13    // Use the extraction operator (>>) to read data
14    iss >> label1 >> id >> label2 >> name >> value;
15
16    // Check if the extractions were successful
17    if (iss) { // Equivalent to checking if the stream is in a good state
18        std::cout << "Parsed data:" << std::endl;
19        std::cout << label1 << " " << id << std::endl;
20        std::cout << label2 << " " << name << std::endl;
21        std::cout << "Value: " << value << std::endl;
22    } else {
23        std::cerr << "Error parsing the string." << std::endl;
24    }
25
26    return 0;
27}

std::ostringstream

std::ostringstream is an output string stream that lets you build a string using the same << operator used with std::cout. Instead of writing to the console, it writes formatted data into an internal string buffer.

This makes it especially useful for constructing complex strings, combining multiple data types, and converting numbers or other values into text in a clean and type-safe way.

1#include <iostream>
2#include <sstream>
3#include <string>
4
5int main() {
6    std::ostringstream oss;
7
8    std::string name = "Alice";
9    int score = 95;
10    double percentage = 95.5;
11
12    oss << "Student Name: " << name
13        << ", Score: " << score
14        << ", Percentage: " << percentage << "%";
15
16    std::string result = oss.str();
17    std::cout << result << std::endl; 
18    // Student Name: Alice, Score: 95, Percentage: 95.5%
19
20    oss.str("");
21    oss.clear();
22
23    return 0;
24}

Priority Queue

Ordering a Priority Queue Based on Values in a Hash Map

1std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
2    std::unordered_map<int, int> map;
3    for (const auto& num : nums) {
4        map[num] += 1;
5    }
6
7    auto cmp = [&](int a, int b) { // lambda function
8        return map[a] < map[b]; // most frequent at top
9    };
10
11    std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
12}

In this example, instead of std::greater, we use a custom lambda that compares elements based on their frequency in the hash map, allowing us to keep the most frequent elements at the top.

Adding and retrieving elements from priority queue

1std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
2
3pq.push(2);
4
5int elem = pq.top();
6pq.pop();
7
8while(!pq.empty()) {
9    //logic here
10}

Defining a max and min-heap

1std::priority_queue<int, std::vector<int>, std::less<int>> pq; // max-heap
2std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // min heap

std::priority_queue<int, std::vector<int>, std::greater<int>>:
int — The type of elements stored in the queue.
std::vector<int> — The underlying container used to store elements. A priority queue doesn't store elements by itself; it uses another container like std::vector or std::deque.
std::greater<int> — The comparison functor that determines the ordering of elements. Using std::greater creates a min-heap, so the smallest element is always at the top.

Basic priority queue operations

1std::priority_queue<int, std::vector<int>, std::less<int>> pq; // max-heap
2pq.pop(); // only removes the top element — it does not return it(call top)
3pq.top(); 
4pq.push(123)

Vector

Pre-allocate and Populate a Vector Using Resize and Loop

1std::vector<int> nums = {1, 2, 3, 4, 5};
2std::vector<int> squares;
3
4// Preallocate the vector with the same size as nums
5squares.resize(nums.size());
6
7for (int i = 0; i < nums.size(); i++) {
8    squares[i] = nums[i] * nums[i]; // Assign square of each element
9}
10    
11std::vector<int> left(5); // this will create a vector of length 5 and fill it with 0s

Obtaining max of vector

1#include <vector>
2#include <algorithm>
3#include <cmath>
4
5class Solution {
6public:
7    int minEatingSpeed(std::vector<int>& piles, int h) {
8        auto max_it = std::max_element(piles.begin(), piles.end());
9        int left = 1;
10        int right = *max_it;
11        int res = right;
12
13        while (left <= right) {
14            int mid = left + (right - left) / 2;
15            if (possible(piles, h, mid)) {
16                res = mid;
17                right = mid - 1;
18            } else {
19                left = mid + 1;
20            }
21        }
22        return res;
23    }
24
25    bool possible(const std::vector<int>& piles, int h, int k) {
26        int res = 0;
27        for (std::size_t i = 0; i < piles.size(); i++) {
28            res += static_cast<int>(std::ceil(static_cast<double>(piles[i]) / static_cast<double>(k)));
29        }
30        return res <= h;
31    }
32};

In this example, we use std::max_element to find the largest value in a std::vector. This function returns an iterator pointing to the maximum element. By dereferencing the iterator with *, we retrieve the actual value.std::max_element performs a linear scan of the container, comparing elements using the < operator by default, and runs in O(n) time complexity.

Two dimensional vectors

1int rows = 3;
2int cols = 4;
3std::vector<std::vector<int>> my2DVector(rows, std::vector<int>(cols, 0));

Obtaining sum of vector

1int minSubarray(std::vector<int>& nums, int p) {
2    long sum = std::accumulate(nums.begin(), nums.end(), 0L);
3}

Finding if an element is contained in the vector

1std::vector<int> vec = {10, 20, 30, 40, 50};
2int target = 30;
3auto it = std::find(vec.begin(), vec.end(), target);
4
5if (it != vec.end()) {
6    std::cout << "Element " << target << " found in the vector." << std::endl;
7} else {
8    std::cout << "Element " << target << " not found in the vector." << std::endl;
9}

Sorting a vector

1std::vector<std::vector<int>> vec = { {3, 10}, {1, 20}, {5, 5}, {2, 15} };
2// Sort the vector of vectors by the first element
3std::sort(vec.begin(), vec.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
4    return a[0] < b[0];
5});

Removing last element from a vector

1vector<int> vector;
2vector.pop_back();

Copy one vector into another vector

1std::vector<int> source_vec{3,1,4,1,5,9,10};
2std::vector<int> dest_vec;
3    
4std::copy(source_vec.begin(), source_vec.end(), std::back_inserter(dest_vec));

Finding the index of an element in a vector

1std::vector<std::string> vec = {"hello", "this", "is", "an", "example"};
2auto it = std::find(vec.begin(), vec.end(), "this");
3int index = std::distance(vec.begin(), it); // returns how many hops from first to last
4std::cout << "the index is " << index << std::endl;

Transforming a vector

1std::vector<int> vec = {1,2,3,4,5};
2std::vector<int> squared_vec;
3std::transform(vec.begin(), vec.end(), 
4    std::back_inserter(squared_vec), 
5    [](int n) { return n * n; });

unordered_set

unordered_set

1bool isValidSudoku(std::vector<std::vector<char>>& board) {
2    std::unordered_map<int, std::unordered_set<int>> row;
3    std::unordered_map<int, std::unordered_set<int>> col;
4    std::unordered_map<int, std::unordered_set<int>> grid;
5
6    // Initialize rows
7    for (int i = 0; i < 9; i++) {
8        row.emplace(i, std::unordered_set<int>());
9    }
10
11    for (int i = 0; i < static_cast<int>(board.size()); i++) {
12        for (int j = 0; j < static_cast<int>(board[i].size()); j++) {
13            int elem = board[i][j];
14            if (elem == '.') {
15                continue;
16            }
17
18            int gridNo = (i / 3) * 3 + (j / 3);
19
20            // Check if the element already exists in the same row, column, or grid
21            if (row[i].find(elem) != row[i].end() ||
22                col[j].find(elem) != col[j].end() ||
23                grid[gridNo].find(elem) != grid[gridNo].end()) {
24                return false;
25            }
26
27            // Insert element into row, column, and grid sets
28            row[i].insert(elem);
29            col[j].insert(elem);
30            grid[gridNo].insert(elem);
31        }
32    }
33    return true;
34}

To check if a value exists in a set, useset.find(elem) != set.end().
To insert a value, call set.insert(elem).
To remove a value, use set.erase(elem).

Convert vector to unordered_set

1std::vector<int> vec{3,1,4,1,5,9,10};
2std::unordered_set<int> set(vec.begin(), vec.end());

Combine two unordered_set

1std::unordered_set<std::string> set = {"hello", "this", "is", "test", "one"};
2std::unordered_set<std::string> set2 = {"yo", "this", "is", "test", "two"};
3set.insert(set2.begin(), set2.end());
4for(const auto str: set) {
5    std::cout << str << " ";
6}
7std::cout << std::endl;

Pointers

1class Solution {
2public:
3    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
4        unordered_map<int, TreeNode*> map;
5        unordered_set<TreeNode*> child;
6        for(const auto edge: descriptions) {
7            int parentVal = edge[0];
8            int childVal = edge[1];
9            bool isLeft = edge[2] == 1;
10            if(!map.count(parentVal)) { // key does not exist in the map
11                map[parentVal] = new TreeNode(parentVal);
12            }
13            if(!map.count(childVal)) {
14                map[childVal] = new TreeNode(childVal);
15            }
16            if(isLeft) {
17                map[parentVal] ->left = map[childVal];
18            } else {
19                map[parentVal] -> right = map[childVal];
20            }
21            child.insert(map[childVal]);
22        }
23        TreeNode* res = nullptr;
24        for(const auto& [val, node]: map) {
25            if(child.count(node) > 0) {
26                continue;
27            } else {
28                res = node;
29            }
30        }
31        return res;
32    }
33};