Learn more about Russian war crimes in Ukraine.

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.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.