Binary Search: A Better Way

So you think you know how to write binary search – just like everyone else. I mean, it’s easy, right? Maybe, but you can probably do it better. Let’s start with an example. Say you have a sorted integer array, and you want to find the largest integer no larger than k, and return its index.

So it usually goes like this: let n = size of array, l = 0 and r = n-1, and dive into a while loop. In the loop, you find a mid point between l and r. And you quit when you have only one number left, which is l = r.

int l = 0, r = n - 1;
while (l < r) {
    int mid = (l + r) / 2;
}

Then what do you do? Well, you could compare it with k.

while (l < r) {
    int mid = (l + r) / 2;
    if (v[mid] > k)
        r = mid - 1;
    else
        l = mid;
}
return l;

If v[mid] is larger than k, then all the valid answers can only be between l and mid-1. Otherwise, anywhere from mid to r could be the answer.

Now you’re happy and you try to run it – and it doesn’t work! In fact, not only does it not work, it’s a terrible piece of crap. Here’s why.

1. Edge cases

What happens if (1) the array is empty, (2) all integers are smaller than k, (3) all integers are larger than k? Well in (1) you’ll return 0 which is wrong, in (2) you’ll get an infinite loop (to be explained later), and in (3) you’ll get 0, which is also wrong. The correct results would be (1) -1 for not found, (2) n-1, and (3) -1 for not found. This algorithm gets all edge cases wrong!

2. Infinite loop

Say if we are given k = 2 and the array {0, 1}. l starts at 0 and r starts at 1, so mid would be (0 + 1) / 2 = 0. And 0 is not larger than 2, so we set l to mid, which is 0. We’re back to the same situation, and this loop will never end!

There are ways to fix the code, of course – you handle the special cases by spraying if statements all over the place, and you can fix the infinite loop with setting mid to (l + r + 1)/2. Like this:

if (n == 0 || v[0] > k)
    return -1;
int l = 0, r = n - 1;
while (l < r) {
    int mid = (l + r + 1) / 2;
    if (v[mid] > k)
        r = mid - 1;
    else
        l = mid;
}
return l;

But it’s ugly! We have to pick between (l + r) and (l + r + 1), which seems totally arbitrary, and there are edge cases to consider. What went wrong?

Everything from the very beginning went wrong. At the point we set l to 0 and r to n-1, we’re already making an implicit statement (loop invariant). We’re assuming that every iteration as we enter the loop, the answer could be anywhere from l to r. But this isn’t even true! If the answer doesn’t exist, then obviously the answer can’t be between l to r. The other assumption made is that the r-l always decreases after each iteration (so the loop eventually terminates) – which is also not true, as examplified in the infinite loop case. Since the loop invariants never held, we get gibberish at the end of the algorithm.

It turns out that if we change our loop invariant, we could be in a much better situation. Here’s the proposal: the transition between the last integer that’s at most k and the first integer that’s larger than k is always between l and r.

That means l must start at -1, and r at n. This is because the transition could happen from -1 to 0 (before the first element) or from n-1 to n (after the last element). The stopping condition would be l + 1 = r, because by then we would know the transition is from l to r, and the answer would be l. Let’s try to code this out:

int l = -1, r = n;
while (l + 1 < r) {
    int mid = (l + r) / 2;
    if (v[mid] > k)
        r = mid;
    else
        l = mid;
}
return l;

Magically, this code handles all edge cases correctly! It’s absolutely correct given any input. We don’t have any more edge cases because we can express all cases using l and r. If the list is empty or all numbers are greater than k, then our “transition” would occur before the first number, which means l = -1 and r = 0. Even though v[-1] is invalid, (l, r) = (-1, 0) is a valid statement that implies there is no element at most k. We also don’t have infinite loops anymore, because when l and r differ at least by 2, (l + r) / 2 is guaranteed to not equal l or r.

As we can see here, instead of searching for an element, we’re really searching for a transition. And by making this change, our code becomes more elegant.

Let’s try this again and do Guess Number Higher or Lower. The problem is that given a function [int guess(int num)] which is equal to [int compare(int magic, int num)], guess the magic number.

int guessNumber(int n) {
    long long l = 0, r = n;
    while (r-l > 1) {
        long long mid = (l+r)/2;
        int res = guess(mid);
        if (!res) return mid;
        else if (res == -1)
            r = mid;
        else
            l = mid;
    }
    return r;
}

Binary search other than array indices

Split Array Largest Sum (hard)

Sometimes, instead of binary searching over the space of indices of an array, we might instead binary search over the space of the answer. See Split Array Largest Sum (hard). Given an array of nonnegative integers, return the least possible threshold such that you can partition the array into m subarrays where the sum of each subarray does not exceed the threshold. The idea here is that directly finding this number is hard, but it is easy to tell given the threshold, the minimum number of subarrays needed such that the threshold condition is met. The algorithm is then binary search for the threshold, compute the minimum number of partitions of that threshold, and find the smallest threshold such that the number of partitions is at most m.

bool valid(vector<int>& nums, int m, long long sum) {
    int cnt = 1;
    long long run = 0;
    for (int x : nums) {
        if (run + x > sum) {
            cnt++;
            run = x;
        } else {
            run += x;
        }
    }
    return cnt <= m;
}
 
int splitArray(vector<int>& nums, int m) {
    long long tot = nums[0];
    int low = nums[0];
    for (int x : nums) {
        tot += x;
        low = max(low, x);
    }
    long long l = low-1, r = tot;
    while (r-l > 1) {
        long long mid = (l+r)/2;
        if (valid(nums, m, mid))
            r = mid;
        else
            l = mid;
    }
    return r;
}

In the valid function, I calculate the number of sections needed, and if it goes over m, that means the current number is too low, hence invalid. We also know that the answer will not be smaller than the largest element in the array, and will not be larger than the sum of the entire array.

Searching for real

And of course you can binary search over a real number range as well. Imagine in the previous example, the input is instead an array of doubles, and the threshold is also a double. The algorithm is basically the same, except that we need to handle floating point comparisons using an [int sign(double x)] function.

int sign(double x) {
    double eps = 1e-10;
    return x < -eps ? -1 : x > eps;
}
 
bool valid(vector<double>& nums, int m, double sum) {
    int cnt = 1;
    double run = 0;
    for (double x : nums) {
        if (sign(run + x - sum) > 0) {
            cnt++;
            run = x;
        } else {
            run += x;
        }
    }
    return (cnt <= m);
}
 
double splitArray(vector<double>& nums, int m) {
    double tot = nums[0];
    int low = nums[0];
    for (double x : nums) {
        tot += x;
        low = max(low, x);
    }
    long long l = low, r = tot;
    while (sign(r - l) > 0) {
    double mid = (l + r) / 2;
    if (valid(nums, m, mid))
        r = mid;
    else
        l = mid;
    }
    return r;
}

The sign function is used to control the accuracy of double. This is because double arithmetic is not exact, and we need to make sure we are comparing them correctly. Using this function, a < b is rewritten as sign(b-a) > 0, and a >= b is rewritten as sign(a-b) >= 0. The easy way to think about this is to move terms across the inequality signs such that one side becomes zero, then wrap the other side in the sign function.

That’s it for now.

TIW: Range Sum

Prefix array sum is a useful tool that shows up often. It achieves the following:

  1. For a given array of n integers that will not change over the course of program execution, precomputation runs in O(n).
  2. After the precomputation step, querying the range sum (summation of v[l..r]) is O(1).

Here’s how you do it in code:

vector<int> v{1, 2, 3, 4, 5};
vector<int> s{0};
for (int x : v)
    s.push_back(s.back()+x);
int i = 2, j = 4;
cout << "3+4+5 = " << s[j+1]-s[i] << endl;

There are two things to note: first, the size of s, our prefix sum array, is one larger than our original array, and the indices are shifted by one; second, in all summation problems, always think about overflow and whether you need to use long long instead of int.

For those who haven’t seen this before, s[i] is the sum of integers from v[0] to v[i-1]. We’re essentially generating the sums of {}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4} and {1, 2, 3, 4, 5}, and say we want to know the sum of {3, 4, 5}, you just use sum {1, 2, 3, 4, 5} to substract sum {1, 2}.

The trick here that I want to bring out is the initial value in the array, 0. Without the 0, the code will look like this:

