5 minute read

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.

Categories:

Updated: