CODEWITHSUNDEEP
arraysalgorithmrotation
sc_ray
sc_ray

Reputation: 8043

Rotating a 2-d array by 90 degrees

A frequent question that props up during array manipulation exercises is to rotate a two dimensional array by 90 degrees. There are a few SO posts that answer how to do it in a variety of programming languages. My question is to clarify one of the answers that is out there and explore what sort of thought-process is required in order to get to the answer in an organic manner.

The solution to this problem that I found goes as follows:

public static void rotate(int[][] matrix,int n)
{
  for( layer = 0;layer < n/2;++layer){
      int first = layer;
      int last = n -1 - layer;
      for(int i = first;i<last;++i){
        int offset = i - first;
        int top = matrix[first][i];
        matrix[first][i] = matrix[last-offset][first];
        matrix[last-offset][first] = matrix[last][last-offset];
        matrix[last][last-offset] = matrix[i][last];
        matrix[i][last] = top;
       }
    }
}

I have somewhat of an idea what the code above is trying to do, it is swapping out the extremities/corners by doing a four-way swap and doing the same for the other cells separated by some offset.

Stepping through this code I know it works, what I do not get is the mathematical basis for the above given algorithm. What is the rationale behind the 'layer','first','last' and the offset?

How did 'last' turn out to be n-1-layer? Why is the offset i-first? What is the offset in the first place?

If somebody could explain the genesis of this algorithm and step me through the thought process to come up with the solution, that will be great.

Thanks

Upvotes: 3

Views: 2635

Answers (1)

Beta
Beta

Reputation: 99094

The idea is to break down the big task (rotating a square matrix) into smaller tasks.

First, a square matrix can be broken into concentric square rings. The rotation of a ring is independent from the rotation of other rings, so to rotate the matrix just rotate each of the rings, one by one. In this case, we start at the outermost ring and work inward. We count the rings using layer (or first, same thing), and stop when we get to the middle, which is why it goes up to n/2. (It is worth checking to make sure this will work for odd and even n.) It is useful to keep track of the "far edge" of the ring, using last = n - 1 - layer. For instance, in a 5x5 matrix, the first ring starts at first=0 and ends at last=4, the second ring starts at first=1 and ends at last=3 and so on.

How to rotate a ring? Walk right along the top edge, up along the left edge, left along the bottom edge and down along the right edge, all at the same time. At each step swap the four values around. The coordinate that changes is i, and the number of steps is offset. For example, when walking around the second ring, i goes {1,2,3} and offset goes {0,1,2}.

Upvotes: 6

Related Questions