vector<int> v{1, 2, 3, 4, 5};
vector<int> s{v[0]};
for (int i = 1; i < v.size(); i++) {
    s.push_back(s.back()+v[i]);
int i = 2, j = 4;
cout << "3+4+5 = " << s[j]-(i > 0 ? s[i-1] : 0) << endl;

OMG, no. Please don’t do this.
This is actually all it takes to solve Range Sum Query – Immutable:

class NumArray {
private:
    vector<int> s;
public:
    NumArray(vector<int> &nums) {
        s.push_back(0);
        for (int x : nums)
            s.push_back(s.back()+x);
    }

    int sumRange(int i, int j) {
        return s[j+1]-s[i];
    }
};

It’s just my personal preference to put class members and methods as private. Everything is the same as above, nothing to see here.

A slightly harder version is doing this in 2 dimensions, but it’s merely putting the above code in some loops and doing it over and over again. Anyway, let’s look at this problem first:

Range Sum Query 2D – Immutable

Given a 2D array, compute summation of a rectangle of the array in O(1) time after precomputation.

So there are two parts to explain: what our “2D prefix sum array” looks like, and how to compute it in linear time.

In 1D, we have one index, i, for each number, and we sum everything from index 0 to index i-1. Similarly in 2D, we have two indices, i, j, and we sum everything 0 <= i’ < i, 0 <= j’ < j. With the same shift-by-one convention, our notation will be: s[i][j] = sum {v[0..i-1][0..j-1]}. To calculate the sum of numbers in the rectangle v[r1..r2][c1..c2], the equation will be: s[r2+1][c2+1] – s[r1][c2+1] – s[r2+1][c1] + s[r1][c1]. To understand why, say if a matrix looks like this:

[ A ] [ B ]

[ C ] [ D ]

Then the sum of D, {D} = {A+B+C+D} – {A+B} – {A+C} + {A}. Therefore there are 4 terms in the expression.

Now down to the second part: how to calculate it in linear time. It’s the same relation, but reversed: {A+B+C+D} = {D} + {A+B} + {A+C} – {A}. In other words, s[i][j] = v[i][j] + s[i-1][j] + s[i][j-1] + s[i-1][j-1].

vector<vector<int> > v{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int r = v.size(), c = v[0].size();
vector<vector<int> > s(r+1, vector<int>(c+1));
for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++)
        s[i][j] = v[i-1][j-1]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
int r1 = 1, r2 = 2, c1 = 0, c2 = 2;
cout << "sum {{4, 5, 6}, {7, 8, 9}} = "
     << s[r2+1][c2+1]-s[r1][c2+1]-s[r2+1][c1]+s[r1][c1] << endl;

As a remark, with some more caution you can do this without any extra space; just store everything in the original array. However you will need to worry about the case about the first item in each 1D array in that case, since you won’t have the zeros padding your matrix to prevent segmentation fault.

The idea of padding a matrix with dummy items is also useful in 2D BFS sometimes, but we can talk about that later.

With some adaptation, this is the code that gets accepted:

class NumMatrix {
private:
    vector<vector<int> > s;
public:
    NumMatrix(vector<vector<int> > &matrix) {
        int r = matrix.size();
        if (r == 0)
            return;
        int c = matrix[0].size();
        s = vector<int>(r+1, vector<int>(c+1));
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                s[i+1][j+1] = matrix[i][j] + s[i][j+1] + s[i+1][j] - s[i][j];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return s[row2+1][col2+1]-s[row1][col2+1]-s[row2+1][col1]+s[row1][col1];
    }
};

Few problems will be so straightforward to apply this approach, but it is often useful as a subroutine in other problems, to reduce the run time complexity. For example this: Count of Range Sum. This is because querying the sum naively is linear in the number of items in the summation, but with this precomputed array we can achieve constant time querying.

That’s basically it; you can call this a data structure with O(n) update and O(1) query, where update means updating an entry in the original matrix, and query means calculating the sum over a rectangle. O(1) update and O(n) query is trivial; you just use the original array for this, and run for loops to calculate the sum every time you want it. But if you want something in between, there’s actually a magical thing called binary indexed tree, which is quite advanced and I will cover in a (very) later post. It achieves O(log(n)) update and query, in somewhere around 10 lines of code.

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)
            r--;
        else
            l++;
    }
    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])
            continue;
        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])
                r--;
            else if (sum < 0 || l > i+1 && nums[l] == nums[l-1])
                l++;
            else {
                ans.push_back({nums[i], nums[l], nums[r]});
                l++;
                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];
            l++;
            t1 = max(t1, height[l]);
        } else {
            ans += t2-height[r];
            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.

TIW: STL #3

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);
        s.insert(x);
    }
    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);
        }
        s.insert(x);
    }
    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())
            s.push_back(nums[i]);
        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())
            s.push_back(v[i]);
        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.

TIW: STL #2

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

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.

 

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++) {
    s.insert(v[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>.

 

Sort

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.

 

Reverse

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.

 

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.

s0.swap(s1);

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

 

Move

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";
v.push_back(move(s));
// 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()) {
        ans.push_back(layer.back()->val);
        vector<TreeNode*> next;
        for (auto it : layer)
            for (TreeNode* c : {it->left, it->right})
                if (c)
                    next.push_back(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.

TIW: STL #1

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.

 

Vector

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;
    stack.pop_back();
}
// 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.

 

Set

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:

s.insert(k);

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:

s.erase(k);
s.erase(s.begin());
s.erase(*s.begin());

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.

 

Map

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;

m[0]++;

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:

m.at(0)++;

 

Pair

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++) {
        f[s[i]-'a']++;
        f[t[i]-'a']--;
    }
    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++) {
        m[s[i]]++;
        m[t[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!

CS201 Project: Tank War

Last semester for CS201 at USC, my group wrote up a game project for class. Not exactly the most innovative or beautifully designed game ever, but the gameplay is pretty fun when it doesn’t lag.

Here’s a link to the executable JAR file: Download

 

Gameplay

First you register a name and put in a password, but make sure you have at least one number and one uppercase letter (don’t ask me why).

Then you either create a room or join a room. So yeah those who don’t have any friend can go home now.

Each person picks a color,

Basically you control a tank and shoot other guys, and they respawn after a while. Pretty typical stuff, but there are two different features:

  1. Bullets rebounce: bullets don’t die until the third time they bump into something;
  2. Tanks can move in all directions, instead of just wasd.

These features make the game quite different.

 

Development

My team has five people, including the following:

Yifan Meng

Anne Yu

Erdong Hu

Hexi Xiao

…and Me

We spent at least 2 weeks on this project, with at least one all-nighter. Ended up with a monster with like 6k lines of Java code.

The game server runs on the EC2 machine that powers this website, and is the lowest tier so please tolerate the lag. I’ll probably keep the server running until my credit card runs out of money.