## Matrix Rotation

### June 6, 2017

We have a two-part exercise today, based on a Microsoft interview question.

First, write a program to rotate an *m* × *n* matrix 90° to the right, as shown below; your solution should touch each matrix element only once:

a b c d e f m j g d a A = g h i rot(A) = n k h e b j k l o l i f c m n o

Second, write a program to rotate a square matrix with *n* rows and columns *in-place*. where the source and target matrices are the same matrix and there is no intermediate matrix (be sure your solution works for both even and odd *n*):

a b c d e u p k f a f g h i j v q l g b B = k l m n o rot(B) = w r m h c p q r s t x s n i d u v w x y y t o j e

Your task is to write the two programs that rotate matrices. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

The first part of the exercise in Python

Both parts of the exercise in Julia. Just a single generic method covering all possibilities.

function rotate{T <: Any}(X::Matrix{T})

n = size(X, 1)

n1 = n + 1

Y = X'

for i = 1:div(n, 2)

j = n1 – i

Y[:,i], Y[:,j] = Y[:,j], Y[:,i]

end

return Y

end

The second part in Python. The rotation is done by swapping two matrix elements at the time.

A better version of the second part. This version sets the matrix elements only once.

Klong version

Python 3.6.

rot() is basically the same as Paul’s.

rot_in_place() moves four corresponding elements at a time. ‘i’ can be thought of as the layer or ring, 0 being the outermost ring.

‘i’, ‘ir’, ‘j’, and ‘jr’ are the row or column indices of the elements being moved.

rot = lambda m:[*zip(*m[::-1])]

def rot_in_place(a):

n = len(a)

for i in range((n+1) // 2):

ir = -i-1

for j in range(i, n-i-1):

jr = -j-1

(a[i][j], a[j][ir],

a[jr][i],a[ir][jr]) = (a[jr][i], a[i][j],

a[ir][jr],a[j][ir])