How to rotate a matrix 90 degrees without using any extra space?

Question

By saying 90 degrees i mean to say if:

A = {1,2,3,
     4,5,6,
     7,8,9}

then after 90 degree rotation A becomes:

A = {7,4,1,
     8,5,2,
     9,6,3}

Answer 1

You need one temp variable, then it is just to jump elements around.

temp = A[0];
A[0] = A[6];
A[6] = A[8];
A[8] = A[2];
A[2] = temp;
temp = A[1];
A[1] = A[3];
A[3] = A[7];
A[7] = A[5];
A[5] = temp;

Answer 2

Transpose and interchange rows or columns (depends whether you want to rotate left or right).

e. g.

1) original matrix

1 2 3
4 5 6
7 8 9

2) transpose

1 4 7
2 5 8
3 6 9

3-a) change rows to rotate left

3 6 9
2 5 8
1 4 7

3-b) or change columns to rotate right

7 4 1
8 5 2
9 6 3

All this operations can be done without allocating new space.

Answer 3

let x be an nxn array 0 based indexing

f = floor(n/2)
c = ceil(n/2)

for x = 0 to f - 1
  for y = 0 to c - 1
    temp = a[x,y]
    a[x,y] = a[y,n-1-x]
    a[y,n-1-x] = a[n-1-x,n-1-y]
    a[n-1-x,n-1-y] = a[n-1-y,x]
    a[n-1-y,x] = temp

Edit If you want to avoid using temp, this works (it also rotates in the correct direction) this time in python.

def rot2(a):
  n = len(a)
  c = (n+1) / 2
  f = n / 2
  for x in range(c):
    for y in range(f):
      a[x][y] = a[x][y] ^ a[n-1-y][x]
      a[n-1-y][x] = a[x][y] ^ a[n-1-y][x]
      a[x][y] = a[x][y] ^ a[n-1-y][x]
      a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
      a[n-1-x][n-1-y] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
      a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
      a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
      a[y][n-1-x] = a[n-1-x][n-1-y]^a[y][n-1-x]
      a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]

Note: This only works for matrices of integers.

Answer 4

The algorithm is to rotate each "ring", working from the outermost to the innermost.

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

The algorithm would rotate all the A's first, then B's then C's. Rotating a ring requires moving 4 values at once.

The index i ranges from 0..ring-width-1, e.g. for A the width is 5.

  (i,0) -> temp
  (0, N-i-1) -> (i, 0)
  (N-i-1, N-1) -> (0, N-i-1)
  (N-1, i) -> (N-i-1, N-1)
  temp -> (N-1, i)  

This is then repeated for each successive inner ring, offsetting the co-ordinates reducing the ring width by 2.

[Another answer has appeared with the code, so I'll not repeat that.]

Answer 5

I came across the following implementation:

For square matrices:

for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

For rectangular matrices:

for each length>1 cycle C of the permutation
    pick a starting address s in C
    let D = data at s
    let x = predecessor of s in the cycle
    while x ≠ s
        move data from x to successor of x
        let x = predecessor of x
    move data from D to successor of s

For more info, one can refer here: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 6

See this article for in-place matrix transposition; also google for "in-place matrix transposition". It can be easily adapted to perform rotation by 90 degrees. To transpose square matrices, you just interchange b[i][j] with b[j][i] where b[k][l] is a[n*k+l]. On nonsquare matrices, it's considerably more difficult. "Without any extra space" is a rather strong requirement, maybe you meant O(1) space? (assuming integers are fixed size) Implementation in C++: here.