# 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.

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.