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. Found an error? Edit this page.