# How to rotate a square matrix in-place

Question 1.6 of Cracking the Coding Interview:

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

For any given point `pt` in the square, we can rotate it 90 degrees (clockwise) with the formula:

``````int new_x = width - 1 - old_y;
int new_y = old_x;``````

We can use this repeatedly on a point to get its three equivalent points. We can then this to rotate the values at all four points:

``````Pt pt2 = rotate_pt(pt1);
Pt pt3 = rotate_pt(pt2);
Pt pt4 = rotate_pt(pt3);

Px tmp = m[pt1];
m[pt1] = m[pt4];
m[pt4] = m[pt3];
m[pt3] = m[pt2];
m[pt2] = tmp;``````

If we apply this procedure to all points in the top-left corner, it rotates the entire matrix. There’s just a little subtlety: when `N` is odd, we include the central column, but omit the central row. Note also that when `N` is odd, there’s a central pixel that doesn’t need to be rotated, and our procedure doesn’t touch it at all.

Here’s my solution in C:

``````
#include <stdlib.h>
#include <stdio.h>

typedef struct Pt {
int x;
int y;
} Pt;

Pt rotate_pt(int width, Pt pt) {
return (Pt){
width-1-pt.y,
pt.x
};
}

typedef int Px;

typedef struct Matrix {
int width;
Px* arr;
} Matrix;

Px matrix_get(Matrix m, Pt pt) {
return m.arr[(pt.x * m.width) + pt.y];
}

void matrix_set(Matrix m, Pt pt, Px px) {
m.arr[(pt.x * m.width) + pt.y] = px;
}

void rotate_matrix_at(Matrix m, Pt pt1) {
Pt pt2 = rotate_pt(m.width, pt1);
Pt pt3 = rotate_pt(m.width, pt2);
Pt pt4 = rotate_pt(m.width, pt3);

Px tmp =           matrix_get(m, pt1);
matrix_set(m, pt1, matrix_get(m, pt4));
matrix_set(m, pt4, matrix_get(m, pt3));
matrix_set(m, pt3, matrix_get(m, pt2));
matrix_set(m, pt2, tmp);
}

void rotate_matrix(Matrix m) {
int num_x = (m.width/2) + (m.width%2);
int num_y = m.width/2;
for (int y = 0; y < num_y; y++) {
for (int x = 0; x < num_x; x++) {
rotate_matrix_at(m, (Pt){x,y});
}
}
}

void print_matrix(Matrix m) {
for (int y = 0; y < m.width; y++) {
for (int x = 0; x < m.width; x++) {
Px px = matrix_get(m, (Pt){x,y});
printf("%i  ", px);
}
printf("\n");
}
printf("\n");
}

Matrix test_matrix(int width) {
Matrix test = (Matrix){
width,
calloc(width*width, sizeof(Px))
};
for (int x = 0; x < width; x++) {
for (int y = 0; y < width; y++) {
matrix_set(test, (Pt){x,y}, (x+1)*10+y+1);
}
}
return test;
}

int main(int argc, char** argv) {
Matrix test_odd = test_matrix(3);
print_matrix(test_odd);
rotate_matrix(test_odd);
print_matrix(test_odd);

Matrix test_even = test_matrix(4);
print_matrix(test_even);
rotate_matrix(test_even);
print_matrix(test_even);

return 0;
}``````

This runs in `O(n^2)`, i.e. linear time in the size of the array, which is optimal, because we at least have to look at all the pixels.