Rotate matrix clockwise

Problem statement – Given an array of N rows and N columns (square matrix), rotate the matrix by 90° in clockwise direction.

Rotate matrix Theory of ProgrammingSolution – This is an implementation based problem, which means that when asked in an interview, the interviewer is mainly testing your skill to write a program which follows some set of rules. There are no tricky cases here but you might struggle in the interview if you don’t have the right approach.

For this problem, let us define a cycle like this –

Rotate matrix Theory of ProgrammingSo the cycle is a ring of elements which consists of mirroring row and column. We will solve this problem cycle-by-cycle, which means, we will rotate the 0th cycle, then the 1st cycle and so on.

Now our rotation will start from the upper left corner element. This element’s vertices (i, j) can be easily evaluated from the cycle number it is in.

Rotate matrix Theory of ProgrammingSo, if the upper left corner element of a cycle is in the cycle number c, then its position in the matrix will be (c, c). Now that we have defined one corner of our cycle, let us find the others. If n is the size of the matrix, can you find the indexes of other corners?

Rotate matrix Theory of ProgrammingOkay so n – 1 – c seems to be an important term, let us call it l (like last index).

Rotate matrix Theory of ProgrammingNow to rotate these values, we need to do –

  • int temp = arr[c][c];
  • arr[c][c] = arr[l][c];
  • arr[l][c] = arr[l][l];
  • arr[l][l] = arr[c][l];
  • arr[c][l] = temp;

Now, if we go to the next element of the ring –

Rotate matrix Theory of ProgrammingTo rotate these values, we need to do –

  • int temp = arr[c][c + 1];
  • arr[c][c + 1] = arr[l – 1][c];
  • arr[l – 1][c] = arr[l][l – 1];
  • arr[l][l – 1] = arr[l];
  • arr[c + 1][l] = temp;

Similarly, for the next item in the ring.

Rotate matrix Theory of ProgrammingWe see that the indices vary by 0, 1, 2, etc. This can be generalized into a loop variable, say i

Rotate matrix Theory of ProgrammingSo, for any matrix, number of cycles c will be from [0, … n / 2]. If you think about it even number sized matrices have n / 2 cycles. Odd number sized matrices have n / 2 + 1 cycles, but the inner-most cycle would be a single integer which doesn’t need to be touched.

Value of i will be from [0 … , l – c). Why? Because we need to increment i, until c + i < l. So i < l – c.

So you have two loops and inside them, we need to write those 5 statements which make the rotation. Simple isn’t it? Try to code it, you can refer to my code below if you get stuck.

Code

public static void rotate(int[][] arr) {
    int n = arr.length;

    for (int c = 0; c < n / 2; ++c) {
        int l = n - 1 - c;

        for (int i = 0; i < l - c; ++i) {
            int temp = arr;

            arr = arr[l - i];
            arr[l - i] = arr[l][l - i];
            arr[l][l - i] = arr[l];
            arr[l] = temp;
        }
    }
}

Keep practicing! Happy Coding! 😀

Leave a Reply