TIW: Two Pointers

It’s quite surprising how much you can accomplish with constant extra space. There are a few classic problems with integer arrays that can be solved by two pointers.

So what is “two pointers”? Basically it’s an approach to put one pointer on the left and one pointer on the right of an array, and keep moving them towards each other one step at a time (there are also cases where you would put both pointers to the left and move them to the right). When this approach applies, the solution is often easy to code and fast to run. I will go through 2-sum, 3-sum and *gasp* a hard problem on Leetcode, trapping water.

Let’s take the first example, Two Sum II. Given a sorted array, output any pair of indices that sum to a given target (weirdly, indices start at 1).

We have done a similar problem before in the post about upper_bound. But here the twists are that the array is sorted and we need to sum exactly to that number. The solution looks something like this:

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size()-1;
    while (l < r) {
        int sum = numbers[l]+numbers[r];
        if (sum == target)
            return {l+1, r+1};
        else if (sum > target)
    return {};

It is easier to explain with code. The idea here is that for each number k in the array, we only need to check whether target-k is in the array as well, and if so, return the two indices. In a sorted array, there is basically only one place to look at, which is where we will end up with binary searching for target-k. If this numbers[i]+numbers[j] is too small, and numbers[i]+numbers[j+1] is too big, that means numbers[i] will not form a solution with any other number.

The algorithm therefore proceeds both both ends, checking whether the current sum is too small or too large; if it is too small, make it bigger by incrementing i, otherwise if it is too big, make it smaller by decrementing j. Note that when you increment i, you are essentially discarding all the solutions that use numbers[i]. This is not problematic because the largest number we have not discarded yet (numbers[r]) is too small for it, so it will never form another solution. This by induction shows the correctness of the algorithm.

This can very easily be generalized to Three Sum: return all the unique triplets that sum to 0.

vector<vector<int> > threeSum(vector<int>& nums) {
    vector<vector<int> > ans;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size()-2; i++) {
        if (i > 0 && nums[i] == nums[i-1])
        int l = i+1, r = nums.size()-1;
        while (l < r) {
            int sum = nums[i]+nums[l]+nums[r];
            if (sum > 0 || r < nums.size()-1 && nums[r] == nums[r+1])
            else if (sum < 0 || l > i+1 && nums[l] == nums[l-1])
            else {
                ans.push_back({nums[i], nums[l], nums[r]});
    return ans;

Sorting is O(nlog(n)), and our algorithm is O(n^2) anyways, so we just sort it to make our life easier. Here we are essentially repeating our two pointers solution n times (n-2 to be exact). In the outermost for loop, I enumerate the leftmost number. To skip duplicates for this number, we just need to make sure we the previous number is not the same, otherwise we would have used this number as starting point already. Then for each inner loop, we are simply doing Two Sum for the array from i+1 to nums.size()-1 with target -nums[i]. Here we skip duplicates by making sure the middle point has not been used before (the previous one is different), and the right point has not been used before (the one after it is different, since the right pointer moves to the left).


Here’s another problem that could use two pointers in a different way: Trapping Rain Water

Given a height array, return the amount of rain water that would be trapped by the valleys.

This one is harder than the ones before in terms of figuring out the algorithm. The key observation here is that we only need to calculate the silhouette of the mountain after filling valleys with rain, and use it to subtract the mountain shape. It is obvious that the silhouette from left to right must first go up and then go down, so you can imagine two guys are climbing hills from both sides and must always go up or stay at the same level. Or you can imagine two pointers instead of two guys:

int trap(vector<int>& height) {
    if (height.size() < 3)
        return 0;
    int l = 0, r = height.size()-1, ans = 0, t1 = height[l], t2 = height[r];
    while (l <= r) {
        if (t1 <= t2) {
            ans += t1-height[l];
            t1 = max(t1, height[l]);
        } else {
            ans += t2-height[r];
            t2 = max(t2, height[r]);
    return ans;

There is nothing special in this problem after you figure out the monotonicity in the shape of the mountain. We have two pointers, and we record the current water level that can be trapped from both sides. Two things to note here: the while condition is l <= r instead of l < r because the pointers point at the positions that we haven’t calculated yet; we move the pointer that is lower in height so a pointer from a side won’t overshoot.


Bonus problem here: Container With Most Water. The code is very similar so I will skip it, but you guys should be able to figure out why two pointers can give a correct solution here. Hint: think about what solutions you are discarding by moving a pointer, and why those solutions will not be optimal.

TIW: In Place Swapping

Among my very little interview experience, I’ve seen this type of question twice. In general, you are given an array (maybe 1D, 2D or higher), and you need to permute the elements in O(n) time without copying the elements into a new array. As the name of this post suggests, the swap() function is handy here.

So here are two approaches to this type of problems: you either keep a place holder, or you use the array itself as the place holder. Let’s go into more details.

Assume we have an array {1, 2, 3} and we need to shift everything to the right by 1 grid. Using a place holder, you first take out the 3, move the 2 to its place, move the 1 into 2’s place, then put the 3 back into 1’s place. Code could be like this:

vector<int> v{1, 2, 3};
int t = v.back();
for (int i = v.size()-1; i > 0; i--)
    v[i] = v[i-1];
v[0] = t;

This is intuitive and is what most people can think of. It is also efficient. However for slightly harder problems, we cannot hard code everything in one loop. Say we want to shift things over by k positions, things get more complicated because k might be a factor or multiple of array length n, and we need to write multiple loops. Before that, let’s look at the below code using the swap function for shifting by k.

int next_place(int pos, int k, int n) {
    return (pos+k)%n;

void shift(vector<int>& v, int k) {
    int n = v.size();
    vector<bool> vis(n);
    for (int i = 0; i < n; i++)
        if (!vis[i]) {
            int next = next_place(i, k, n);
            do {
                swap(v[i], v[next]);
                vis[next] = true;
                next = next_place(next, k, n);
            } while (next != i);

Let me illustrate the idea using the same example {1, 2, 3}: first we swap 1 and 2 to have {2, 1, 3}, then we swap 2 and 3 to get {3, 1, 2}. Essentially the first element is used as a place holder to hold 2 while we moved 1. This is always in linear time because all the work is associated with coloring the visited vector, and we never color the same dot twice. We also only access the visited vector once for read and once for write.

Note that this solution is not optimal to the problem, since we used O(n) extra space. With some gcd magic, we can eliminate the extra space, like this:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);

int next_place(int pos, int k, int n) {
    return (pos+k)%n;

void shift(vector<int>& v, int k) {
    int n = v.size();
    for (int i = 0; i < gcd(n, k); i++)
        for (int j = next_place(i); j != i; j = next_place(j))
            swap(v[i], v[next]);

Whether we can do the problem in O(1) extra space is very dependent on the complexity of the problem (and whether your interviewer says so).

The magic about this idea of swapping in place is that for a different problem, you just need to write a different next_place function. Here’s one problem I got interviewed on:

Given an array of strings, like {“1”, “2”, “3”, “4”, “A”, “B”, “C”, “D”}, rearrange them in place so that you get {“1”, “A”, “2”, “B”, “3”, “C”, “4”, “D”}.

Now that we know the general solution, we only need to figure out where each element wants to go. Say the total length is n, then elements indexed i below n/2 wants to go to 2*i, the elements above n/2 wants to go to 2*(i-n/2)+1 = 2*i-n+1. Here’s the code:

int next_place(int pos, int n) {
    return pos < n/2 ? 2*i : 2*i-n+1;

void shift(vector<string>& v) {
    int n = v.size();
    vector<bool> vis(n);
    for (int i = 0; i < n; i++)
        if (!vis[i]) {
            int next = next_place(i, n);
            do {
                swap(v[i], v[next]);
                vis[next] = true;
                next = next_place(next, n);
            } while (next != i);

There is very little change to the shift function.


Rinse and repeat for this problem: Rotate Image. Given a square matrix, rotate it by 90 degrees.

Ok, let’s figure out where to go (x’, y’) for an element at (x, y). Here x is the column index, and y is the row index. As x increases, y’ should increase, and as y increases, x’ should decrease. So we have the functions in the form: x’ = a-y, y’ = b+x. We also know that (0, 0) goes to (n-1, 0}, so we have a = n-1, b = 0. This can alternatively be figured out by noting that 0 <= x, y, x’, y’ < n.

Naively we have:

pair<int, int> next_place(pair<int, int> pos, int n) {
    return make_pair(n-1-pos.second, pos.first);

void rotate(vector<vector<int> >& matrix) {
    int n = matrix.size();
    vector<vector<bool> > vis(n, vector<bool>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!vis[j][i]) {
                pair<int, int> next = next_place(make_pair(i, j), n);
                do {
                    swap(matrix[next.second][next.first], matrix[j][i]);
                    vis[next.second][next.first] = true;
                    next = next_place(next, n);
                } while (next.first != i || next.second != j);

But we can do better: we know each group of rotation is within 4 elements. How do we iterate through all the rotating groups of 4 once and only once? Consider the two cases: n is even and n is odd.

When n is even, we just go through one quadrant: n/2 x n/2, then we are done. Simple.

When n is odd, the number of groups we have will be n*n/4 = (2k+1)*(2k+1)/4. Oh wait, the numerator is odd! Of course, we need to take out the center point since we don’t need to rotate it. Ok, so we have (4k^2+4k)/4 = k(k+1) = (n/2)*((n+1)/2), using integer division. Hmm, seems like we can use these two numbers as number of loops.

Now we try to combine the two cases, and we can see that n/2 and (n+1)/2 actually works for both case. Let’s dive into the code:

pair<int, int> next_place(pair<int, int> pos, int n) {
    return make_pair(n-1-pos.second, pos.first);

void rotate(vector<vector<int> >& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n/2; i++)
        for (int j = 0; j < (n+1)/2; j++) {
            pair<int, int> next = next_place(make_pair(i, j), n);
            for (int k = 0; k < 3; k++) {
                swap(matrix[next.second][next.first], matrix[j][i]);
                next = next_place(next, n);

Done, easy right? Some people would prefer embedding the next_place function in the rotate function, but that’s a personal preference.

To summarize,

  1. if you can figure out a way to iterate through all the groups that rotate among themselves one element at a time without duplicates, then do so without creating a new vector to mark visited nodes;
  2. otherwise just make a bool matrix to mark them, at an extra space cost of O(n).

One final remark: all the above code using swap could be done using an extra place holder, and that would be slightly more efficient (up to a constant factor). I find it slightly more annoying.


I will dedicate this post to two functions in particular: upper_bound and lower_bound. They make the impossible become possible. Basic facts about them:

  1. they act on sorted data structures (sorted vector, set, map, etc);
  2. they perform binary search in O(log(n)) time;
  3. they return iterators so you can move forward and backward.

I will then go over 2 problems to demonstrate the power of these functions.

Let’s say you have 5 integers in a data structure, {1, 3, 5, 7, 9}, either in a vector or a set. Say you would like to find the smallest number that is larger than k, then you simply do:

vector<int> v{1, 3, 5, 7, 9};
set<int> s(v.begin(), v.end());
int k = 6;
// Binary search in a vector
auto it = upper_bound(v.begin(), v.end(), k);
if (it != v.end())
    cout << *it << endl;
// Binary search in a set
it = s.upper_bound(k);
if (it != s.end())
    cout << *it << endl;

Lower bound is not the opposite of upper bound, surprisingly. It finds the smallest number that is larger than or equal to k, allowing the equal case (which is excluded in upper_bound).


The functions are simple, but let’s dive into practice. There are quite a few problems on Leetcode for which I used upper_bound, but many are quite hard (see this one: Perfect Rectangle). This series is supposed to be easy and about syntax rather than algorithm, so I decided to make up one problem.

Problem statement:

Given a vector of integers v and an integer k, find the smallest sum from all pairs of elements that is larger than k. For example for v = {6, 0, 5, 1, 9} and k = 12, possible sums would be {1, 5, 6, 7, 9, 10, 11, 14, 15}, and the smallest that is larger than 12 would be 14.

One way to do it is to sort it and use 2 pointers, which is O(nlog(n)). I will talk about that approach in a later post. Here, a way is to use set. The algorithm essentially picks an element x, then looks at all the numbers in front of it, and pick the smallest one y that is larger than k-x, since then we know x+y > k.

int closestTwoSum(vector<int>& v, int k) {
    set<int> s;
    int ans = INT_MAX;
    for (auto x : v) {
        auto y = s.upper_bound(k-x);
        if (y != s.end())
            ans = min(ans, x+*y);
    return ans;

To get the largest sum that is smaller than k, there are two things you can do: negate all numbers and apply the same code (essentially reversing order of integers), or move the iterator given by upper_bound. Just to demonstrate, the second approach looks like this:

int closestTwoSum(vector<int> v, int k) {
    set<int> s;
    int ans = INT_MIN;
    for (auto x : v) {
        auto y = s.lower_bound(k-x); // *y larger than or equal to k-x
        if (y != s.begin()) { // if *y is not the smallest number we have
            y--;  // go back to the smaller one
            ans = max(ans, x+*y);
    return ans;

That’s a teaser problem. Now let’s get to the real business, longest increasing subsequence. The problem statement is:

Given an array of integers, find the longest increasing subsequence and return its length. For example in {1, 4, 5, 7, 2, 9, 3}, the longest increasing subsequence is {1, 4, 5, 7, 9}, so we return 5.

It’s also on Leetcode: Longest Increasing Subsequence

This is a well known dynamic programming problem, depending on how you design your dp algorithm, you can get either O(n^2) or O(nlog(n)) solutions. The O(nlog(n)) algorithm is well known, so I will just briefly describe it.

Our basic idea is to keep appending elements to increasing subsequences. Key observation: if using the first x numbers, you can create two increasing subsequences of length 5: one ending with number 7 and another ending with number 9, then we can discard the latter. This is because if we could append a later element k to 9, we can definitely append k to 5 to make a sequence of length 6. Therefore in our dp array, for each dp[i], we store the smallest element that an increasing subsequence of length i can end with. With a new element k, we search for the largest dp[i] that is smaller than k, then assign k to dp[i+1] in case k is smaller than dp[i+1]. Then the length of the longest increasing subsequence would be the largest i such that dp[i] exists.

Since this post is not meant to teach you introductions to algorithms, you should google it if you don’t understand. I’m just trying to how to implement it without making a mess. In the algorithm, there’s a part of binary search, so that could be replaced by a vector upper_bound. It turns out that instead of appending to the subsequences, it’s easier to work in reverse and prepend to them. If we are searching for a larger element, that means we are finding an increasing subsequence that starts with a number larger than the current one, and we are trying to prepend to it. Let’s look at the code and analyze it:

int lengthOfLIS(vector<int>& nums) {
    vector<int> s;
    for (int i = nums.size()-1; i >= 0; i--) {
        auto it = upper_bound(s.rbegin(), s.rend(), nums[i]);
        if (it == s.rbegin())
        else if (*(--it) < nums[i])
            *it = nums[i];
    return s.size();

Here, s[i] denotes the largest number that a subsequence with length i can start with. As the length increases, intuitively the starting number has to be smaller, so this vector is strictly decreasing. To use upper_bound to binary search for the slightly larger element to update, we need to pass in the reverse iterators rbegin() and rend(). If the returned iterator is the last element in the vector, that means we have found a new longest increasing subsequence. Otherwise, it means we have found a better increasing subsequence of the same length with a larger (better) starting value.

Final remark on longest increasing subsequence: to get the longest nondecreasing subsequence, we can preprocess the array to use almost the exact same code above. Here’s how:

int lengthOfLNDS(vector<int> nums) {
    vector<pair<int, int> > v;
    for (int i = 0; i < nums.size(); i++)
        v.push_back(make_pair(nums[i], i));
    vector<pair<int, int> > s;
    for (int i = v.size()-1; i >= 0; i--) {
        auto it = upper_bound(s.rbegin(), s.rend(), v[i]);
        if (it == s.rbegin())
        else if (*(--it) < v[i])
            *it = v[i];
    return s.size();

Pretty simple, I just used a pair<int, int> to replace int. The first item is the original data, the second item is the array index, used to tie break equal values.


This should be a relatively easy post. Things covered: auto, iterator, sort, next permutation, reverse and swap. If you know all of these you can skip.



Auto is a keyword that saves you some thinking time. It is nothing but a lazy way to write code, no concept or algorithm whatsoever. Like how Python induces the data type, you can use auto to force your compiler to do your job.

auto x = 5;
auto p = make_pair(2, 4);
auto s = vector<int>(4);

When would you ever want to be lazy, as a hardworking programmer, you ask? Well it helps shorten the code sometimes, especially in the case of iterators.



Since implementation is hidden in a black box for STL data structures, we have less control over how to mess with the data directly. That’s why we have iterators to let us peep into the black box. Iterators for each data structure are different from others, but they mostly do one thing: iterating through data points you put in the data structure. You always initialize an iterator from an instance of a data structure, for example the begin() function of sets and maps, which we have seen in the previous post.

Iterators act as pointers to elements, so you need to dereference to get the value. For sets and maps, they could be quite useful:

vector<int> v{1, 5, 8, 2, 9};
set<int> s;
map<int, int> m;
for (int i = 0; i < v.size(); i++) {
    m[v[i]] = i;
for (auto it = s.begin(); it != s.end(); it++)
    cout << *s << endl;
for (auto it = m.begin(); it != m.end(); it++)
    cout << it->first << " " << it->second << endl;

Had I not used auto, I would have written set<int>::iterator and map<int, int>::iterator. Then your code will look uglier, but that’s a personal preference.

To explain a little bit, .begin() gives an iterator to the first item in the data structure. In the case of set and map, begin() points to the smallest element.

Then, .end() returns a special iterator marking the end of the data structure. It is not the last element; it is the iterator after the last element. Trying to dereference it will crash your program.

To print things in reverse order, just use rbegin() and rend() in place of begin() and end(), no pain at all. The ++ operator gives you the next iterator, and — gives you the previous one. We will see subtleties later on with these two operators.

Another shorthand for the loop in order above:

for (auto it : m)
    cout << it.first << " " << it.second << endl;

note that the “it” here is not actually the iterator, but a dereferenced key-value pair. Like literally a pair<int, int>.



To sort a vector, just pass in the begin() and end() iterators. Obviously it modifies the vector you pass into it.

vector<int> v{1, 4, 5, 2, 6, 3}
sort(v.begin(), v.end()); // {1, 2, 3, 4, 5, 6}
sort(v.rbegin(), v.rend()); // {6, 5, 4, 3, 2, 1}

If you are a hardcore c fan, you can even pass in c array pointers, since iterators are like pointers anyways:

int v[] = {1, 4, 5, 2, 6, 3};
sort(v, v+6);

Strings are like vector<char>, so you can sort a string too. For example, for the anagram problem last time, a really short piece of code could be:

sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;

This is going to be O(nlog(n)), n being the sum of length of the two strings. So strictly speaking this is not the best solution ever, but hey it’s only three lines.


Next permutation

This is a really handy way to enumerate all n! ways to permute a vector of size n. Let’s say for some reason you need to generate all 720 permutations of {1, 2, 3, 4, 5}, this is all you need to do:

vector<int> v{1, 2, 3, 4 ,5};
do {
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

It is good to know the algorithm behind this function, basically you just go from the back to the front, until the next number is smaller, then you swap that next number with a slightly larger number from this number to the back, and keep everything in ascending order after this slightly larger guy.

One cool aspect about this function is that you can hack it so it gives you combinations instead of permutations. Let’s say you have 5 guys, and you want to choose 2 of them. Then you just feed the function with a special vector:

vector<int> v{0, 0, 0, 1, 1};
do {
    for (int i = 0; i < v.size(); i++)
        if (v[i] == 1)
            cout << i << " is chosen" << endl;
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

This function is useful in interviews, but rarely applicable in real life. But when you actually need to enumerate, things will be so much easier with a bug-free built-in function.



To reverse a vector, there’s a function aptly called reverse. Like sort, that will modify the original vector. If you don’t want to modify it, you can make a new vector via a special constructor.

vector<int> v{1, 2, 3, 4 ,5};
string s = "abcde";
reverse(v.begin(), v.end()); // {5, 4, 3, 2, 1}
reverse(s.begin(), s.end()); // "edcba"
vector<int> u(v.rbegin(), v.rend()); // {1, 2, 3, 4, 5}
string t(s.rbegin(), s.rend()); // "abcde"

Please don’t write a for loop to do what you can do with built-in functions. You will be surprised how many fewer bugs you need to clean with shorter code and fewer loops.

Another trick that is occasionally useful: let’s say you want to reverse the 3rd to 6th character (start counting from 0th) of string s. Then you can:

string s = "12345678";
reverse(s.begin()+3, s.begin()+7);
cout << s << endl; // 12376548

Note that the second parameter is always one after the last element you want to swap.



There are two swap functions. The first is swap(x, y) which swaps two variables of the same type, the other is a way to rename your black boxes.

To swap two variables:

int x = 3, y = 6;
swap(x, y);
string s = "12345";
swap(s[2], s[4]);

Another is to swap the content of STL data structures.


But you can just write swap(s0, s1) instead, because since C++11 there is no performance difference between the two.



Sometimes if you want to deal with an object, there are some unnecessary deep copies that make your code less efficient. For example in the following code, if we ignore the function move(), there will be two copies of “test”, one stored in s and one stored in the vector. The point is, we don’t care what s becomes afterwards, so we can destroy it after pushing it to the vector. Move does exactly this: destroy the original, so we only have 1 instance of the object, and we can eliminate the time complexity due to deep copy.

// Destroying a string after pushing to the vector
vector<string> v;
string s = "test";
// Setting v1 to v2 in O(1) time
v1 = move(v2);


Ok, that should be enough for us to grab a problem. Here’s a medium level one:

Binary Tree Right Side View

TLDR: given a binary tree, output the rightmost element in each layer in a vector. The algorithm is to traverse the tree layer by layer, each time pushing in the value of the right most node:

vector<int> rightSideView(TreeNode* root) {
    vector<int> ans;
    if (!root)
        return ans;
    vector<TreeNode*> layer{root};
    while (!layer.empty()) {
        vector<TreeNode*> next;
        for (auto it : layer)
            for (TreeNode* c : {it->left, it->right})
                if (c)
        layer = move(next);
    return ans;

Notice the use of for (auto x : y) in this context: x would be the actual element, so I did not dereference it before I used it as a TreeNode*. Also note the move at the end of the loop.

Last small remark: in C++, NULL is the only pointer value that means false, and 0 is the only integer value that means false. So you can write if (ptr) or if (!ptr) to test for null, and if (num) or if (!num) to test for 0 value.

Next, we’ll talk about upper_bound and lower_bound.


This post in a nutshell:

vector<vector<pair<int, map<int, set<int> > > > >
    nutshell(n, vector<pair<int, map<int, set<int> > > >(m));

If you know what that means (not that it MEANS anything), then you can skip this post.

STL is the most basic and useful topic. With good practices, they can make your code much more concise and easier to debug.



Basic facts:

  1. push_back() is O(1), pop_back() is O(1);
  2. you can make 2D arrays with different lengths for each row;
  3. initialize a multi-dimensional array in 1 line;
  4. let vector take care of all the dynamic allocation and deallocation of memory you ever need;
  5. avoid stack overflow at times.

Some initialization methods:

// Initialization of 1D vector with no elements:
vector<int> x;

// Initialization of 1D vector with 10 elements, default value 0:
vector<int> x(10);

// Initialization of 1D vector with 10 elements, default value -1:
vector<int> x(10, -1);

// Initialization of 2D vector of 10 rows x 20 columns, default value 0:
vector<vector<int> > x(10, vector<int>(20));

// Initialization of 2D vector of 10 rows x 20 columns, default value -1:
vector<vector<int> > x(10, vector<int>(20, -1));

// Initialization of a 1D vector of user defined values:
vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Vectors can be used as stacks, with push_back(), back(), and pop_back().

vector<int> stack{1, 2, 3, 4, 5};
while (!stack.empty()) {
    cout << stack.back() << endl;
// output: 5 4 3 2 1

I will cover more usages of vectors, for example for BFS and DFS, when I get through more problems.



Sets are very useful and powerful. Basic facts:

  1. elements are unique;
  2. insert, take smallest, take largest, find, erase any element are O(log(n)), so you can use it as a heap/priority queue;
  3. elements are in sorted order;
  4. binary search is built-in, which I will go through in a coming post;
  5. inside the black box, sets are balanced binary search trees.

Making a set:

// Initializing an empty set
set<int> s;

// Initializing a set with elements from a vector
set<int> s(v.begin(), v.end());

Finding if an element is in a set:

if (s.find(k) == s.end()) { // alternatively, if (s.count(k) == 0) {
    cout << "not in the set" << endl;
} else {
    cout << "found in the set" << endl;

Inserting to a set:


Finding the smallest and largest in a set:

if (!s.empty()) {

    cout << "smallest element: " << *s.begin() << endl;

    cout << "largest element: " << *s.rbegin() << endl;


Erasing an element in the set:


Notice that there are two ways to erase an element: you can either pass in the iterator of the element, or pass in the actual element value. I will probably leave iterators to another post so this one is not super long.

When you do not need the elements sorted, you might want to consider using std::unordered_set instead of set, which is basically a hash table version of set. Insert, find, erase will become O(1), but space required is larger, time constant is larger which means it might hurt performance for small set sizes, and you will not be able to get the smallest element in O(log(n)).

Sometimes you do not want the elements to be unique, say you want to keep the height of each student in a class in a set. Then you would want std::multiset, which is basically set without the unique element requirement.



Maps are like dictionaries, it maps one simple thing (a word) to another thing (its definition). Basic facts:

  1. keys are unique;
  2. insert, take smallest, take largest, find, erase any key are O(log(n));
  3. keys are in sorted order;
  4. binary search is built-in;
  5. inside the black box, maps are balanced binary search trees, each node containing a second data (the value) that is not used for comparison.

Make a map:

map<int, int> m;

Put something in the map:

m[42] = 3;

Tip: you can access a non-existent key-value pair this way:

map<int, int> m;


This way of access to a non-existent key-value pair will throw an exception, sometimes good for debugging, and otherwise equivalent to the above:




I think pair is the most underrated STL data structure ever. It is not taught in classes usually (not in mine anyways) because it does not contain any special algorithm, but it is a great shorthand for simple data structures. Basic facts:

  1. a pair sticks 2 things together;
  2. it has a default comparator which compares the first guy, and if they tie, compares the second guy.

To make a pair:

pair<int, int> p0;
pair<int, int> p1 = make_pair(1, 2);
if (p0 < p1)
    cout << "0 < 1 confirmed" << endl;


Now that we have all the pieces, we can start sticking things one inside another. Let’s grab a Leetcode problem:

Valid Anagram
TLDR: given two strings with lowercase letters, determine if they are anagrams of each other.

Here’s one way to do it using vector, with f[i] counting the frequency of the (i+1)th alphabet:

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    vector<int> f(26);
    for (int i = 0; i < s.length(); i++) {
    for (int i = 0; i < 26; i++)
        if (f[i] != 0) return false;
    return true;

Here’s another way to do it using map, same idea:

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, int> m;
    for (int i = 0; i < s.length(); i++) {
    for (unordered_map<char, int>::iterator i = m.begin(); i != m.end(); i++)
        if (i->second != 0) return false;
    return true;

Yeah… That’s quite trivial. But we’ll get to the fun stuff after we have all the basics.

One final remark for STL data structures: put them in the scope where they belong. For example, if you need to create a vector 10 times, don’t make one vector as a global variable but rather create the vector within the for loop, so you won’t accidentally use garbage values left from the last iteration.

Index: Tech Interview Walkthrough

In order to prove the worth of this site, I am planning to write a series of posts about writing clean code in CS tech interviews. The entire series will focus on only the basics. Although these topics are supposedly basic stuff, there’s a lot that I didn’t know a year ago, before I got into semi-serious programming training. I will pick interesting problems from Leetcode, group them by similarity, and discuss the tricks to make debugging less painful.


Target audience:

  • If you are looking for a job in CS;
  • and you are not extremely good at it;
  • and you often write long and clumsy code very slowly during interviews;
  • and you plan on using C++, then my posts might be useful.

If you compete a lot in programming contests, then you probably have seen most of what I will talk about.


What this series is NOT:

  • Introduction to algorithms: there are many algorithms that I will not cover, simply because there is not a single way to write elegant code for that particular algorithm (for example greedy), or will not be useful in interviews (say, max flow).
  • How to get a job offer in a month: after learning the tricks, it takes a lot of practice to know how to apply them.
  • Professional C++: you might learn a bit about the language, but I’m not an expert in C++, so you won’t become one by reading my posts.
  • ACM programming contests guide: I am simply unqualified to be your coach.


Things to know:

  • my code runs on C++11, if you don’t know how to compile, Google it;
  • I ignore all the includes, using namespace std and stuff, fix it yourself.


List of topics:

1. STL

2. Things about arrays

3. Edgy things

4. Linked lists

5. Special topics

Happy coding!